Hi :)

I am sure you have recently encountered a bunch of blogs about AI cheaters (e.g., this), and you may have different feelings towards it, like anger, fear, or hopelessness. This blog is an extended version of my comment, which tried to propose some feasible, small changes that may save online CP (for now).

Changes

In short, I describe some solutions enabling a CP-skilled based competition in which using AI is allowed. These changes make problems harder for (current) AI and make the human part more prominent.

No testing results during the contest

This is not a new thing at all; in fact, this is how Topcoder used to be back in the day, and even now, COCI is like this. There is a spectrum of showing test results in contests, starting from old topcoder or COCI that show you nothing other than compilation and sample tests, to IOI or atcoder contests that show your result on each test of the whole test cases (or subtasks). Thinking of corner cases, writing generators, and debugging all by yourself is a technique that (current) LLMs are not very good at. A simple proof for this is that you have to allow them to submit 10K submissions on IOI to get gold medal but any gold medalist (or even any medalist) can write a simple generator and validator for their solutions (specially if they are as fast as a LLM in coding) and get free infinite submissions. This is a sign of how LLMs are just hacking CP as a search problem.

Not showing the limitations (or showing a part of it)

This is a bit odd and annoying. But I have been spending quite a lot of time reading LLMs chain of thoughts and comparing them to mine. I think they are not good at complexity analysis (checkout my experiences 1, 2, 3, they are a bit unrelated, but they show how poorly they perform when it comes to analyzing time complexity and validation) and if the problems don't say the limits for some (or all of the) parameters and ask the contestant to solve it with the best possible complexity (or complexities) that they can. Skilled people with AI will outperform others.

Harder problems

Back when I started CP, there were only Div 2 and Div 1, so I will talk only about them. Based on this paper, even current strong models perform awfully in Div 1 contests. They are fast and great in Div 2 or classical problems (of course with no human help), but harder problems are out of their reach (another clue of search hacking). A simple change could be to make Div 2, Div 1 and make Div 1, Div 0 (i.e., starting from Div 1 B or C). This may sound cruel to starters, but maybe with good use of AI during the contest, green coders can easily get D1A accepted during 2hrs (maybe). Also, I always hated that I couldn't have enough time to think on D1C or D1D because I was too occupied with D1A & D1B implementations; with this, people have more time to think on hard problems during contests.

New problem scoring system

I believe the codeforces scoring system is designed to award fast coders more than problem solvers. For example, in this Div 1 contest, if you solve B in the first minute without wrong attempts, you will have a higher score than a person who solves G at the last minute with a couple of wrong attempts. And because LLMs are fast, they will be better than all of us in any D2 contests. By making the scoring system like Atcoder (that the score does not decrease during the contest, but a penalty is calculated for your submissions) and even changing the scoring system to grow exponentially (not linear) as index of the problem increases, this will make sure that a person that can solve a very hard problem is always better than fast easy solvers (which (current) LLMs are now all fast easy solvers).

Rolling out

My idea is not to just change the codeforces tomorrow but to start testing these or similar small changes in unofficial contests where people are allowed to use LLMs. We see how it goes; If it is too easy or too hard, we change it. If everything goes well, everybody may have a separate rating for participating in AI-allowed contests (like Topcoder's different ratings) (and maybe people's names are displayed in two colors :D). It will be a long process through a lot of trial and fails, which I think CP deserves.

Why is change needed

Cheaters and bots are everywhere, and I won't bet on AI code detection because it's getting harder to recognize human-generated code, content, voice, art, etc, from AI-generated. After all, it is the exact thing they have been trained to be, to be like us!

From another point of view, I see using AI as a skill. If you don't think it is a skill in CP, just check this blog and see how genius people can use these tools.

Why it might work

CP is a search problem of size $$$2^{50K}$$$ (I am sure much better approximates can be made). Any code generator with infinite time is better than tourist (and transitively all of us).

Current models without chains of thoughts are only capable of solving problems that are near to their distribution, and by test time compute, they can do impressive things, but it gets exponentially harder for them to go a little bit deeper (checkout ARC-AGI). So, a simple solution would be to make the domain bigger and harder to search. It will stop them for quite some time.

I know AI is getting better and better, and trillions of dollars have been spent on it and will be spent! But as long as the human mind has any advantage over models, we should be able to make a version of CP that measures that human ability.

Regulations

I guess there should be some regulation on what AI people can use in these types of contests, but (for now) skilled people with free models do much better than non-skilled people with huge models. And cheating by spending is the best kind of cheating, because it does not scale to thousands of people.

Hi all!

I'm one of the 2020 (better to say 2021) wf participants, according to this link there are two major differences between the upcoming WF and previous WFs:

• Each team member will be provided with a computer.
• The competition is scheduled to last four hours.

Obviously the first rule results in the second rule because when teams can write codes on three computers they are faster and so time should be reduced.

But the reason mentioned in the link for the first rule is " Individual computers are provided for health safety purposes. " which looks kinda meaningless.

The reason I say that, is that all team members which participate WF on-site are fully vaccinated, multiple times PCR tested people, and if they're infected by COVID, they will spread the virus between themselves in the hotel room they have to share or all the other places they are in touch together.

The only logical reason for the first rule (in my opinion) is that it tries to synchronize two scoreboards ( ICPC World Finals Championship & ICPC World Finals Invitational which are defined in the link) which doesn't look like a fair trade off to me. And it is good to mention that it won't be a satisfying experience for two years awaiting participants if three team members are separated from each other meanwhile they have three computers. It isn't much different from online participation which was available a year ago.

Which one do you choose? to change ACM ICPC WF procedure for separation of three fully vaccinated, PCR tested people for health safety reasons or to experience a normal WF after two years of waiting?

Letter most:

For each lowercase letter count number of its occurrences in $$$s$$$, maximum of this value for all letters is the answer. All can be done in $$$O(n)$$$.

code

Array modification:

Assume  will be the maximum. it can be proven that all operation should be done in direction of $$$x$$$ ($$$j=i+1$$$ for all operation on its left and $$$j=i-1$$$ for all operations on its right).

Now consider $$$pref_x$$$ is maximum value of $$$a_x$$$ if all operations be done in direction of right for all $$$i=1, 2, ..., x$$$.

And consider $$$suf_x$$$ is maximum value of $$$a_x$$$ if all operations be done in direction of left for all $$$i=x, x+1, ..., n$$$.

It can bee seen that:

• $$$pref_x = \frac{perf_{x-1}}{2} + a_x$$$.

• $$$suf_x = \frac{suf_{x+1}}{2} + a_x$$$.

And so the answer is $$$max_{i=1}^{n}(pref_i + suf_i - a_i)$$$.

All can be done in $$$O(n)$$$.

code

Plan for nothing:

Consider an array $$$c_1, c_2, .., c_n$$$, for all intervals like $$$[l, r]$$$ do the following operation:

• $$$c_l = c_l + 1$$$.

• if $$$r \lt n$$$, $$$c_{r+1} = c_{r+1} - 1$$$.

Then consider $$$pref_i = c_1 + c_2 + ... c_i$$$. a day is good for date if and only if $$$pref_i = 0$$$.

So the answer will be minimum $$$i$$$ that $$$pref_i = 0$$$ and if it doesn't exist answer is $$$-1$$$.

code

Lonely M's array:

First reverse $$$a_1, a_2, .., a_n$$$.

Consider two following arrays:

• $$$less_i, 1 \leq i \leq 3\times 10^5$$$: maximum length of all subsequence which ends with $$$... \leq i$$$.

• $$$greater_i, 1 \leq i \leq 3\times 10^5$$$: maximum length of all subsequence which ends with $$$... \geq i$$$.

• initially both are filled with zero.

Start sweep line form $$$1$$$ to $$$n$$$:

• for each $$$a_i$$$ maximum length subsequence that ends with $$$... \leq a_i$$$ is $$$max_{j=1}^{a_i}(greater_j) + 1$$$ lets call it $$$X$$$.

• for each $$$a_i$$$ maximum length subsequence that ends with $$$... \geq a_i$$$ is $$$max_{j=1}^{a_i}(less_j) + 1$$$ lets call it $$$Y$$$.

• after calculating $$$X$$$ and $$$Y$$$, $$$less_{a_i}$$$ should be updated with $$$X$$$ and also greater_{a_i} should be updated with $$$Y$$$. The answer is $$$max_{i=1}^{3 \times 10^5}(less_i)$$$ because the subsequence should finish with $$$\leq$$$.

There are some RMQ(range maximum queries) and some single elements updates that all can be done using segment trees or fenwick trees (because queries are all either a prefix or suffix) in $$$log(3 \times 10^5)$$$.

So all can be done in $$$n \times log(3 \times 10^5)$$$.

code

Two papers I:

For an edge $$$E$$$, consider number of matchings that includes $$$E$$$. if this number is even $$$E$$$ can be ignored. So the answer is xor of all $$$E$$$'s weight which belongs to odd number of matching.

Consider the tree is rooted from vertex $$$1$$$ and: 

• $$$dpDown_{v, 0}$$$: parity of number of matchings for subtree of $$$v$$$ which using $$$v$$$ is forbidden for matchings.

• $$$dpDown_{v, 1}$$$: parity of number of matchings for subtree of $$$v$$$ which using $$$v$$$ is allowed for matchings.

Both dps can be calculated easily by a dfs from root and updating parent's dps from childs.

For an edge from $$$v$$$ to $$$par_v$$$(parent of $$$v$$$), parity of number of matching which include this edge is:

$$$dpDown_{v, 0} \times \prod_{u\ is\ par_v's\ child\ except\ v} dpDown_{u, 1} \times X$$$, that $$$X$$$ is parity of number of matchings for all vertices else subtree of $$$par_v$$$. $$$X$$$ can be calculated and passed through dfs.

So for all of edges can seen that are they in odd number of edges or even by another dfs and passing and updating $$$X$$$ through dfs arguments.

All can be done in $$$O(n)$$$.

code

Expectation:

Consider two dps:

• $$$dpCnt_{from, to, len}$$$: number of grids with two rows and $$$2^{len}$$$ columns that are colored in black and white and its first column is $$$from$$$ and its last column is $$$to$$$.

• $$$dpSum_{from, to, len}$$$: sum of number of maximal connected components of all grids with two rows and $$$2^{len}$$$ columns that are colored in black and white and its first column is $$$from$$$ and its last column is $$$to$$$.

for each $$$len$$$ its dps can be calculated by cutting it in two halfs, fix $$$from$$$ and $$$to$$$ for both halfs and it can be seen that:

• $$$dpCnt_{from , to, len} = \sum (dpCnt_{from, to_l, len-1} \times dpCnt_{from_r, to, len-1})$$$.

• $$$dpSum_{from , to, len} = \sum (dpSum_{from, to_l, len-1} \times dpCnt_{from_r, to, len-1} + dpCnt_{from, to_l, len-1} \times dpSum_{from_r, to, len-1} - X \times dpCnt_{from, to_l, len-1} \times dpCnt_{from_r, to, len-1} $$$.

• which $$$X$$$ is number of components that are unified from touching $$$to_l$$$ and $$$from_r$$$. For answer dps can be merged like described above in a way that sum their $$$2^{len}$$$s is $$$n$$$.

All can be done in $$$O(log(n))$$$.

code

Two papers II:

Consider a random spanning tree, if it has got odd number of $$$1$$$ weighted edges the answer is YES. Otherwise if there exist a cycle which contains both $$$1$$$ weighted edges and $$$0$$$ weighted edges, we can add a $$$1$$$ weighted edge to the tree and remove a $$$0$$$ weighted edge from the tree or add a $$$0$$$ weighted edge to the tree and remove a $$$1$$$ weighted edge from the tree so number of $$$1$$$ weighted edges in the tree becomes odd and answer will be YES.

And if there isn't any cycle which contains both $$$1$$$ and $$$0$$$ weighted edges the answer is NO.

For finding the cycle there should exist a biconnected component of graph which contains both $$$1$$$ and $$$0$$$ weighted edges. So by extracting biconnected components of graph and check whether do they contain both $$$1$$$ and $$$0$$$ weighted edges or not, the problem can be solved.

All can be done in $$$O(n+m)$$$.

code

Hello everyone!

I would like to invite all of you to participate in October Circuits '20. It's a coding marathon that opens at Oct 17, 15:30 UTC and runs for 7 days, closing on Oct 24, 15:30 UTC. Please make sure to check your time zones.

The problems were prepared by me. Thanks to Arpa for coordination and MhdMohammadi for testing and haas, Haghani, ... for creating tps and MikeMirzayanov for testlib.h .

Problem statements are short but they contain easy to ignore story parts, the stories are about two character named M and Y:

This coding marathon challenges you with 8 problems. You are expected to solve 7 algorithmic and 1 Approximate programing problem over a period of 7 days.

The timeline of the challenge is as follows:

• Day 0: Problem 1, Problem 2, Problem 3

• Day 1: Problem 4, Problem 5

• Day 4: Problem 6, Problem 7

• Day 6: Problem 8

• Day 7: Challenge ends

New problem statements will be published every 48 hours.

Remember, this is a rated contest and there are amazing vouchers for top three coders.

For more information, visit the contest's official web page.

UPD: There are some defects in some of tests for problems Two paper I and Expectation, I fixed tests but because of incomprehensible hackerearth admins neither me nor Arpa are not allowed to modify tests so the only way is to consider score in problem Two paper I is from 64 and in problem Expectation is from 60 (they are all correct), Sorry all.

UPD2: Editorial is published, it should be published by HacherEarth weeks ago.

Hi all!

I was trying to understand tutorial for problem C and I think I find a mistake in it.

In the third line it says Observe that flipping the direction of an odd cycle changes the sign of the permutation that is obviously wrong. for example in n = 3 and P = 2, 3, 1 when you flip the directions of edges P become 3, 1, 2 that has the same number of inversions(=2) and it can be proven that the parity of number of inversions depends only on number of cycles in permutation's graph.

I think the solution is not the way that described in tutorial because tutorial's answer for a triangle is zero but AC solutions print 2 for triangle that is correct.

Can anyone or ko_osaga explain solution or the tutorial?

thanks.

Does any body knows why SGU(acm.sgu.ru) is not working? it is about 2 days that i know!

Here are iran's team for IOI 2016 (russia) sorted by rating.

1- Ali Bahjati LiTi (last year gold medal)

2- AmirMohammad Dehghan PrinceOfPersia

3- Arash Mahmoudian Reyna

4- SeyedParsa Mirtaheri SeyedParsa

thanks.

UPD: results:

1-Ali Bahjati — Gold Medal (rank 11)

2-Arash Mahmoudian — Gold Medal (rank 13)

3-AmirMohammad Dehghan — Silver Medal (rank 31)

4-SeyedParsa Mirtaheri — Silver Medal (rank 54)

I see lots of problems about cout/cin , most of them are telling that cin/cout are slow and it's better to use scanf/printf;

but cin/cout are prettier and more easy to code for c++ coders. so i try to make an IO that it's pretty and fast.

#include <bits/stdc++.h>

using namespace std;

class FastIO{
public:
    //Output operators :
    inline FastIO & operator << (const int &a){ printf("%d" , a); return *this; }
    inline FastIO & operator << (const long long &a){ printf("%I64d" , a); return *this; }
    inline FastIO & operator << (const double &a){ printf("%.9f" , a); return *this; }
    inline FastIO & operator << (const long double &a){ printf("%.9lf" , a); return *this; }
    inline FastIO & operator << (const char * const&a){ printf("%s" , a); return *this; }
    inline FastIO & operator << (const string &a){ printf("%s" , a.c_str()); return *this; }
    //Input operators :
    inline FastIO & operator >> (int &a){ scanf("%d" , &a); return *this; }
    inline FastIO & operator >> (long long &a){ scanf("%I64d" , &a); return *this; }
    inline FastIO & operator >> (double &a){ scanf("%lf" , &a); return *this; }
    inline FastIO & operator >> (long double &a){ scanf("%lf" , &a); return *this; }
    inline FastIO & operator >> (char * const&a){ scanf("%s" , a); return *this; }
}fastIO;//you can change it to cin/cout 

int main(){
    int a;long long b;double c;
    fastIO >> a >> b >> c << a << " , " << b << " , " << c << "\n";
}

How to become strong and expert in DP ?

can any body tell me some problems and some links to read ?

thanks all!