goryinyich's blog

Codeforces Beta Round #78
By goryinyich, 13 years ago, translation, In English
Hi there!

Me - Sergey Vedernikov - is the author of today's CF beta round.

During the round you'll assist far away kingdom citizens in solving everyday problems, and sometimes - just to fight for your survival.
This round is "red" =), therefore the problems should not appear too difficult, and you should get pleasure from solving them.
To those who know Russian language I recommend to read problem statements in Russian. Not because of the quality of translation - English just poorly communicates Russian folklore language style.

Finally I want to thank Artem Rakhov for invaluable help during the round preparation, Maria Belova for the qualitative translation of the problems, Mikhail Mirzayanov for excellent CF system and all participants for not leaving this event without your attention.

More AC verdicts and high rating to all of you! gl & hf

UPD: Unfortunately, problem B (div. 1) / D (div. 2) appeared to be more difficult, and author's solution appeared wrong. The round will be unrated. I apologise for this to all participants.
  • Vote: I like it
  • +42
  • Vote: I do not like it

Comments Comments (117)
| Write comment?
13 years ago, # |
  Vote: I like it +6 Vote: I do not like it
What do you mean by "This round is red" ? 

Nice rating by the way ;)
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it
    This was joke for you to remember "first violet round" =)
    → Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it +15 Vote: I do not like it

    "This round is red" (literally) means that this round is made by red CF user. There is a difference between 'red' and 'orange' rounds. (by the way, 'violet' round was not so 'violet' because of anonymous help :) ).
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it
    Red round
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it -10 Vote: I do not like it
      Red standing.
      yellow, black , blue fallen down.
      Red staring at yellow :-o
      Nice :-D
      → Reply
    • 13 years ago, # ^ |
      ← Rev. 4   Vote: I like it +5 Vote: I do not like it

      Попробовал в Google+ написать сообщение в блог.
      Так вот, при добавлении ссылки на этот пост умный Гугл выбирает заодно и картинку выше.

      (в предыдущей правке скрин, но более подходящее ему место в этой теме: http://codeforces.me/blog/entry/2278)
      → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Problems sound easy... :D 
→ Reply
13 years ago, # |
  Vote: I like it -11 Vote: I do not like it
GOOD LUCK!!!!!!!!!
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
How is red round correlated to easy problem set? Isn't it the other way? Am I missing something here?
→ Reply
13 years ago, # |
← Rev. 2   Vote: I like it -12 Vote: I do not like it
good luck everyone :D
→ Reply
13 years ago, # |
  Vote: I like it -12 Vote: I do not like it
thanks a lot. high ratings to all :)
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I am new to codeforces...I have'nt seen the contest interface..Can anyone guide me ..Also I am using Java..So some technical help would also be great...
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    Use Arrays.sort!  

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

      So you can swap some random elements and everything will be OK.
      → Reply
      • 13 years ago, # ^ |
        ← Rev. 2   Vote: I like it -14 Vote: I do not like it

        Once I've tried to make a 'Pifia' in one AI challenge. The sense was to predict Java environment random generation due to known calls to random generator. I've failed because of a bug in challenge API, but sometimes random prediction is possible :)
        → Reply
13 years ago, # |
  Vote: I like it +4 Vote: I do not like it
Good luck everybody.
Thanks to the problem setters for their contribution

→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Any idea for problem C div II?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    My solution was to try every combination, ignoring the rotation constraint, and save them in a array. Then I took every combination in the array and make all the rotations from it and erase these rotations from the list, the answer was the number of solutions left in the array.
    → Reply
13 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Do anybody know pretest 6 of problem B (Div 1)?
→ Reply
13 years ago, # |
  Vote: I like it +18 Vote: I do not like it
Now I know what a RED round means.
→ Reply
13 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

This round probably has the most number of unsuccessful attempts (in DIV 1).
Looking forward to the tutorial :P.
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Nice problemset - I've solved only E and placed 22nd (hope it won;'t change after system tests).
→ Reply
13 years ago, # |
  Vote: I like it +7 Vote: I do not like it
I think that problems were difficult because of the some (hard to understand) sentences...
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
in A was there any pretest in which integer part ended with 9? i forgot to check out solutions in hacking phase.
i doubt there was not such case , so many solutions will fail.
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Div2 C: 
Can we use a brute force approach?
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    Yes you can, try out all the permutations (which is at most 6!).

    → Reply
  • 13 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    yes, brute force works:
    there are 720 permutations of 6 colors, and 24 equivalent positions for a cube.
    It would therefore need 720*24 checks.  It's low.
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      can you explain the 24 positions.
      How do i figure it out.
      Thanks for the help.
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it
        bottom - 1 from 6.
        front - 1 from 4 which have the same bottom.
        → Reply
      • 13 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it
        1 identical transformation
        9 rotations around 3 lines connecting the opposite faces (by 90 degrees)
        6 rotations around 6 lines connecting the opposite edges (by 180 degrees)
        8 rotations around 4 lines connecting the opposite vertices (by 120 degrees)
        → Reply
      • 13 years ago, # ^ |
        ← Rev. 3   Vote: I like it +5 Vote: I do not like it


        It's a group isomorphic to S4.

        A rotation of the cube corresponds to a permutation of the four diagonals.

        → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Thanks guys for the help.
        it sounds a little too difficult for me.<I know very little of this isomorphism>
        I did 720 permutation but lost track how to do the rotations <24>.
        can anyone give me some links where I can get these 24 positions or how can i do it?

        Thanks for your help again.
        → Reply
        • 13 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          Actually you can use the stupid approach: Just brute force over the 4x4x4 ways to spin the dice in the X, Y, and Z axis.

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

    24 step :
    0,0,0,1,0,0,0,1,0,0,0,1,2,0,0,0,1,0,0,0,1,0,0,0
    ---------------------------------------------------
    0:
             +---+
         | 5 |
     +---+---+---+---+
     | 3 | 0 | 1 | 2 | ----->
     +---+---+---+---+
         | 4 |
         +---+
             +---+
         | 1 |
     +---+---+---+---+
     | 5 | 0 | 4 | 2 | 
     +---+---+---+---+
         | 3 |
         +---+
    1:
             +---+
         | 5 |
     +---+---+---+---+
     | 3 | 0 | 1 | 2 | ----->
     +---+---+---+---+
         | 4 |
         +---+
             +---+
         | 5 |
     +---+---+---+---+
     | 0 | 1 | 2 | 3 | 
     +---+---+---+---+
         | 4 |
         +---+
    2:
             +---+
         | 5 |
     +---+---+---+---+
     | 3 | 0 | 1 | 2 | ----->
     +---+---+---+---+
         | 4 |
         +---+
             +---+
         | 1 |
     +---+---+---+---+
     | 4 | 2 | 5 | 0 | 
     +---+---+---+---+
         | 3 |
         +---+

    → Reply
13 years ago, # |
  Vote: I like it +18 Vote: I do not like it
Nice problems - however, I don't think it was balanced.
Number of submissions that passed the pretest are {A:218, B:20, C:29, D:21 and E:27}. 
 - Big gap between A and others.
 - (B C D E) very close to each other.

For problem B, i think the example cases were too trivial.
→ Reply
13 years ago, # |
  Vote: I like it +9 Vote: I do not like it
Annoying problem statements. My B (div2) is going to fail because I failed to grasp the peculiarity of the statement till I locked my solution and checked another coder's solution.

Problems overall were nice, though tough. 
→ Reply
13 years ago, # |
  Vote: I like it +10 Vote: I do not like it
I suggest that this contest is unrated.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it
    Why?
    → Reply
    • 13 years ago, # ^ |
      ← Rev. 3   Vote: I like it +14 Vote: I do not like it

      We suppose that the jury's solution for B (Div. 1) is incorrect, and this problem doesn't have a correct solution for n ~ 1017.
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        any details?
        → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        What do you mean by "doesn't have a correct solution for n ~ 1017" ?
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          The answer can be quite long ;)
          → Reply
        • 13 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          Probably the answer will contain too many digits. I'm not sure, I haven't investigated the situation carefully. Some participants wrote something about it in russian comments. In any case, the problem is much more difficult than it was supposed to be.
          → Reply
          • 13 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it
            So, the question to the author. Will you reduce the constraints so that the solution is possible to print, and explain it in editorial?
            → Reply
      • 13 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it
        even Petr didn't try this problem at all (didn't submit)
        → Reply
        • 13 years ago, # ^ |
            Vote: I like it +20 Vote: I do not like it
          Clever guy Petr, huh? :)
          → Reply
          • 13 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it
            How did Petr know it ....Petr is the god in my heart 4ever!
            → Reply
            • 13 years ago, # ^ |
                Vote: I like it +9 Vote: I do not like it
              I believe it's simpler than what you guys think, he just couldn't find a correct solution :)
              → Reply
              • 13 years ago, # ^ |
                  Vote: I like it +14 Vote: I do not like it
                Petr is so cool that he always knows which problems have wrong jury solution
                → Reply
13 years ago, # |
  Vote: I like it +6 Vote: I do not like it
Div-2 B
I was able to hack a solution just because the participant didn't put '.' after 
Unrecoverable configuration


→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    all praise to your keen eyes.
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it
    Why wasn't there a pretest for this?
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it
      Because it would create an unrecoverable configuration =)
      → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Uhm... When I wrote my B (div2) I made a copy-paste error: my solution never printed "Unrecoverable.." but printed always "Excellent pages" instead. I sent it, and failed on pretests! Then I corrected it and got it accepted.

      How is it possible?
      → Reply
    • 13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      actually the participant had checked for "Unrecoverable Configuration." at 2 places. At one he forgot to put '.' :)

      → Reply
13 years ago, # |
  Vote: I like it +10 Vote: I do not like it
That was a hard and unballanced round. Also, I missed the usual explanation of the sample cases in some problems in Div 1, mainly B and E...
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
oh, no..........
→ Reply
13 years ago, # |
  Vote: I like it +13 Vote: I do not like it
I really enjoyed the contest. Perhaps a good warm-up (if not overheat) before tomorrow's TCO.

I will be really really really looking forward to E's editorial.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    enjoyed the contest, yes, but it's unrated :(
    anyway good luck for tomorrow's TCO then :D
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Can we expect CodeForces rounds authored by you soon?
    Your TopCoder contests were cool and Hard problems were as tough as today's problemset if not more ^_^
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +30 Vote: I do not like it
      Thank you! I'm very happy to hear that.

      I've asked to but haven't got any reply until now. Maybe they already have too many authors - or maybe they simply missed my email. In either case you have the answer.
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it +29 Vote: I do not like it
        I don't know what happened with your email, but will be really great to see your round on Codeforces. I'll ask RAD to ping you about it. Thank you.
        → Reply
    • 13 years ago, # ^ |
        Vote: I like it +12 Vote: I do not like it
      Agree with caustique, dolphinigle's contests are awesome.
      In fact, he is our favorite in Indonesia :D
      → Reply
13 years ago, # |
  Vote: I like it +21 Vote: I do not like it
After 13 days waiting for this contest. to be unrated! :(
→ Reply
13 years ago, # |
  Vote: I like it +18 Vote: I do not like it
Hmm.....unrated..It makes me sad ;(
By the way , I couldn't get pleasure from solving these because it seemed that problems are very difficult except for A!

I think that recent contests are becoming difficult than the contests of the past clearly.
→ Reply
13 years ago, # |
  Vote: I like it +5 Vote: I do not like it
My contest performance was very bad.Cannot solve problem C. But who cares the contest is unrated so I m feeling lucky...................

→ Reply
13 years ago, # |
  Vote: I like it +8 Vote: I do not like it
Why interval between contests have increased? We would love to have 2 contests in a week,at least 1.
→ Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it +13 Vote: I do not like it

     Having not enough nice problems for the contest.
    → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    2 contests in a week would be nice.
    shorter problem description with no translation error would be nicer.
    good & balanced problem set will be even better.

    I look forward to it.
    → Reply
13 years ago, # |
  Vote: I like it +1 Vote: I do not like it
In B (Div1)/D (Div2), how to proof that a given strategy is an optimal one ?
→ Reply
13 years ago, # |
  Vote: I like it +6 Vote: I do not like it
I don't know if I'm missing something, but if the author solution for the "B div1/D div2" was wrong. How did 21 coder manage to get it accepted ?!!
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it
    They have the same wrong solution...
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it
      So, they had the same wrong thoughts, and made the same mistakes as the problem setter ?!
      → Reply
13 years ago, # |
  Vote: I like it +7 Vote: I do not like it
This contest supposed to be rearranged as like as SRM504.5
→ Reply
13 years ago, # |
← Rev. 3   Vote: I like it -13 Vote: I do not like it

Can this contest be rerated with the ignorance of AC solutions in B (Div1)/D (Div2)?

I think it's better than unrated....
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it
    What with people who spent time on problem B/D?
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it
      I spent time on B, but I wish the contest to be rated :D
      → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
I think it's better to rematch in few days.
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    Waiting for Codeforces Beta Round #78.5 :)
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Any editorials coming soon??? or not? :(
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
This was my first contest and goes of unrated....disappoiting:(
→ Reply
13 years ago, # |
  Vote: I like it -16 Vote: I do not like it
Now I know the meaning of "red"
for me "red" means hard but unrated with pretty large stories.
→ Reply
13 years ago, # |
  Vote: I like it +5 Vote: I do not like it
Round #79 and #80 is coming soon
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Many contests are coming soon. It feels nice :))
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Why isn't 98B in the PROBLEMSET rejudged? The problem has already been modified. 
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I don't have neccessary rights. It will be rejudged soon.
    → Reply