Disclaimer: My natural English ability is questionable. I have passed the blog through chatgpt to correct grammatical mistakes.

I experimented with o1-mini and tried to understand its implications for competitive programming on Codeforces at level 2500 or higher. Obviously, the current AI cannot outright provide you with solutions; however, there are already ways it can help quite a lot.

Brute Force Writing

I believe most competitors regularly use brute-forces. They are kind of an admission of failure to find your mistakes on your own. Previously, brute-forces came with the cost of taking 5 minutes to write. I would not do it unless it is a very hard problem, or I have tried debugging by hand for 10 minutes and seen nothing. If AI usage is assumed, then these 5 minutes would be completely saved.

Five minutes would correspond to approximately a 10 performance rating if on the final problem and increasingly more on earlier problems.

Translations of Languages

This may fall under the Code-Completion tools mentioned in the rules https://mirror.codeforces.com/blog/entry/133941, so maybe it is fine.

This is really for the unfortunate people who use Kotlin like me or Python. But if we can use the tools most comfortable for us, with the one downside (speed) completely negated, that doesn't seem particularly fair.

When I am using Kotlin, I need to constantly keep in mind constant factors and risk TLE in some cases. Some time limit issues can be offset by well-optimized prewritten libraries. I personally find this to be worth it (or I would have switched long before), and these are always the trade-offs, making (to me) Python vs. Kotlin vs. C++ a mostly fair and informed decision.

Code Trimming/Rewrite

This may fall under the Code-Completion tools mentioned in the rules https://mirror.codeforces.com/blog/entry/133941, so maybe it is fine.

Basically, I ask the AI to "remove all unused functions" or "rewrite the code to be cleaner." This should have been an IDE feature, and IDEs can definitely "remove all uncalled functions." But now, AI can be much smarter and more consistent, such as "refactor this to use X instead," or if you write a simple n^2 code and ask to "optimize this using a segment tree." I don't know where the line is.

Heavy Data Structures

The AI can perform simple (simple relative to level 1900) tasks very, very fast. Current good competitive programmers can handle more complex tasks but at a moderate speed. There is one area where this mismatch is especially strong: implementing well-known data structures with slight augmentations.

There are a few data structures that are extremely flexible, but you almost never use them: red-black trees, treaps, segment tree beats, and link-cut trees. They can support many queries, but previously required (1) a working implementation that matches your coding style, and either (2A) preparing prewritten code of the exact version you need or (2B) going through your code and changing every single related spot, hoping that you don't miss anything.

Previously, option 2B was not very practical for long data structures, and option 2A was possible but limited to only a few common tasks, as there are simply too many situations to prepare for. Instead, we just don't use them, since typically they won't be the intended solution and there is a harder-to-think-of but easier-to-implement way.

With AI, however, it can generate your 100–300-line treap or red-black tree in no time, supporting any of your highly specific requests.

This is particularly relevant for competitors around the 3000 level, but for purple, orange, and red-rated participants, regular segment trees, merge sort trees, and 2D data structures all fall into this category.

Example

In 1976E - Splittable Permutations, we need to maintain an array of distinct values that supports two operations: specifying value $$$v$$$ and a new value $$$w$$$, and inserting $$$w$$$ before or after $$$v$$$.

The no-brainer option is a treap, as treaps can famously support any dynamic array with many operations. The second option is to think offline, where the operations correspond to a tree, allowing us to use an idea similar to the Kruskal-reconstruction tree. The third option, which is definitely the best, is to realize this can be handled with a basic linked list implementation. During practice, I ended up going forward with the second option.

Yet, the first option certainly requires the least thinking. I asked ChatGPT for a treap implementation supporting those queries and replaced my linked list. The solution was accepted rather easily 281351200. It was not on the first try, but it just required a quick understanding of the ChatGPT code to realize that it had written some functions with ( O(n) ) complexity and then asking it to correct the implementation.

For reference, this is my exact prompt:

Build a treap in Kotlin that maintains an array that supports the following operations: (1) Given a value in the array, insert a value after it or before it. (2) Output the current array. It can be guaranteed that the array has no duplicate values.

Note that, in particular, the AI didn't tell me I was dumb and could have used a linked list, but instead it enabled me to move forward with a very simple idea.

Additional Example

I don't have another concrete problem in mind, but consider the following tasks that have appeared many times:

• Have a usual ordered set (i.e., can add and remove elements with values up to $$$10^9$$$.
• Find the sum of the $$$k$$$-largest elements, or find the sum/max/min of elements with keys within some range $$$[l, r]$$$.

Usually, the best course of action is to (1) process the input offline and perform coordinate compression, (2) do some binary search or segment tree descend to find the two corresponding cuts, and (3) use a normal segment tree to maintain the desired information. This is a multistep process that is complicated but is the simplest using only typical prewritten libraries.

However, this is a trivial task for a custom Red-Black tree. At some point, I decided it was worth learning and implemented for myself a version of a Red-Black tree that can handle the sum variant. It took quite a while (over 4 hours), and I still haven't implemented the max version.

But now, anyone can just get an implementation—well, you should definitely have one before a contest—but my actual concern is generating this during a contest.

Conclusion

The point is that with AI, we can make use of additional data structures to their maximum flexibility, with far less knowledge required. With AI, we only need to know "what is potentially possible," and sometimes their performance in terms of constant factors, and never worry about how painful the implementation is.

I can see there is already some impact to even the high rated people.

Opinions

The rules clearly says passing subproblems is also cheating. I personally think this is definitely considered a subproblem, even if you completely provide the solution ideas, and therefore is cheating. So this was the main point of the blog: LGMs could already cheat -- not by a lot, but by some useful margins. But we should also entertain the idea that what if this is not considered cheating:

The first thought I had was, "This is disgusting; there is no way this should be allowed.".But then I realized I am not qualified to judge and make the verdict, and my current opinion is, "I don't know."

Prewritten libraries are always available, and they always provide serious tactical advantages—the cost is your preparations, and the preparations also require the same skill set, so it never trivializes anything.

This is made complicated by the following obvious logical conclusion: A generated library created before a contest must be legal.

The distinction becomes "pre-generated library" vs. "in-contest generated library." In this case, generating every single variant seems to be a sensible thing to do.

In terms of problem solving, it is absolutely clear that I did not provide every single idea to ChatGPT. I may know that a Red-Black tree can handle a maximum query, but that is not the same as knowing the exact way to maintain those parameters and the exact query functions to achieve this.

Of course, even if the act itself is okay, it may not be possible to separate it from other not-okay uses, such as asking, "What data structures could I use to support these queries?"

Further subdivision of Competitive Programming

I believe currently there are two major rulesets: prewritten code allowed ( all online competitions) and not allowed (all onsite competitions, though possibly with printed materials). For example, if Atcoder ARC and AGC continue to allow all AI tools, then that would be a different playfield compared to CF, and we should get good at yet another style of coding. I don't know what the rules would be in other (smaller) platforms.

Additional Comments

Due to the emergence of AI, we may need to properly distinguish between prewritten library and newly AI generated code. I propose the following simple rule in face of this: All prewritten library must be made public. I don't fully support this but I just add this to get the conversions going.

I have been receiving some compile error: Idleness Limit Exceeded (Process hangs) on Kotlin 1.7.

Here are a some submissions that got this verdict; 255101271, 255116970, 255117872

Sometimes, the code submit are quite long and convoluted. It is understandable if it takes too long to compile and results in CE. This would be an expected behaviour. Here are some codes that got such a verdict 254944230. 208298280. Usually, I may find myself with such verdicts if number of lines is exceeding 1000.

However, in the cases mentioned above, the code is only moderately long. Besides, they compile perfectly well in Kotlin 1.9 (e.g. one of the submissions 255102462, 255116875 , (side note: the first code will TLE on 1.9, demonstrating the need to submit it on 1.7)). Even though it is clear that shorter programmes are less likely to result in this verdict (255102439 shows one of the code managed to compile after removing unused functions), "Idleness Limit exceeded" definitely feels like something is not working right.

I am not sure if this issue had been around for some time (since the presence of kotlin 1.7) or is only here recently.

Additionally, in the case of "CE — Compilation time out", I would be able to receive the verdict within a minute or so. With the "CE idleness limit exceeded", it would take about 5 minutes to receive the verdict, which would be a serious issue during contests.

This issue is exclusive to Kotlin 1.7 on codeforces, the current 1.9 on codeforces is working totally fine.

It doesn't seem like the issue is due to particular chunks of codes, since they individually compile on 1.7.

Update: The current settings of 1.9 should run at least as fast as the previous Kotlin 1.6.

Dear codeforces and MikeMirzayanov,

Please restore Kotlin 1.6.

This issue could be serious enough to end my CP career.

The short story is that Kotlin 1.6 is the only 32-bit version. Without Kotlin 1.6 we must submit in 64bits, and in many situations this will be too slow.

As the only 32 bits version available of the language, it should not have been removed to begin with.

After using the exact language version on Round 920 (Div.3) having decent success, I found that I was unable to submit in Kotlin 1.6: It seems that Kotlin version 1.6 had been removed.

If this is a mistake, please restore it. If this is simply the result of having three languages versions being too much: You could probably remove 1.7.20, as 1.9.21 seems to be superior in every way.

The version 1.6, — more precisely, the 32 bits environment and the associated JVM settings/ versions etc.. Are critical to viability to use Kotlin on codeforces. I still find 1.6 to be consistently the fastest version, and will only use 1.7/1.9 on specific situations (e.g. during 64 bits operations). On solutions that heavily uses boxed integers i.e. MutableList (which is necessary for the most convenient solutions), Kotlin 1.6 runs two or three times faster. Even without those, the solution could still be anywhere from 20% to 50% slower.

This has been pointed out in a comment I wrote earlier, link. It had always been a serious fear of mine that codeforces would just drop Kotlin 1.6 randomly. I hope that codeforces can recognise how much differences this little bits of speed make: With 1.6, even if solutions that got TL can probably pass under a small optimisations. If 1.6 is not available, I can imagine situations where it is seriously difficult to pass an intended solution (especially when the TL was not made lenient for one reason or another), at least, without having multiple TLE penalties. An example that comes to my mind is 241859779 : my contest submission is 600ms, submission in 1.9 is 950ms, awfully close to TL.

I don't believe Kotlin 1.6 and 1.9 have the same speed: For a simple example, the solutions I submitted in the div3 round toady:

For most submissions they run in ~200ms, so the speed difference probably won't matter much as it is a constant initiation time. For the two problems that run more than that:

Problem F: 1.6, 1000ms 241743081, 1.9 , 1400ms 241859276 Problem G: 1.6, 400ms 241772417, 1.9 , 700ms 241859263

In conclusion, please restore Kotlin 1.6.

Thank you for your participation!

1734A — Select Three Sticks

We first sort the array $$$a$$$ in non-decreasing order.

Denote the indices of the elements that we choose from $$$a$$$ to be $$$x$$$, $$$y$$$, and $$$z$$$, where $$$1 \le x < y < z \le n$$$, and the final value (after performing the operations) of the concerned elements to be $$$v$$$.

The minimum required number of operations is then $$$|a_x-v|+|a_y-v|+|a_z-v|$$$. It is well-known that such expression attains its minimum value when $$$v$$$ is the median of $$$a_x$$$, $$$a_y$$$, and $$$a_z$$$. Since the array $$$a$$$ has already been sorted, it is best to assign $$$v$$$ to be $$$a_y$$$.

Our expression then becomes $$$|a_x-a_y|+|a_y-a_y|+|a_z-a_y|=(a_y-a_x)+0+(a_z-a_y)=a_z-a_x$$$. We would like to minimize the value of $$$a_z$$$, which implies $$$z$$$ should be as small as possible since $$$a$$$ is sorted. It is clear that taking $$$z=y+1$$$ would minimize the value of the expression. Similarly, we can show that we can take $$$x=y-1$$$ to minimize the value of the expression.

Therefore, the only possible values of the triplets $$$(x,y,z)$$$ are of the form $$$(t,t+1,t+2)$$$ for positive integers $$$1 \le t \le n-2$$$, and we can iterate through all such triplets and find the best one.

The time complexity is $$$\Theta(n \log n)$$$ per case due to sorting.

#include <bits/stdc++.h>
using namespace std;
void solve(){
	int n;
	cin>>n;
	int a[n+1];
	for (int i=1; i<=n; i++){
		cin>>a[i];
	}
	sort(a+1,a+n+1);
	int ans=2e9;
	for (int i=3; i<=n; i++){
		ans=min(ans,a[i]-a[i-2]);
	}
	cout<<ans<<'\n';
}
int main(){
	int t;
	cin>>t;
	for (int i=1; i<=t; i++){
		solve();
	}
}

1734B — Bright, Nice, Brilliant

Note that the brightnesses of the rooms on the $$$i$$$-th floor is at most $$$i$$$. This is because in room $$$(i,1)$$$, only $$$i$$$ rooms, namely, $$$(1,1)$$$, $$$(2,1)$$$, $$$\ldots$$$, $$$(i,1)$$$ can reach to $$$(i,1)$$$ through some number of staircases.

It is also possible to find a configuration of torches in the pyramid such that the brightnesses of the rooms on the $$$i$$$-th floor is exactly $$$i$$$, i.e. it attains the upper bound.

The configuration is as follows: Room $$$(i,j)$$$ contains a torch if and only if it is the leftmost room ($$$i=1$$$) or the rightmost room ($$$i=j$$$) on the $$$i$$$-th floor.

This is valid because for all rooms $$$(i,j)$$$, it can be reached from $$$(1,1)$$$, $$$(2,1)$$$, $$$(3,1)$$$, $$$\ldots$$$, $$$(i-j+1,1)$$$ and $$$(2,2)$$$, $$$(3,3)$$$, $$$\ldots$$$, $$$(j,j)$$$. In other words, room $$$(i,j)$$$ has brightness $$$(i-j+1)+j-1=i$$$, so the pyramid is nice.

#include <bits/stdc++.h>
using namespace std;
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                cout << (j == 1 || j == i) << ' ';
            }
            cout << '\n';
        }
    }
}

1734C — Removing Smallest Multiples

One operation should be used to remove every element not belonging to $$$T$$$.

Let $$$v$$$ be an element not belonging to $$$T$$$. Suppose a $$$x$$$-cost operation removes value $$$v$$$, then $$$v$$$ must be divisible by $$$x$$$. Furthermore, the multiples $$$x,2x,\cdots (k-1)x$$$ must have been already removed from $$$S$$$, where we write $$$v = kx$$$.

Since removed elements stay removed, the above is only possible if all of $$$x,2x,\cdots (k-1)x$$$ does not belong to $$$T$$$.

For each $$$v$$$, let $$$f(v)$$$ be the smallest integer $$$x$$$ satisfying the above condition. As we can always remove $$$v$$$ using a $$$v$$$-cost operation, $$$f(v) \leq v$$$ and in particular $$$f(v)$$$ exists.

The total cost must be at least $$$\sum_{i \not \in T} f(i)$$$. We claim that this cost can be achieved.

To do so, we should remove the required elements in ascending order. When removing $$$v$$$, we assume all $$$w \not\in T$$$ with $$$w<v$$$ have already been removed. At this state, an $$$f(v)$$$-cost operation would be able to remove $$$v$$$.

It remains to find the values $$$f(v)$$$. To do so efficiently, we can perform the above process in a bottom-up manner similar to the Sieve of Eratosthenes. Please refer to the code below for implementation details. The overall complexity is $$$n (1 +\frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n}) = \Theta(n \log n)$$$.

#include <bits/stdc++.h>
using namespace std;
void solve() {
    int n;
    cin >> n;
    bool a[n + 1];
    string str;
    cin >> str;
    for (int i = 1; i <= n; i++) {
        a[i] = (str[i - 1] == '1');
    }
    long long ans = 0;
    int cost[n + 1];
    for (int i = n; i >= 1; i--) {
        for (int j = i; j <= n; j += i) {
            if (a[j]) break;
            cost[j] = i;
        }
    }
    for (int i = 1; i <= n; i++) {
        if (!a[i]) ans += cost[i];
    }
    cout << ans << '\n';
}
int main() {
    int t;
    cin >> t;
    while (t--) solve();
}

1734D — Slime Escape

Let's call a group of slime good if their total health is at least $$$0$$$, or if defeating this group allows you to reach the exits.

We partition the slimes into good groups in a two-pointer like manner. To form the groups to the right, start from position $$$k$$$, then find the smallest position $$$r$$$ such that slimes from $$$k+1$$$ through $$$r$$$ form a good group. We do the same starting from $$$r+1$$$ again. Repeat this process until slimes to the right are partitioned into groups, which can be done by maintaining the sum of health. We partition the left slimes into groups in a similar way.

We can observe that in an optimal strategy, we may assume the player absorbs group-by-group.

For any good group, since the total health is positive, there is no drawback to absorbing a good group. In other words, whenever it is possible to absorb a good group, we will absorb it.

For each group $$$G$$$, we calculate the ``requirement'' of the group — the lowest health we can begin with, such that we can absorb the group while maintaining non-negative health at all times. The requirement of a group of slime with health $$$a_1,a_2 \cdots a_n$$$ can be expressed as

Finally, we can simply simulate the process. We repeatedly attempt to absorb good groups to the left or to the right. We keep track of the current health, initially equal to $$$a_k$$$. Whenever we consider whether to absorb a group or not, we absorb it if and only if the current health is at least as high as its requirement. Otherwise, we ignore it for now and attempt to do so for the group on the other side. If it is possible to reach a state where either all left groups or all right groups are absorbed, then we can win the game. If at some point, it is not possible to absorb the left group nor the right group, then we lose.

The overall complexity is $$$\Theta(n)$$$.

It is also possible to use a range $$$\max$$$/$$$\min$$$ segment tree form the groups instead of using two-pointers, in which case its complexity would be $$$\Theta(n \log n)$$$.

#include <bits/stdc++.h>
using namespace std;
void solve() {
    long long n, k, P;
    cin >> n >> k;
    k--;
    long long L[n];
    for (int i = 0; i < n; i++) cin >> L[i];
    P = L[k];
    L[k] = 0;
    long long ps[n + 1];
    ps[0] = 0;
    for (int i = 1; i <= n; i++) ps[i] = ps[i - 1] + L[i - 1];
    int l = k, r = k + 1;
    vector<pair<long long, long long> > LG, RG;
    for (int i = k - 1; i >= 0; i--) {
        if (ps[i] <= ps[l] || i == 0) {
            long long worst = 0, cur = 0;
            for (int j = l - 1; j >= i; j--) {
                cur += L[j];
                worst = min(worst, cur);
            }
            LG.push_back({cur, -worst});
            l = i;
        }
    }
    for (int i = k + 2; i <= n; i++) {
        if (ps[i] >= ps[r] || i == n) {
            long long worst = 0, cur = 0;
            for (int j = r; j <= i - 1; j++) {
                cur += L[j];
                worst = min(worst, cur);
            }
            RG.push_back({cur, -worst});
            r = i;
        }
    }
    reverse(LG.begin(), LG.end());
    reverse(RG.begin(), RG.end());
    long long curp = P;
    while (true) {
        bool acted = false;
        if (!LG.empty() && curp >= LG.back().second) {
            curp += LG.back().first;
            LG.pop_back();
            acted = true;
        }
        if (!RG.empty() && curp >= RG.back().second) {
            curp += RG.back().first;
            RG.pop_back();
            acted = true;
        }
        if (LG.empty() || RG.empty()) {
            cout << "YES\n";
            return;
        }
        if (!acted) {
            cout << "NO\n";
            return;
        }
    }
}
int main() {
    int t;
    cin >> t;
    while (t--) solve();
}

1734E — Rectangular Congruences

We say a matrix to be good if it satisfies the congruence condition (the second condition).

When we have a good matrix, we can add any value $$$c$$$ to a whole row while maintaining the congruence relation. The same is true for adding the same value to a whole column.

Suppose we have any good matrix $$$A$$$, then by adding $$$b_i - a_{i,i}$$$ to the $$$i$$$-th row for each of $$$i=1,2,\cdots,n$$$, we obtain a good matrix that has the desired values on the diagonal.

In fact, there are a lot of possible constructions. We present a few of them here:

• $$$a_{i,j} = i \times j \pmod n$$$

• $$$a_{i,j} = (i + j)^2 \pmod n$$$. This needs special handling when $$$n=2$$$.

• $$$a_{i,j} = \frac{(i+j)(i+j+1)}{2} \pmod n$$$.

• The coolest part is that all quadratic polynomials in the form $$$ai^2 + bij + cj^2 + di + ej + f$$$ are valid for all integers $$$a,b,c,d,e,f$$$ and $$$b \not\equiv 0 \pmod n$$$

As a bonus, we prove that the general quadratic polynomial gives a good construction.

Here are some extra observations that may enable one to find a good matrix more quickly.

#include <bits/stdc++.h>
using namespace std;

int want[355];
int board[355][355];
int main() {
    int n;
    cin >> n;
    for(int i = 0; i < n ; i ++){
        cin >> want[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            board[i][j] = (i * j) % n;
        }
    }
    for(int i = 0; i < n; i ++){
        int extra = (want[i] + n - board[i][i] )% n ;
        for (int j = 0; j < n; j++) {
            board[i][j] += extra;
            board[i][j] %= n;
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << board[i][j] << ' ';
        }
        cout << endl;
    }
}

1734F — Zeros and Ones

Observe that the $$$i$$$-th character is `1' if and only if $$$i$$$ has an odd number of set bits in its binary representation. Both solutions make use of this fact.

The constraints allows solutions of up to $$$\Theta(q \log^3 n)$$$. Yet, both of the model solution runs in $$$\Theta(\log n)$$$.

1. Digit DP solution

The question can be reformulated as follows: How many integers $$$x$$$ between $$$0$$$ and $$$m-1$$$ inclusive have the property that the total number of set bits of $$$x$$$ and $$$x+n$$$ is an odd number?

This can be solved with digit DP. We process the bit position from $$$\lceil \log(\max) \rceil$$$ down to $$$0$$$. We maintain three states:

• $$$\text{ans}$$$, a boolean value;

• $$$\text{trailzeros}$$$, an integer between $$$0$$$ and $$$\lceil \log(\max) \rceil$$$ inclusive; and

• $$$\text{under}$$$, a boolean value.

We can thus conclude the following: the number of trailing zeros is all we need to decide the answer.

After processing each bit $$$k$$$, we should have the following: the number of integers $$$x$$$ between $$$0$$$ and $$$\lfloor \frac{m}{2^k} \rfloor$$$ inclusive which have the following property:

• the total number of set bits of $$$x$$$ and $$$x + \lfloor \frac{n}{2^k} \rfloor$$$ is equal to $$$\text{ans} \mod 2$$$;

• the number of trailing `1's of $$$x + \lfloor \frac{n}{2^k} \rfloor$$$ is equal to $$$\text{trailzeros}$$$;

• the boolean value $$$[x < \lfloor \frac{m}{2^k} \rfloor]$$$ (where $$$[]$$$ is the Iverson bracket).

Now onto the transitions. Suppose we are adding the $$$(k-1)$$$-th digit, and let $$$d$$$ be the new digit of $$$x$$$, and $$$z$$$ be the $$$(k-1)$$$-th digit of $$$n$$$.

• If $$$z+d = 0$$$, then $$$(\text{ans},\text{trailzeros})$$$ after digit $$$k$$$ will be transited to $$$(\text{ans},0)$$$ after digit $$$k-1$$$;

• if $$$z+d = 1$$$, then $$$(\text{ans},\text{trailzeros})$$$ after digit $$$k$$$ will be transited to $$$((\text{ans} + z +d) \mod 2, \text{trailzeros}+1)$$$ after digit $$$k-1$$$;

• if $$$z+d =2$$$, then $$$(\text{ans},\text{trailzeros})$$$ after digit $$$k$$$ will be transited to $$$((\text{ans} + z + \text{trail} + 1) \mod 2, 0)$$$ after digit $$$k-1$$$

The final answer is the total number of values for which $$$\text{ans} =1 $$$ and $$$\text{under} = 1$$$.

The above solution runs in $$$\Theta(\log^2 (\max))$$$ per query. There is a simple way to optimize this to $$$\Theta(\log(\max))$$$: note that we only need to keep parity of $$$\text{trailzero}$$$.

There are many other digit DP approaches that give similar time complexity. The constraints should allow most of them pass.

val Boolean.chi:Int get() = if(this) 1 else 0 //characteristic function
fun Int.has(i:Int):Boolean = (this and (1 shl i) != 0)
fun Long.has(i:Int):Boolean = (this and (1L shl i) != 0L)
fun main(){
    repeat(readLine()!!.toInt()){

        val (n,m) = (readLine()!!.split(" ").map { it.toLong() })
        var DP = Array(2){Array(2){LongArray(64)}}

        DP[0][0][0] = 1

        for(bit in 60 downTo 0 ){
            var new = Array(2){Array(2){LongArray(64)}}
            for(under in 0 until 2){
                for(ans in 0 until 2){
                    for(nd in 0 until 2){
                        if(under == 0 && nd == 1 && !m.has(bit)) continue
                        val nunder = ((under == 1) || (nd == 0 && m.has(bit))).chi


                        val np = nd + n.has(bit).chi

                        for(trail in 0 until 62){
                            var nans = ans
                            if(nd == 1){
                                nans = 1 - nans
                            }
                            var newtrail:Int

                            if(np == 0){
                                newtrail = 0
                            }else if(np == 1){
                                nans = 1 - nans
                                newtrail = trail + 1
                            }else if(np == 2){
                                nans = (nans + trail + 1) %2
                                newtrail = 0
                            }else{
                                error("oh no")
                            }

                            new[nunder][nans][newtrail] += DP[under][ans][trail]
                        }
                    }
                }
            }
            DP = new
        }


        var ret = 0L
        for(trail in 0 until 64){
            ret += DP[1][1][trail]
        }
        println(ret)

    }
}

2. Recursive Solution, by darkkcyan

Define the function $$$f(x) := $$$ the parity of bit one in the number $$$x$$$.

We have thus reworded the statement into evaluating the follow expression:

The formula can be further transformed as:

since $$$\left[ f(a) \ne f(b) \right] = f(a \oplus b)$$$ holds true for all non-negative integers $$$a$$$ and $$$b$$$.

Imagine we construct a grid and assign the value at row $$$r$$$ and column $$$c$$$ to be $$$f(r \oplus c)$$$. Then, $$$T$$$ is sum of a diagonal of length $$$k$$$ which starts at either $$$(0, n)$$$ or $$$(n, 0)$$$. Without loss of generality, we use $$$(0, n)$$$ in this editorial.

The grid can be constructed similarly to the way we construct the string $$$S$$$. We start with a $$$1$$$-by-$$$1$$$ matrix $$$M_0=\begin{bmatrix} 0 \end{bmatrix}$$$.

Then, the matrix $$$M_i$$$ of size $$$2^i \times 2^i$$$ can be constructed as follows:

where $$$\overline{M_{i - 1}}$$$ is the matrix $$$M_{i - 1}$$$ but with flipped bits.

Here is another way of constructing the grid: let $$$C_i$$$ be an infinite chess board with alternating colors, similar to a regular chess board, but with each of the cells being size $$$2^i \times 2^i$$$. For example, $$$C_0$$$, $$$C_1$$$ and $$$C_2$$$ in an $$$8$$$-by-$$$8$$$ grid is as follows:

.*.*.*.*
*.*.*.*.
.*.*.*.*
*.*.*.*.
.*.*.*.*
*.*.*.*.
.*.*.*.*
*.*.*.*.


..**..**
..**..**
**..**..
**..**..
..**..**
..**..**
**..**..
**..**..


....****
....****
....****
....****
****....
****....
****....
****....

We claim that our grid is the $$$\text{xor}$$$ of all chess board $$$C_i$$$. The proof is easy: $$$C_i$$$ is constructed by $$$\text{xor}$$$-ing the $$$i$$$-th bit of the the row and column number.

We are therefore motivated to proceed in the following way: if we drop the least significant bit (by making it to be $$$0$$$), we are still solving a very similar problem to the original problem, because dropping the first bit is similar to removing $$$C_0$$$. And when we shift $$$C_i$$$ to $$$C_{i - 1}$$$, it is a recursion of the same problem!

Going back to the problem, where we are computing sum of a diagonal of length $$$k$$$. If $$$k$$$ is odd, we can make it odd by adding the last element to the result and decreasing $$$k$$$ by one. Now, $$$k$$$ is even, and we can utilize the recurrence as follows:

• remove $$$C_0$$$.

• scale the board down by 2 (including $$$n$$$ and $$$k$$$). By doing so, $$$C_i$$$ becomes $$$C_{i - 1}$$$.

• solve the new problem.

• scale the board up again and add $$$C_0$$$ back.

• from the result of the scaled down problem, some how calculate the result of the original problem

The result of the scaled down problem is the number of $$$2$$$-by-$$$2$$$ cells with value $$$1$$$. From the number of $$$2$$$-by-$$$2$$$ cells with value $$$1$$$, we compute the number of cells with value $$$0$$$ as well. It is not hard to observe that it crosses the $$$2$$$-by-$$$2$$$ cells at all places. The only thing that matters is the parity of $$$n$$$.

• If $$$n$$$ is even, then the diagonal crosses the diagonal of the $$$2$$$-by-$$$2$$$ cells. In the scaled-down version, the diagonal is still a single diagonal starting at $$$(0, \frac{n}{2})$$$; otherwise,

• if $$$n$$$ is odd, it crosses the corner of the $$$2$$$-by-$$$2$$$ cells. In the scaled-down version, the diagonal is actually $$$2$$$ neighboring diagonals starting at $$$(0, \frac{n-1}{2})$$$ and $$$(0, \frac{n+1}{2})$$$.

Also, the $$$2$$$-by-$$$2$$$ cells with values $$$0$$$ and $$$1$$$ respectively will also have the form:

.*    *.
*.    .*

From here we have everything we need to compute the result of the original problem.

Overall, the number of states we have to visit is $$$\Theta(\log k)$$$.

import random

cache = {}

def popcount(n):
    res = 0
    while n:
        res += 1
        n &= n - 1
    return res

def solve(n, k):
    if k == 0:
        return 0
    if k == 1:
        return popcount(n) & 1
    if k % 2 == 1:
        t = solve(n, k - 1)
        x = popcount((k - 1) ^ (n + k - 1)) & 1
        # print(t, x)
        return t + x
    if (n, k) in cache:
        return cache[(n, k)]
    if n % 2 == 0:
        one_cell = 2
        zero_cell = 0
        cnt1 = solve(n // 2, k // 2)
        cnt0 = k // 2 - cnt1
    else:
        one_cell = 0
        zero_cell = 1
        cnt1 = solve(n // 2, k // 2) + solve(n // 2 + 1, k // 2)
        cnt0 = k - cnt1
    res = one_cell * cnt1 + zero_cell * cnt0
    # print(f"n = {n}, k = {k}, cnt1 = {cnt1}, cnt0 = {cnt0}, one_cell = {one_cell}, zero_cell = {zero_cell}")
    cache[(n, k)] = res
    return res

t = int(input())
for _ in range(t):
    cache.clear()
    n, k = map(int, input().split())
    print(solve(n, k))

UPD: The round has been rescheduled to a different time due to a clash with a CodeChef contest

Hello CodeForces!

Me, AHappyPotato and __jk__ are excited to invite you to participate in Codeforces Round 822 (Div. 2). It will start at 23.09.2022 15:05 (Московское время). The round will be rated for everyone with less than 2100 rating. You have 2 hours to solve 6 problems. Please note the unusual start time.

We would like to take this opportunity to thank everyone who have contributed to our round:

• darkkcyan for his excellent coordination;
• anthony123 and jerryliuhkg for proposing tasks that did not make it to the final problemset;
• thenymphsofdelphi, kevinxiehk, xuanquang1999, vinfat, ACGN, Mike4235, brianlee.lck, JeffreyLC, prvocislo, ITO, snowysecret marvinthang, QuangBuiCPP, Rekaxem, Alan, sharkycode and OGname, for testing and providing invaluable advice;
• KAN for translating the problem statements into Russian;
• MikeMirzayanov for the marvellous CodeForces and Polygon platforms; and finally,
• You, for participating in this contest!

We look forward to seeing you on the leaderboard!

UPD: Score Distribution: 500 — 750 — 1250 — 2000 — 2250 — 3250

UPD2: Editorial

UPD3: Winners!

Div 1 + 2:

1. GOI_Official
2. Um_nik
3. tzc___________________wk
4. Second_Brave_Niuniu
5. hitonanode

Official:

1. GOI_Official
2. tzc___________________wk
3. Second_Brave_Niuniu
4. Sand_Emperor
5. steven14414

I am searching through the problems for a specific tag. I want them to be sorted by problem number. A day or so earlier, they are indeed nicely sorted by problem number. Right now it doesn't seem to be sorted. Is this a bug or intended change? If so please consider adding the feature to sort by problem number.

Here is page 10 of constructive algorithms retrieved as I wrote this. Link Filter by Constructive Algorithim

Not all tags are affected. For example, the divide and conquer tag is sorted. This is also how I expect it to work.

This is an important feature: I plan to do only early problems with tags shown and save recent problems for virtual contests.

EDIT: I got so annoyed by this that I just wrote my script and use codeforces API instead... Script

Hi! I am relatively new to competitive programming , taken parts in GCJ for 2 years (with Swift). I am certainly new to CodeForces.

I want to use Swift for solving problems on CodeForces, and I am slightly surprised that this isn't an option. If I were to guess, I would say maintaining another language could be costly. But searching through other blogposts (Say https://mirror.codeforces.com/blog/entry/72941, https://mirror.codeforces.com/blog/entry/52225, https://mirror.codeforces.com/blog/entry/67751), it looks like it just wasn't discussed seriously. Also, I couldn't find any general guidelines for suggesting a new language, so it looks like it was just never discussed seriously.

In view of this, I wish to make a feature request about if it is possible to include Swift (Swift 5.1 by Apple) as a language for codeForces.

I will go through some reasons why it is very reasonable to use Swift for CP.

1) Main Reason: It is a Developed modern language that is decently popular

Swift is a modern language, that has been out since 2014. Basic Object oriented, try/catch features exists. Swift also does a lot of modern features quite well: First class functions, Generics, strong inferred typing.

Swift is consistently within the top 10 most popular language, whichever source I find.

2) Reason for CP: Very clean syntax

Unlike the the Apple predecessor Objective-C , which is very archaic and clunky in its syntax. The whole Swift is built from ground up keeping clean syntax in mind. Clean syntax is one of the promise of the Swift language. A few things that worth mentioning:

• No ; , () , and "return" whenever unambiguous
• Inferred typing, but still type safe
• The syntactic sugar of optionals (? and ! operators, guard statement in Swift)
• Many shorthands for closures (Pure functions in some languages): Any of these can be used for sorting: {a,b in return a<b},{return $0 < $1} , {$0 < $1} ,<, and of course .sorted() if it is a standard type.

And some very versatile features that is helpful for large projects, but are conceivable to develop a CP framework out of: Generics, and Protocol with associated types And latest features in Swift 5: Functional builder and property wrappers

Certainly some of these features will be present in some other languages. I don't know about all languages, I am only certain these are not in Python, for example.

The point is not that all these can be reasonably applied in CP, rather, that this set of tools is adapted to some CP tasks, so this option should exist.

3) The language isn't slow, it is still a statically typed compiled language after all.

4) Also , not a good reason by itself but still worth mentioning: Google Code Jam has Swift as an option.

I will admit, I like using Swift because I come from industry programming, and a large portion of popularity is due to it being the native language for Apple developments. However, I firmly believe that as explained above, it is a very serious language that is competitively viable.

Therefore, I wholeheartedly wish that I can use Swift for CodeForces. I hope this can be considered seriously.