tunyash's blog

Codeforces Round #122
By tunyash, 12 years ago, translation, In English

The upcoming contest is brought to you by me. My name is Arthur, I'm a student of Chelyabinsk lyceum 31.

I am glad to thank Gerald for contest preparation management, Delinur for translation of statements, MikeMirzayanov for a really excellent system, dolphinigle for test-solving, proof-reading and much valuable advice, fdoer, grey_wind, Skird and alger95 for help in problem development.

There is nothing more to say yet. As you can see, contest will be held in two divisions separately. The scoring system will be standard (not dynamic), but scores for tasks may be unusual (see update of this post).

There won't be volume stories. I hope you will like the contest and its problemset and everything will be OK.

UPD: Scores for tasks:

Division 1: 500-1000-2000-2000-2500

Division 2: 500-1000-1500-2000-3000

UPD2:

Congrats to winners =)

Div1:

  1. Petr
  2. tourist
  3. yeputons
  4. peter50216
  5. aram90

Div2:

  1. lucien
  2. tomasz.kociumaka
  3. sjynoi

UPD3 some part of English editoral posted. You will find the remaining part of the editorial later

UPD4 English editoral was completed.

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

Comments Comments (46)
| Write comment?
»
12 years ago, # |
  Vote: I like it -27 Vote: I do not like it

How can I register as virtual contestant?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Now you can only register as real contesant. There is no way to register out of competition.

    → Reply
»
12 years ago, # |
  Vote: I like it +87 Vote: I do not like it

Wow, dolphinigle as the tester? I would expect clear problem statements and a stable, rated round then :)

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

    I agree. He always explains everything clearly in all of his problem statements. :)

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

the contest will be interesting if the scores for tasks are unusual. And I hope the contest be rated.

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

And the score distribution is... :-?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    is ... published

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Division 1: 500-1000-2000-2000-2500

    Division 2: 500-1000-1500-2000-3000

    it is writen now.

    → Reply
»
12 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Can anyone give me a formula that can count new rating? Thanks very much. :-)

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

So what is the observation that solves B?

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

    Eliminate any sequence that contains two consecutive XOR operations.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it +4 Vote: I do not like it

      It's WA :) Sometimes you need to make only XOR operations without adding to get better result.

      tourist's test:

      Input: 1 2 1 10 20 -100 1

      Output: -1200

      Answer: -1000

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

        Yes, because of that you assume that you can't do consecutive XOR operations, BUT ALSO NOTE: after that you should also assume that the length of operations can be u, u — 2, u — 4, ... u — 2k

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

        While adding new operation if (u-operations_done%2==0) you can actualize result (later operations will be only xors).

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

      Hmm I still got a time limit even after implementing something like that.

      You need to check sequences shorter than u as well, right?

      EDIT: Aha you already answered :) thanks.

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Yes, please see the message above. Regarding to time limit, all possible sequences are about 2mln, and for each of them you need to do 30 operations, so 4s time limit should be ok.

        → Reply
»
12 years ago, # |
  Vote: I like it +32 Vote: I do not like it

Where/How do I report cheaters?

Check out this 2 guys codes for problem A:

http://codeforces.net/contest/193/submission/1756318

http://codeforces.net/contest/193/submission/1756337

Its the same code, they are both from the same country and they submitted at the same time..

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    You'd better contact either Gerald, or author of the contest, or MikeMirzayanov.

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

    Their rating graphs since mid-April 2012 don't look vastly different either. Or their avatars, for that matter. Why would someone submit exactly the same stuff from two accounts anyway?

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Maybe it is one user that has another account for testing and when he gets accepted he submits the same code with his real account. Either way it should be penalized by admins. Cheaters are never welcome.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 4   Vote: I like it -32 Vote: I do not like it

      Sorry, That accounts is mine, I always use 2 accounts to join codeforces beta round, but I am not a cheater, I don't know that, and I will use only one account to submit on next contest. Sorry, because I don't know.

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +22 Vote: I do not like it

        Can't help wondering what could be the reason for always using two accounts, if not cheating?

        → Reply
»
12 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Its only 8 minutes after the end of the contest and the system test for DIV-2 has completed 77% ... Blazing fast :)

→ Reply
»
12 years ago, # |
  Vote: I like it +36 Vote: I do not like it

Nice problemset. Hard, but fun :)

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

    Thank you =)

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Yes the contes was verry good and interesting and the there was no problems with the tasks.

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi guys, I solved problem for the first time (in 2 participation) and my rating decreased as for the time I do not solve any problem. Is it normal ? Thanks for the contest,

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

    Rating is change depend on your ranking, not from your submission :)

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

      Thanks, i just do not noticed that I effectively less ranking than the first time one.

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

Really enjoyable and challenging contest. I could've done much better, but I still had lots of fun doing it and it's all that matters. Congratulations to the organizer!

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I like the problem E in Div 2.

Any idea how to solve this equation?

  k1 * [ 0; 0; 1; 0; 1; 1 ]
+ k2 * [ 0; 1; 0; 1; 0; 1 ]
+ k3 * [ 0; 1; 1; 1; 1; 0 ]
+ k4 * [ 1; 0; 0; 1; 1; 1 ]
+ k5 * [ 1; 0; 1; 1; 0; 1 ]
+ k6 * [ 1; 1; 0; 0; 1; 1 ]
+ k7 * [ 1; 1; 1; 0; 0; 0 ]
===========================
       [ a; b; c; d; e; f ]

I thought that queue is too slow for this, but only "trick" (I do not know if it's working — if it is enough) is the one from statement — we can combine 6 combination to get [ 4; 4; 4; 4; 4; 4 ]...

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

    Although i don't think this equation related to Ediv1, Use some of method like Gauss-Jordan Elimination to solve it. After did elimination you will get 1 free variable, Bruteforce on that variable is enough to pass Ediv2 problem

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

      you are correct, it's E in div2 (C in div1), thanks for hint ;-)

      → Reply
»
12 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Great contest ... analytical problem set and clear statement ... really enjoyble .... and thtz the spirit of CodeForces ... :)

→ Reply
»
12 years ago, # |
  Vote: I like it +4 Vote: I do not like it

a really great contest. thanks for bringing such a great time to us. of course the problems were hard. :D

I hope there will be an editorial for this round too.

thanks again.

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can u explain me how to solve the problem 194B? thanks so much :)

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

    We take the square's fields as a linear sequence of 4*n fields. To simplify our calculations, we'll mark the fields starting from 0 (the bottom left corner).. all the way to 4*n — 1. In every move we will traverse n+1 fields, thus landing on the field marked as k * (n+1) mod 4*n, where k is the amount of moves we made. Now it is obvious that the solution to the problem is the smallest positive k for which k * (n+1) gives a remainder 0 when dividing with 4*n, plus 1 (because we have to count the initial cross too).

    Hope this helped.

    → Reply
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

So where is the English editoral?

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

    It's hard for me to write it, but you can see editoral for the first 3 div2 problems. Today I hope, you will see editoral of all div2 problems.

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I`m 204th coder in ranking, but my profile shows I got 206th.

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

    Two cheaters were deleted from the standings. And places wasn't updated. I'm not sure, but it looks like truth.

    → Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Why does it say "Statement is not available." when I try to access a problem statement from this contest?

→ Reply