Problem ARMY OF ME (CodeChef: Practical coding for everyone) from the January Long Challenge 2020 is the same as problem J (Russian statements https://codeforces.com/gym/101788/attachments/download/6959/statements.pdf) from this contest Dashboard - XI Открытый Кубок СПбГУ по программированию среди школьников - Codeforces
The only difference is online and offline queries.
5 Likes
I don’t think people knew about it. Look at the number of AC. Moreover removing this problem after the contest is over will not be fair. I wasted a lot of my time just to get 21 pts, instead If it were removed during contest, I could have spent that remaining time in solving the challenge problems.
You should have posted this when contest was running.
Yeah , same here, even those 21 pts took me hours to implement XD
2 Likes
21 pts was easy AF.
Just find all the subarrays having contiguous elements starting at “L” and store corresponding R’s in V[L] using
Length of the largest subarray with contiguous elements | Set 1 - GeeksforGeeks .
Now just do binary search for each L in given range for each query.
O(N*log(N)) per query.
@l_returns
Easy for you . I implemented using dp.
And it doesn’t matter, atleast it took the precious time of mine, which I could have used to solve challenge problems. If you see my profile, I was submitting till the last hour.
Those few hours saved would have given me better results in challenge problems.
1 Like
Dp was not required. 
1 Like
To be fair, in that problem, n and q <= 150,000, which is somewhat easier since O(nsqrtn) solutions can pass (and there are such solutions using Mo’s algorithm). n and q <= 500,000 in ARMYOFME which requires a O(nlogn) solution.
2 Likes
I didn’t know this approach… I solved it using recursion instead… Thanks for sharing this approach
1 Like
Even if you used dp, it could’ve been a simple bottom-up dp which preprocesses the answer for each pair.
Your code is too tough to read tho
2 Likes
I agree that it’s never pleasant when a problem turns out to be used before, but I don’t really think it was plagiarism. Honestly, if you boil down the statement to just the mathematical formulation, it is very simple and it’s very likely that more than one person has come up with it.
Additionally, with the higher constraints and online restriction here, I think the problems are not really equivalent (as mentioned, this version here is very strict on requiring an online O(N log N) approach).
With this in mind I don’t personally think that any action should be taken, but the admin has the final say on any matter.
There are thousands of competitions and probably hundreds of thousands of problems in competitive programming nowadays, so I would be very reluctant to call something plagiarism when I can see myself easily coming up with the same problem as well.
8 Likes
Because, I didn’t code it keeping in mind that anyone would read.
I did the same (except it was a top-down dp with very little modifications).
2 Likes
This author might be honest. Idk him. Idk the truth.
But now I know which type of problems should I choose if I wanna copy 
2 Likes
I agree with @enchom. The number of ACs is very low, and I think less than a half solved the problem by using those links. So the number of affecteds is negligible.
However I was a bit suspicious at the begining because the same issue happened with multiple problems of the same setter. I think it was not intentional, the setter is smart enough to know that doing that puts his reputation at stake, also CodeChef has an international community and eventually someone will point out that the problem was not original.
6 Likes
As a matter of fact there is a problem on codeforces called “good subsequences” which is exactly the same problem as this but with two changes: queries are offline and you are asked to find the number of such intervals not the longest one.
It also has an offline solution with two stacks + segtree which is what i thought of but couldnt make it online so i did brute force and took the 21
Edit: in the event that some really did get points on this via plagiarism, i would say it was pretty impactful. Like just look at the recent contests. For instance in jan20a i got every question, except for armyofme which i got 21 on. On the challenge problem i was in the late 60s/early 70s in the score and i got 95 point something in the other relative grading one. I was 3rd in the ranklist on day 4-5 but by the end i was 40ish. Now just imagine if i had solved armyofme. I would be easily in top 10. While i do not mean that i overly care for ranks etc but it still is a big deal. So i would say that even if a small number of people do this the honest ones suffer.
Edit 2: the online offline difference is a big thing though so i wont call this problem copied. I came up with the offline solution within a day yet couldnt solve online.
1 Like
I don’t believe that this was plagiarized. Searching for a contiguous set of numbers is not that creative an idea. There was a similar hard problem in March of last year: CodeChef: Practical coding for everyone.
3 Likes