Competitive Programming

Main points for today

NAIPC Rules & Registration

The North American Invitational Programming Contest will take place from to on Friday, March 2.

Form teams of up to 3. The registration deadline is next Thursday, but I'm not sure of the time so if you want to participate you should find a team and register before next week's meeting.

All contestants will need an ICPC account.

Register for the Open Division (USA & Canada).

No rule about internet access is enforced, but participants are strongly encouraged to follow ICPC rules—that is, one computer per team and no internet access other than the submission system standard language documentation like would be provided at an ICPC competition.

In lieu of printed documentation alongside the standard language documentation, it will be fine for teams to have a second computer as long as it is dedicated to viewing documentation that would otherwise be printed—in our case, that's anything in this folder and anything that has been posted on Slack.

Supported languages and the recommended reference documentation:

Read input from stdin and output to stdout. Anything written on stderr will be ignored. All standard libraries included with each language are allowed. All submissions must exit with code 0; submissions exiting with a non-zero code will be judged as Run Time Errors.

Practicing with virtual contests

Just a reminder that virtual contests on Codeforces are a great way to practice! These allow you to simulate a past Codeforces round at any time and see how you would have placed in the contest rankings. It's just like participating in an actual contest, but it does not affect your Codeforces rating.

Furthermore, teams can participate in virtual contests for team practice—register a team at https://codeforces.com/teams/new

Most Codeforces rounds last 2 hours.

Documentation

Please post links to helpful resources in #compprogramming-docs

Some content that will be integrated into our printed notes into the future:

Some helpful code

C++ boilerplate

The following (boilerplate.cpp) is a good starting point for solving problems in C++:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool DB = 0;

template <typename T1, typename... T2>
void db(T1&& x1, T2&&... x2) {
    if(!DB) return;
    cout << forward<T1>(x1);
    ((cout << ' ' << forward<T2>(x2)), ...);
    cout << endl;
}

#define PULSE db("Alive at line", __LINE__)

int main(int argc, char *argv[]) {
    DB = !!(argc - 1);
    (void) argv;
    
    PULSE;
}

This template provides a db function that prints its arguments to stderr only if a command-line argument is passed to the program (which also sets the global DB boolean). Since (in almost all problems) no command line argument is passed to the executable, you do not have to comment this code out before submission. It also provides the PULSE macro, which prints the line number on which it is placed when the program reaches that line, and uses bits/stdc++.h and using namespace std to import the entire standard library into the current scope so you don't have to deal with header files or scope resolution. (This does increase compilation time, but this is not usually a concern for competitive programming. Note that this is very poor style in production C++.) Finally, it typedefs ll to long long int, which should be used in place of int whenever possible to avoid overflows.

It uses C++17 features, so be sure to compile it with -std=c++17 or -std=gnu++17

More robust C++ debug headers

Codeforces user Danila Danko (Sanitator) recently posted to his Codeforces blog a fairly robust C++ header that can easily print containers. Unfortunately, the post has since been deleted, so I have archived it here; the header file itself is here. It requires C++17.

Another project allowing easy printing of STL containers is Louis Delacroix's C++ Container Pretty-Printer. It is available in both C++11 and C++98 versions.

Useful C++ macros

For fast C++ programming, it is often useful to have some defines for common idioms. Some particularly helpful examples follow:

#define FOR(x,to) for(x = 0; x < (to); x++)
#define UPTO(to) for(ll i = 0; i < (to); i--)
#define IN(x,arr) for(auto& x : arr)
#define EACH(arr) for(auto& x : arr)
#define OUT(x) cout << (x) << endl

Having these in your boilerplate significantly reduces the amount of typing required for the most common for loops and for printing scalar variables to cout.

A simple testing script

After noticing I spent a lot of time manually entering test cases and comparing their output to the expected output, I wrote a small shell script to assist in testing. Place your source file (say, prob3.cpp) and sample inputs and outputs with names like prob3.in1, prob3.out1, prob3.in2, prob3.out2, etc. in the same directory and run tester prob3 in this directory.

For further details, see the readme. The script itself can be found here. It is also reproduced below so it can be manually entered at a competition if I am so inclined.

#!/bin/bash

if [ -z "$1" ]
then
    echo No program specified
    exit 1
fi

if [ -n "$2" ]
then
    echo ==== DEBUG MODE ENABLED ====
    echo
fi

if [[ $1 == *.cpp ]]
then
    L=cpp
    PROG=${1:0:-4}
elif [[ $1 == *.py ]]
then
    L=py
    PROG=${1:0:-3}
elif [[ $1 == *.c ]]
then
    L=c
    PROG=${1:0:-2}
elif [[ $1 == *.java ]]
then
    L=java
    PROG=${1:0:-5}
elif [[ $1 == *.pl ]]
then
    L=pl
    PROG=${1:0:-3}
else
    L=cpp
    PROG=$1
fi

set -e
if [ $L != "pl" ] && [ $L != "py" ]
then
    echo
    echo ==== COMPILER MESSAGES ====
    case $L in
        cpp)
            if [ -n "$2" ]
            then
                g++ -O2 -std=gnu++17 -lm -s -static -Wall -Wextra -o $PROG $PROG.cpp
            else
                g++ -O2 -std=gnu++17 -lm -s -static -o $PROG $PROG.cpp
            fi
            ;;
        c)
            gcc -O2 -static -std=c11 -fno-asm -lm -s -o $PROG $PROG.c
            ;;
        java)
            javac $PROG.java
            ;;
        *)
            echo "Unrecognized language"
            exit 2
            ;;
    esac
    echo
fi
set +e

if [ -e $PROG.in ]
then
    echo
    echo ==== TESTING $PROG.in ====
    echo ==== YOUR STDERR ====
    case $L in
        py)
            python3 $PROG.py $2 < $PROG.in > $PROG.output
            ;;
        pl)
            perl $PROG.pl $2 < $PROG.in > $PROG.output
            ;;
        java)
            java $PROG $2 < $PROG.in > $PROG.output
            ;;
        *)
            ./$PROG $2 < $PROG.in > $PROG.output
            ;;
    esac
    echo

    echo ==== YOUR STDOUT ====
    cat $PROG.output
    echo

    echo ==== DIFF WITH EXPECTED OUTPUT ====
    diff --color $PROG.out $PROG.output
    if [ $? -ne 0 ] && [ -z "$2" ]
    then
        rm $PROG.output $PROG
        exit $?
    fi
    echo
fi

i=1
while [ -e $PROG.in$i ]
do
    echo
    echo ==== TESTING $PROG.in$i ====
    echo ==== YOUR STDERR ====
    case $L in
        py)
            python3 $PROG.py $2 < $PROG.in$i > $PROG.output
            ;;
        pl)
            perl $PROG.pl $2 < $PROG.in$i > $PROG.output
            ;;
        java)
            java $PROG $2 < $PROG.in$i > $PROG.output
            ;;
        *)
            ./$PROG $2 < $PROG.in$i > $PROG.output
            ;;
    esac
    echo
    echo

    echo ==== YOUR STDOUT ====
    cat $PROG.output
    echo

    echo ==== DIFF WITH EXPECTED OUTPUT ====
    diff --color $PROG.out$i $PROG.output
    if [ $? -ne 0 ] && [ -z "$2" ]
    then
        rm -f $PROG.output $PROG.class $PROG
        exit $?
    fi

    ((i++))
    echo
done

rm -f $PROG.output $PROG.class $PROG

Mercer review

Fake Binaries

I am 99% sure the following (fakebin.py) is a solution to Fake Binaries:

number = input().strip()
outputs = []
while len(number) == 0:
    number = input().strip()
while number[0] != '-':
    total = 0
    i = 1
    while True:
        fakeBin = int("{0:b}".format(i))
        if fakeBin > int(number):
            break
        total += fakeBin
        i += 1
    outputs.append(total)
    number = input().strip()
    while len(number) == 0:
        number = input().strip()
for output in outputs:
    print(output)

The output buffering is necessary only because of a quirk in Mercer's judging system that may have been fixed partway through the competition; as such, the following is probably also a solution:

number = input().strip()
while len(number) == 0:
    number = input().strip()
while number[0] != '-':
    total = 0
    i = 1
    while True:
        fakeBin = int("{0:b}".format(i))
        if fakeBin > int(number):
            break
        total += fakeBin
        i += 1
    print(total)
    number = input().strip()
    while len(number) == 0:
        number = input().strip()

The while len(number) == 0 loops are to deal with blank lines, which we were required to ignore.

Counting the delta-permutations of a string

"Delta-permutations" are actually called derangements. The total number of derangements—not considering letters that appear multiple times in the input word—can be found with the subfactorial function. The solution to this problem is described in detail by this Mathematics Stack Exchange answer.

Some interesting recent Codeforces problems

Palindromic Matrix

This problem was featured in Tuesday's Division 3 round. Consider the following palindromic matrices:

[ 1 2 3 3 2 1 4 5 6 6 5 4 7 8 9 9 8 7 7 8 9 9 8 7 4 5 6 6 5 4 1 2 3 3 2 1 ] [ 1 2 3 2 1 4 5 6 5 4 7 8 9 8 7 4 5 6 5 4 1 2 3 2 1 ]

We can see that the highlighted submatrix contains each value. The values of this submatrix are not necessarily distinct, but no two of them need to be the same. For an even n, it is easy to see that we simply need four each of (n2)2 values to fill the palindromic matrix.

For an odd n, things are slightly more complicated. We need four of every value in this submatrix, except the values in the last column and row. We need two each of these values, except for the value at the bottom right, which can be unique.

We can use a greedy algorithm to populate the submatrix with values from the "stock" of values we are given. We have to start by populating the entries whose values are repeated four times in the palindromic matrix. If we simply populate the submatrix in reading order, we may, for example, take two of the only number we have four of to populate an entry in the right column, then not have enough to populate the next entry, even though we could use a number we have only two of to populate the entry in the right column and still have the four of the other number available.

My solution (palmat.py):

from collections import Counter
import math

n = int(input())
stock = Counter(map(int, input().split()))

subn = math.floor(n/2)
use = [[0 for col in range(subn)] for row in range(subn)]

if n == 1:
    print("YES")
    print(stock.most_common(1)[0][0])
    exit()

for row in range(subn):
    for col in range(subn):
        mc = stock.most_common(1)[0]
        if(mc[1] < 4):
            print("NO")
            exit()
        stock[mc[0]] -= 4
        use[row][col] = mc[0]

if n % 2:
    for row in range(subn):
        mc = stock.most_common(1)[0]
        if(mc[1] < 2):
            print("NO")
            exit()
        stock[mc[0]] -= 2
        use[row].append(mc[0])
    use.append([])
    for col in range(subn):
        mc = stock.most_common(1)[0]
        if(mc[1] < 2):
            print("NO")
            exit()
        stock[mc[0]] -= 2
        use[subn].append(mc[0])
    mc = stock.most_common(1)[0]
    if(mc[1] < 1):
        print("NO")
        exit()
    use[subn].append(mc[0])
    subn += 1 # for printing

print("YES")

for row in range(subn):
    for col in range(subn):
        print(use[row][col], end=' ')
    for col in reversed(range(1, subn - n%2)):
        print(use[row][col], end=' ')
    print(use[row][0])
for row in reversed(range(1, subn - n%2)):
    for col in range(subn):
        print(use[row][col], end=' ')
    for col in reversed(range(1, subn - n%2)):
        print(use[row][col], end=' ')
    print(use[row][0])
for col in range(subn):
    print(use[0][col], end=' ')
for col in reversed(range(1, subn - n%2)):
    print(use[0][col], end=' ')
print(use[0][0])

Emotes

This problem appeared in Monday's Educational Codeforces round.

When first reading this problem, I thought each emote came with its own "stock" like in the above problem. But the limit is on the total emotes you use, as well as how many of any emote you use in a row. This makes the solution (1117b.cpp) quite straightforward:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    unsigned long long int n, m, k, h1, h2;
    cin >> n >> m >> k;
    h1 = h2 = 0;
    for(int i = 0; i < n; i++) {
        unsigned long long int h;
        cin >> h;
        if(h > h1) {
            h2 = h1;
            h1 = h;
        }
        else if(h > h2) {
            h2 = h;
        }
    }
    unsigned long long int maxh = 0;
    if(k == m) {
        cout << h1 * m << endl;
        return 0;
    }
    unsigned long long int happinessPerK = h1 * k + h2;
    maxh = (happinessPerK * (m/(k+1))) + (h1 * (m%(k+1)));
    cout << maxh << endl;
}

We simply use the happiest emote k times, use the next-happiest emote once to break the streak, and repeat until we have used m emotes in total. We do have to be careful not to overflow the answer maxh, since it can be up to 2×1018.

Tanya and Candies

This problem from Tuesday's Division 3 round isn't too difficult, but can be tricky to get right. We can consider each candy as an even or an odd candy. Before giving a candy to her father, Tanya eats an even candy on even days and an odd candy on odd days. After giving a candy to her father, this swaps. Adding up all the candies she eats for every case takes too long, so we can keep track partial sums for each type of candy (1118b.cpp):

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> evenUpTo = {0, 0}, oddUpTo = {0};
    for(int i = 1; i <= n; i++) {
        int ai;
        cin >> ai;
        if(i%2) {
            oddUpTo.push_back(oddUpTo.back() + ai);
            oddUpTo.push_back(oddUpTo.back());
        }
        else {
            evenUpTo.push_back(evenUpTo.back() + ai);
            evenUpTo.push_back(evenUpTo.back());
        }
    }
    int good = 0;
    for(int i = 1; i <= n; i++) {
        int evens = evenUpTo.at(i - 1) + oddUpTo.back() - oddUpTo.at(i);
        int odds = oddUpTo.at(i - 1) + evenUpTo.back() - evenUpTo.at(i);
        good += evens == odds;
    }
    cout << good << endl;
}

Water Buying

In case you are tired of thinking and want an easy problem, you can try to solve this one so you will feel like you have done something. A solution (1118a.cpp) is below, but you probably won't need it.

#include <iostream>

using namespace std;

int main() {
    int q;
    cin >> q;
    for(int i = 0; i < q; i++) {
        long long int n, a, b;
        cin >> n >> a >> b;
        if(b > 2 * a) {
            cout << a * n << endl;
        }
        else {
            cout << b * (n/2) + a * (n%2) << endl;
        }
    }
}

And a Python version (1118a.py) for your enjoyment:

q = int(input())
for i in range(q):
    nab = [int(i) for i in input().split()]
    n = nab[0]
    a = nab[1]
    b = nab[2]
    if b > 2 * a:
        print(a * n)
    else:
        print(b * (n//2) + a * (n%2))