Berezin's blog

Codeforces Round #234 (Div. 2)
By Berezin, 11 years ago, translation, In English

Hi! Soon Codeforces Round #234 (Div. 2) will take place, i am the author, Dmytro Berezin :)

Thanks to Gerald Agapov (Gerald) for the help in round preparation, Maria Belova (Delinur) for tasks translations, Mike Mirzayanov (MikeMirzayanov) for perfect system, and Sergii Nagin (Sereja) for his agreement (to share his evening with me) to help in testing.

Distribution will be announced as soon as found :) Standard :)

Good luck!

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

Comments Comments (132)
| Write comment?
»
11 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Sorry for my bad english.

:D

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

This is the first round after CF crashed, I'm very excited with this round, also number 234 have several nice coincidence with primes numbers!!!! I Hope be a good round for everyone!!! let's go to upgrade ranking!!! Good luck to everyone!!

J

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

Glad to see Codeforces back on its feet.

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

This is my first contest on codeforces,I like ACM. I think it will be successful for me. Good luck for everybody!!!

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

Wish to become Candidate Master again.

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

    Hope codeforces don't be such a problem again.After all,I really like it.

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

After accident ,i think problems in round will be about crash of the system. Good luck for everybody "Fixing" the system.

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

Last contest people here were saying that 233 is a very lucky number and the website crashed. Stop saying "hope the contest will be lucky". Anything that you say will not affect the contest.

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

in russian version of this blog it is written "to share delicious potatoes and becon with me" instead of "evening", also there is "potatoes" among the tags (prooflink)

maybe this will help you solve more problems during contest, gl :)

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

Distirbution Distribution will be anounced announced as soos soon as found decided

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

    Thank you, sorry for that typos. "Found" was a small joke about lost distribution :)

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

Hope this contest would be about Inna and Dima. :)

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

Dark week of codeforces ending after 234(round)2(div) seconds...

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

Distribution not found :D

→ Reply
»
11 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Problem B: simultaneously instead of simulaneously. Please fix it.

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

Problem D: The way with number i can be described with integers ui, vi and xi mean that this way allows moving energy from bacteria with number ui to bacteria with number vi or vice versa for xi dollars.

ui can go to vi with xi dollars. Does it mean vi can go to ui with xi dollars?

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

    I think so. That is what "vice versa" means, I guess.

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

      Yeah, and the problem didn't say whether ui,vi <= n. Actually, it should describe clear this point.

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

i submitted peoblem B wrongly 3 times before the announcement was made. will i get +150?

→ Reply
»
11 years ago, # |
  Vote: I like it -7 Vote: I do not like it

Easy problems.

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

A sad day for hackers :(

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

Problem B solution, before the announcement is NP-Complete ?!

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

    Yeah, i think so

    → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 5   Vote: I like it -8 Vote: I do not like it

    first i will answer ur question. no, it is still solvable in . i solved it well before the announcement was made (albeit after one wrong submission due to problem statement not being very clear).

    the problem asked to find minimum number of moves, and we can easily observe that choosing all rows where dwarf has not yet reached candy is the minimum answer.
    so i don't think the announcement really changed anything about the solution. in fact it just gave us a hint as to how to solve the problem.

    EDIT: sorry, my mistake! please ignore this post!

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

      Wrong, consider example:

      G....S
G.S...
G..S..

      The minimum number of moves is 2, not 3.

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

        i don't think u understood the problem correctly. in each move, the player must choose a set of rows and move the dwarf in all these rows to the right, until one of them reaches the candy (or the end of row).

        EDIT: sorry, my mistake. i couldnt visualize ur example properly when i wrote the original comment as it wasnt displayed like a matrix then.

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

          That's right, and we can do it in two steps:

          1. rows 1 and 2;
          2. rows 1 and 3.
          → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think you are wrong the answer is 3

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

      look at this sample :

      3 7 ....G.S

      ..G...S

      G.....S

      by your algorithm answer is 3 but answer is 2.

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

      That's not true. For example, consider the testcase:

      3 4
**GS
*G*S
G**S

      The optimal solution is to choose row 1 and 3 in the first move and then rows 2 and 3 in the second.

      → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 5   Vote: I like it +1 Vote: I do not like it

    Official test from task B :

    4 8
G*S*****
****G*S*
G*****S*
**G***S*

    Answer: 3

    But the answer is 2: firstly choose 3 and 4 lines, then 1,2,3.

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

Announcement for B problem was too late i thought every step is move not every "lets go " is a move !

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

The problem statement for Problem B was corrected too late.

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

Impressed with amazing testing speed

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

    Testing does not have unusual speed... The speed you see is because of low number of submissions...

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

      but there were many users registered :/

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

        Just 1800 of them participated...

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

Was it just me or were the problem statements this time pretty difficult to understand (in English)?

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

In problem D can someone explain why the answer for 7 test "yes"?

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

    There is only one bacteria for each type. So all bacterias in one type can gain energy with cost = 0 from a bacteria with same type .

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

      "Dima's Chef (Inna) calls the type-distribution correct if there is a way (may be non-direct) to move energy from any bacteria of the particular type to any other bacteria of the same type (between any two bacteria of the same type) for zero cost."

      there is 0 operation,so bacterias can not move energy from any bacteria to any other bacteria,am i right?

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

        ...to any other bacteria of the same type...

        Any other. This condition's satisfied if there's no other bacteria of the same type.

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

The descriptions of five problems are too lengthy and so difficult to understand...

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

Horrible problem statements ... :/

:(

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

May someone tell me why this submission get WA, i don't know why it is printing -1 on test 8

http://mirror.codeforces.com/contest/400/submission/5944310

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

Nice problems... Thanks to author....!!!

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

In problem E, I submitted this code at first. 5935260

But, I easily found the case which make my code TLE. (n=m=10^5 , a1=a2=...=an=65535, question are repetition of "0 0" and "0 65535")

So, I wrote another code and submiited. And I lost about 900 pts :(

But, I submitted first solution after contest, it passed systest and execution time is less than my second submission!!!

To avoid such things, I want writers to make testcases more powerful...

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

    I agree, it should TLE...

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

For problem B, why my submission code1 got WA, but another code2 got AC, but I do think they are the same. Plz help me, thanks much.

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

    In the first code, you use char p[1005] to store the distance between 'G' and 'S'
    It will overflow.

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

      Oh, I see it. What a stupid mistake. Thanks very much.

      → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

How can the answer for the following test case be 3??

3 4
**GS
*G*S
G**S

Clearly it is 2: 1st move: select 1st row and 3rd row. 2nd move: select 2nd row and 3rd row. but the accepted answer is 3. Can anyone explain why this is so?? Was it a fault or I'm not understanding the problem correctly. Because I wasted a lot of time thinking otherwise. :(

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

    i have the same problem and The author had a mistake: "Problem B. Inna and New Matrix of Candies ***** In problem B was mistake in the statement you must choose all line with dwarf that is not in candy location, not several. Now the statement is correct. Sorry for that."

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

      But the announcement said "you must choose all line with dwarf that is not in candy location, not several" So "all line" means that we can choose several lines in which dwarf is not present on the candy. Isn't it??

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

      Never mind. I got it. Although the announcement was also ambiguous. First saying "all line" and then "not several". Confusing. :(

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

    You are right, answer was 2 before the announcement. But they changed problem in middle of contest to this version : In a move you must chose all of row that G is not arrived to S , but the first problem was a set of rows.

    but don't worry, this is just another mistake in codeforces. :)

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

    After your first move ('O' indicates G and S are in the same position):

    ***O
**GS
*G*S

    After your second move:

    ***O
***O
**GS

    So you need a third move: select the 3rd row

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

    The problem statement has been changed at the later stage.You have to move in each row where G and S have different index. In the above case — 1 move , 1st row G and S have same index.2nd row **GS.3rd row **G*S 2nd move ,1st row work is already over, 2nd row G and S have same index now.3rd row **GS 3rd move,3rd row G and S have same index now.1st and 2nd row already over.

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

    The statement says that you are not allowed to exclude any possible movement, so, by saying "select 1 and 3", you are excluding a possible movement (moving on row 2), which is not correct according to the final statement. Your point is correct regarding the original statement, tough.

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

Problem B was so cute. I spent more than an hour to try to figure it out bur failed...Hahahahaha~

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

Thanks for the testing speed.Hope it will be continued in future contests...

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

We had some interesting friends join our competition today :D

dibil01 dibil02 dibil03 dibil04 dibil05 dibil07

dibil08 dibil09 dibil10 dibil11 dibil12 dibil13

dibil14 dibil15 dibil16 dibil17 dibil18 dibil19

dibil20 dibil21 dibil22 dibil23 dibil24 dibil25

dibil26 dibil27 dibil28 dibil29 dibil30 dibil31

dibil32 dibil33 dibil34 dibil35 dibil36 dibil37

dibil38 dibil39 dibil40 dibil41 dibil42

Mr. dibil, I applaud your determination, but why have you forgotten about 06? It ruined my beautiful rectangle :(

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

    So Mr dibil, how many brothers are u?

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

      Dibil can be family title too... :P

      Mr. dibil, his father, his uncle, his son, his grandfather... everyone is in codeforces ... :P

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

    i think the real owner of all these accounts is Beket. midway through the contest, i saw that he had hacked dibil03's solution for problem A 6 times!
    i guess the admins saw this, analyzed the codes of the hacked solutions (probably they all contained hard-coded wrong output for the hack cases having checked the codes, i can now confirm that this is indeed true), and discounted all hacks except the first one.

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

was it an unrated contest? when the rating will be changed? or won't change?

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

In the beginning I thought the data for B is too weak ....

And I also wrote a wrong code , and want to hack somebody .....

and I get -50 .....

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

no server error seen in today's contest :) ...... good work codeforces :)

→ Reply
»
11 years ago, # |
  Vote: I like it -7 Vote: I do not like it

Omg, with such a lot of bugs this round is still rated.

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

Ratings have changed!

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

my rating changed from 1694 to 1697! not sure if i should be happy that it increased, or sad that i was so close to going back to Candidate Master!!

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

کصصصصااافطاا آنریت کنیییین.عوضیا "بی" غلط بووووود in english : nice contest,nice questions

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

I need help with understanding problem E. Doesn't procedure look like this:

  • 1 2 1
  • 3 3
  • 3

And the sum is 13? What didn't I understand correctly?

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

Poor English translation in this round.

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

http://mirror.codeforces.com/contest/400/submission/5935405 I think it strange,for I compiled the program with my native compiler "GNU GCC Compiler 4.8.2", which seemed to be correct(there is "1x12").However on the onlinejudge, it failed with the same compiler at a lower version.Why is there such a difference?

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

    something stranger:http://mirror.codeforces.com/contest/400/submission/5947329 I changed the compiler to MS C++ 2010,while the answer seems to be correct.But there is a runtime error after the output of the answer.I checked it out and found it was because of the wrong exit code.

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

      I also faced a similar kind of problem with this code, on ideone it is showing runtime error and on codeforces WA while it is working fine on my laptop: http://ideone.com/V6GaTw

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

      Here: char t[12]; cin >> t; 13 symbols are getting read into t (12 letters plus a zero as the end of line). Change to t[13] and it will get accepted.

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

        Thank you!I did forget the end of string token, and it get accepted now.

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

    In char t[12], you have to leave space also for the terminating null character. See 5948774.

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

Hi everyone, can anyone explain me why the output of the following input is 9?

10 10 G********S G******S G****S G**S ****G****S *****G***S ******G**S *******G*S ********GS G********S

Because according with the problem you need the number of steps to solve the problem

Step 1: Say Let's go and end when row 8 arrive the candy cell.

Step 2: Say Let's go and end when row 7 arrive the candy cell.

Step 3: Say Let's go and end when row 6 arrive the candy cell.

Step 4: Say Let's go and end when row 5 arrive the candy cell.

Step 5: Say Let's go and end when row 4 arrive the candy cell.

Step 6: Say Let's go and end when row 3 arrive the candy cell.

Step 7: Say Let's go and end when row 2 arrive the candy cell.

Step 8: Say Let's go and end when row 1 and row 9 arrive the candy cell.

So, it is giving me 8 for best answer, what I am missing?

Thanks in advances J

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

    At the very least, there are 10 rows, and you mention only 9.

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

      In step8 row1 and row9 arrive the candy cell, row8 it is not counting because S and G are in the same cell

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

        Still only rows 1–9 in your explanation...

        There are 9 rows with numbers from 1 to 9, inclusive.

        There are 10 rows in the input, according to the first line.

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

          Sorry the row is missing is the one with the S and G in the same cell,

          *In step8 row1 and row10 arrive the candy cell, row9 it is not counting because S and G are in the same cell

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

            Initially, S and G can not be on the same cell.

            Otherwise, what is the one single character you read from standard input for that cell?

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

              if that can't happen how you understand row 9:

              ********GS

              ?

              I though that means they are in the same cell, this is the test3

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

                Quoting the problem statement:

                The field for the new game is a rectangle table of size n × m.

                ...

                Next n lines each contain m characters — the game field for the "Candy Martix 2: Reload". Character "*" represents an empty cell of the field, character "G" represents a dwarf and character "S" represents a candy.

                Each character in the input corresponds to exactly one cell. So, the string "SG" represents two adjacent cells.

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

                  Ohhh, ok now I got it!! Thank you very much!!

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

"can choose all lines of the matrix where dwarf is not on the cell with candy", it is just 'can', not necessary 'must'. And actually, problem means 'must choose all lines'. This is another point that problem didn't describe clearly.

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

What's the meaning of "judgement failed" ? I tried to submit a solution of problem C (for practice) but the verdict is like that : submission

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

    If you go to the ProblemSet Status, you'll see many submissions with verdict "Judgement failed".

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

    I am not sure, but last time I got that was because I used a huge array. Here you are using a vector of size 10^5 * 2 so I guess it should be fine.

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

      It seems that there is a technical problem in Codeforces , all recent submissions are getting "judgement failed", check this page

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

When I register for practice, my submission's verdict is Judgement failed. What was happened?

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

    Just try submit again. It's only temporary

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

In fact ,I think the problems in this round is very good.But some problem's description is too long too difficult for some Chinese senior high school students,it cost me and my friends a lot of time to understand the meaning of the problems(We not very good at English). So I prefer more problems with simpler description. Thanks.

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

Up for next Round (#234) !

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

Can anyone explain me in short steps their solution to problem E? Thanks :)

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

any editorial? :D

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

Please give the problem E solution

→ Reply