Error_Yuan's blog

About #893 C
By Error_Yuan, 10 months ago, In English

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$$$.

  • Vote: I like it
  • +103
  • Vote: I do not like it

»
10 months ago, # |
  Vote: I like it +195 Vote: I do not like it

You, of course, are shocked. You, of course, think that the round should be unrated.

You are wrong. Here's why.

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it +37 Vote: I do not like it

    Yeah, it won't be unrated, but perhaps unranted :)

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The problem is generic enough to have been thought of by two people independently, I think it's just a coincidence.

      → Reply
      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        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...

        → Reply
        • »
          »
          »
          »
          »
          10 months ago, # ^ |
          ← Rev. 2   Vote: I like it +13 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            10 months ago, # ^ |
              Vote: I like it +5 Vote: I do not like it

            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.

            → Reply
»
10 months ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

The whole platform is in Chinese, I'd say that this particular problem is somewhat plagiarism-proof.

(Something something widely known in China...)

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    isnt it possible that they google translated it or maybe someone who knows chinese translated it for them? maybe idk, possibilities...

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it +35 Vote: I do not like it

      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?

      → Reply
  • »
    »
    10 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I've added the English version of the problem. (I prepared this problem on Polygon)

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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)

      → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

"It seems that many people just copied the solution."

how many people do you think use luogo outside China?

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    but there's also too many Chinese on codeforces.

    → Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Do you know how many people in China use codeforces?

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Sure there are so many. Almost everyone knows and lots of people use it.

      → Reply
    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      Almost everyone who studies algo in China, e.g. myself.

      → Reply
      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        No. There are 1 million Chinese accounts on Luogu, but only 25000 on Codeforces.

        → Reply
    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Such as myself.

      → Reply
»
10 months ago, # |
← Rev. 3   Vote: I like it +20 Vote: I do not like it

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?

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    Hmm... What's the initial version of C? Is it the same as the one from Luogu?

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
      ← Rev. 2   Vote: I like it +25 Vote: I do not like it

      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.

      → Reply
»
10 months ago, # |
← Rev. 3   Vote: I like it +7 Vote: I do not like it

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

→ Reply
»
10 months ago, # |
  Vote: I like it +136 Vote: I do not like it

I can guarantee that we didn't copy, pure coincidence, sorry for that :(

Anyone who is not retarded stupid 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.

→ Reply
»
10 months ago, # |
  Vote: I like it -136 Vote: I do not like it

Unrate this round!!

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

→ Reply
»
10 months ago, # |
← Rev. 5   Vote: I like it -35 Vote: I do not like it

.

→ Reply
»
10 months ago, # |
  Vote: I like it +14 Vote: I do not like it

"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

→ Reply
»
10 months ago, # |
  Vote: I like it -16 Vote: I do not like it

You are wrong. Here's why.

That contest was on 5,14.

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But there are so many Chinese on Codeforces!(like me)

    → Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it -32 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Mannnnn.... although I think there are only a few ways to solve this problem ,I don't know much actually,but it think they narrowed down the problem, again not sure about that as I'm not experienced enough

      → Reply
    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      many of them think raising rating is a great way to show off

      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.

      → Reply
    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      LOL.

      → Reply
»
10 months ago, # |
  Vote: I like it +1 Vote: I do not like it

It's a good contest,but I think C is really influent the rating.(

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
10 months ago, # |
  Vote: I like it -78 Vote: I do not like it

I think many people copied the solution isn't important.What's more,it should be unrated.

→ Reply
»
10 months ago, # |
  Vote: I like it +23 Vote: I do not like it

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://codeforces.com/blog/entry/112709

→ Reply
  • »
    »
    10 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it
    Maybe some people asking for the round unrated for this reason
    → Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 :(

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

yo

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For Luogu, Codeforces title translation is really not very good, so some questions are ambiguous, I hope Luogu administrators can pay attention to this.

→ Reply