Unfortunately, Problem C was coincidenced with a problem authored by me on Luogu (a famous Online Judge platform in China). Here is the link.
Even worse, this problem occured on a recent contest on Luogu (May 2023).
It seems that many people just copied the solution.
upd: Here is the English statement of the problem from Luogu.
You are given two integers $$$n$$$ and $$$k$$$.
Let us define the balance of a permutation $$$^\dagger$$$ $$$a$$$ of length $$$n$$$ by the following progress:
- For all $$$1\le i\le n$$$, let $$$b_i=\gcd(a_i,a_{i+1})^\ddagger$$$, specifically, we consider $$$a_{n+1}=a_1$$$;
- The balance of $$$a$$$ equals to the number of distinct intergers in the array $$$b$$$.
You have to find a permutation $$$p$$$ of length $$$n$$$, which balance is exactly $$$k$$$, or determine no such permutation exists.
$$$^\dagger$$$ A permutation of length $$$n$$$ is an array containing each integer from $$$1$$$ to $$$n$$$ exactly once. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).
$$$^\ddagger$$$ $$$\gcd(x,y)$$$ denotes the greatest common divisor (GCD) of integers $$$x$$$ and $$$y$$$.
You, of course, are shocked. You, of course, think that the round should be unrated.
You are wrong. Here's why.
Yeah, it won't be unrated, but perhaps unranted :)
The problem is generic enough to have been thought of by two people independently, I think it's just a coincidence.
I think it's just a coincidence too. But I'm really confused that, is the difficulty of B and C disordered, or a lot of people copied the solution...
I personally feel that thinking of the solution to B is much easier than C (if one is given a simple and clear statement to both problems).
But it has a pretty convoluted (and in some places misleading) statement, and the implementation involved has a lot of potential for bugs, so that might be the reason behind the skewed solve count.
yes I also think so, B was easy if the statement was given properly, but C was easy as per the Div 2 C problems of past contests.
The whole platform is in Chinese, I'd say that this particular problem is somewhat plagiarism-proof.
(Something something widely known in China...)
isnt it possible that they google translated it or maybe someone who knows chinese translated it for them? maybe idk, possibilities...
For example, I don't know English or Japanese very well but I can read problems on CodeForces and Atcoder with the help from online dictionary. The language is not the biggest difficulty, right?
yea i guess
I've added the English version of the problem. (I prepared this problem on Polygon)
Well now you've done it, I demand that at least 5 last rounds are made unrated.
(My initial point was that in order to be able to google this problem you have to know the language in the first place, if a person can search for a problem in multiple languages — good for them)
"It seems that many people just copied the solution."
how many people do you think use luogo outside China?
but there's also too many Chinese on codeforces.
Do you know how many people in China use codeforces?
Sure there are so many. Almost everyone knows and lots of people use it.
Almost everyone who studies algo in China, e.g. myself.
No. There are 1 million Chinese accounts on Luogu, but only 25000 on Codeforces.
Such as myself.
Before you attack the authors, I think this is truly a case of bad coincidence. We don't have unlimited amount of idea, and sometimes, people come up with the same idea.
EDIT: The original version is the same as the one from lougu, so I'm not so sure now.
As a tester, I originally tested the round with a harder version of C. Since testers had difficulties with that, it was changed to this easier version. If anything, this prove that the author didn't copy or even take inspiration, because why would they just replace the task with the version they copied or took inspiration from?
Hmm... What's the initial version of C? Is it the same as the one from Luogu?
After rechecking, it is the same. I had assumed that the one from luogu is exactly the same as the one in contest.
Note that this doesn't necessarily mean the author copied, since "doing max" to "doing any value <= max" is a common generalization. But I guess now it's not so clear whether the author copied or not.
imo, this problem is way too generic to appear on codeforces altogether, regardless of whether it has been copied from a recent contest or not
I can guarantee that we didn't copy, pure coincidence, sorry for that :(
Anyone who is not
retardedstupid would not copy problems, and arbuzick — the author of the problem, is almost an IOI participant and codeforces IGM, so I hope it is pretty convincing :)Lastly, hardly no one in Russia uses luogu, since even its iterface is not translated.
Tbh this version of the problem is much better as someone that knows why the sol of today's C works can solve this problem directly (while someone who guessed it can't)
"It seems that many people just copied the solution." I think we can't blame this way, the question was ..I think... typically a bit easier than other C problems of div2 ,but the B had a herculean language to be understood, so a lot of people(like me ,who usually can't solve C) shifted to C and thought over it rigorously so that we don't negative delta... another fact is , I think the approach is quite general.Maybe I am a newbie, not sure if I am suitable enough to comment here, but just expressed my opinion , since a friend of mine forwarded this blog to me
You are wrong. Here's why.
That contest was on 5,14.
also Luogu, even if it is famous in china, I don't think so it is so well known in English speaking countries like mine,I even heard of Kattis,but not Luogu
so I think,we can't blame this way right?
Um, there's a lot of primary school students studying algo in China, many of them think raising rating is a great way to show off, so they just copied LOL
So that's why you released this blog to let yourself get more rating to show off? Not everyone in China wants to show off I guess.
LOL.
It's a good contest,but I think C is really influent the rating.(
The problem is on https://www.luogu.com.cn/problem/P9345, and you can see the solution at https://www.luogu.com.cn/problem/solution/P9345.
I think many people copied the solution isn't important.What's more,it should be unrated.
Bruh as far as I know, you directly copied the solution of my problem on Luogu and gained +10 delta...
Solution
Your Code
lmao，i think it will skip,but didn't skip...bruhhhhh
Some people asking for the round unrated. Are they stupid? This scenario happened before and mike clarify the issue. Here is the blog link: https://mirror.codeforces.com/blog/entry/112709
On this blog two codeforces problems coincidence with each other.
But here codeforces problem coincidence with luogu problem.
And Umi said: The original version is the same as the one from lougu.
Round #819 Unrated due to Problem Theft.
This site can’t be reachedThe webpage at https://www.luogu.com.cn/contest/ might be temporarily down or it may have moved permanently to a new web address. ERR_TUNNEL_CONNECTION_FAILED :(
You may view https://www.luogu.com.cn/contest/list.
nope , again cant e reached
Are you chinese? I think I remember the luogu admins saying ips outside china are blocked bc ddos attacks (I am not sure, please don't blame me if I am)
im not in china , its now open — idk why but ty sir