yaro's blog

Codeforces Round #188
By yaro, 11 years ago, translation, In English

Hello, friends!

Winter 188th Codeforces Round is coming!

We wished to prepare for you some enjoyable problems (as we believe, not very difficult) with nice ideas and clear statements.

"We" includes authors of the problems yaro and Rei, Codeforces Rounds supervisor Gerald and the platform founder MikeMirzayanov. Special thanks to Pasha (PavelKunyavskiy) and Artem (RAD) for the testing and helpful comments.

Last time I was preparing a competition here on Codeforces, Rounds were still "beta". Well, with less "beta" comes greater responsibility. So I wish the authors and the organizers a successfully held Round. As for the participants, I wish you the unconventional ideas, the clean code (and a clean keyboard, of course), and satisfaction from five (well, possibly the less number will also do...) correct and accepted solutions!

It seems to us that it is not an easy job to arrange the problems by their difficulty, so we have chosen the dynamic scores. Still (out of curiousity) let us put a bet on the following relative difficulties for the problems: div.1 — B-B-C-C-E, div.2 — A-B-C-C-E. How close is our guess?

UPD Sorry for the problems with the Codeforces testing queue during the round.

We will still be happy if you rate our contest (when it will be over): short survey.

And with the gap of one hack the winner of div.1 is meret (Jakub Pachocki)!

Div.1 standings, Div.2 standings.

Analysis (thanks to Rei for the translation).

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

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

Seeing your bet on difficulty levels, Just one question: Are the last 3 questions of div2 not gonna be the same as first 3 questions of div 1..??

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

    Yes, they are.

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

      what is d diff b/w div 1 & div 2? i am a beginner and this is my first contest. what should i opt for- div 1 or 2? plz reply asap

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

    it seems like div 2 will be A-B-**D**-**D**-E !!!!

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

      D1 500 = D2 1500, D1 1000 = D2 2000, D1 1500 = D2 2500

      This tradition is also a bit strange. The ratios of points are different.

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

        Are you sure that ratios of point must be equals to ratios of difficulties? It isn't clearly.

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

      Exactly!

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

maybe there will be GAME OF THRONES effect on the problem statement.. :)

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

    'We have to save Robb! He needs your help, but for this you have to find the number of .... to identify the traitor. Please, hurry up!' For example

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

Since you said for div 2 it's A-B-C-C-E, I guess you meant that it's A-A-C-C-E for div 1?

Or is it A-B-D-D-E for div 2??

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

    C'mon everyone, don't be so peaky :) He only said that the 3th and 4th problem are of similar difficulty.

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

I hope that this round will be easier because according to the announcement, it seems that this round is going to be difficult. Thanks !

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

Haaa, Game of Thrones! "Growing Strong" & "As High As Honor"!

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

contest is prepared by a lot of people thank you all but I hope it will not be like chinese contest

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

Thanks yaro and also Rei for the contest!

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

    if it is easy for you, it will also be easy for other people :D

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

      Than the competition becomes a speed competition :D

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

        I participated in two such contests(but it was not simple(AB — very simple and CDE or DE — difficult(solved by 5-30 users)

        1) Codeforces Round 163 (Div. 2) (there were 2 very simple problems, third was solved by 80 users, and two last weren't solved) — it's really speed competition

        2) Untitled contest

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

          I had a similar experience, where just one unsuccessful hack brought me from position 200 to position 1300 XD

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

            And my schoolmate did one successful hack and comes to position 400 from position 900(but his own solution crashed on final tests)

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

what is d diff b/w div 1 & div 2? i am a beginner and this is my first contest. what should i opt for- div 1 or 2? plz reply asap.

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

judgement is going very slowly... please check

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

What the hell is that?! 15 minutes to get a response for the submission?!!!

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

in queue for more than 10 minutes in Div2 B. judging sucks. :(

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

very slow judgement, this is becoming very annoying

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

Queued :(

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

    Yeah, I think is time to upgrade those Pentium II they have, don't you think? In TopCoder this never happens, just saying...

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

      Watch out, people are very sensitive here... My "Queued" comment presses some buttons that the other complaints don't

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

      In topcoder problems there are not super large constraints, so the system test is evaluated quickly... Just saying.

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

        We are talking about the pretests here, which are known for their lack of "super large constraints", whose time-limit is 2s anyway. So, please.

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

          In fact, some pretests can have 'super large constraints' :) I don't know if this contest have it, but well... Have fun and keep coding.

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

      There's no judge results right after the submission. How would it possible to get queue? (Solutions aren't testing on samples)

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

How is my solution hacked even when i ddnt lock it ??

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

    when you didn't lock your solution it can be hacked but you can resubmit another solution again, but when you lock it, you can't resubmit another solution.

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

The judegement is very slow. Hope the system test will be finished as soon as possible.

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

Wow, so many hacks for Div2 Problem C. I guess some coders overlooked the constraints for input data. Anyway, at least it was interesting trying to hack others. Oh and it seems to me that the writers have managed to make a nearly-perfect A-B-C-D-E problem set for DIV2, at least according to number of solvers before sys-test...

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

    For Div2 Problem C.

    Maybe some case like this: -1000000000000000000 1 2

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

    my hacking test for problem C Div 2: -1000000000000000000 1 1000000000000000000

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

i guess one of reason that the pretest is a bit slow is because many TLE codes for C div 2 :)

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

thanks yaro and Rei for the contest! :) next time try to make the system testing a bit faster!

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

how cruel the C in div.2 is! -10^18 1 10^18 is a strong test data.^_^.

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

Survey for the contest....what a democracy..!

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

Sad sad sad :-(|) ...

...
long long x,y,m;
long long res;
...
int mymx = max(x,y); // int ???
int mymn = min(x,y); // int ???

x = mymx;
y = mymn;
...
→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

system testing has also been too slow!!! what is the reason?

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

    I guess because of the amount of TLEs in DIV2 C and DIV1 A

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

      All TLEs solutions in A div 1 (C div 2) were hacked, I think. And slow speed of system testing is because slow B div 1 (D div 2) solutions.

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

Oh,It my best rank until now.

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

Status of submission 3895303 is still "Running on pretest 8", why?

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

    Because that code is Forrest Gump ..... "Run Forrest Run " ...... :) :

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

my submission 3887964 for Div-2 B failed on the last test case! :(

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

oh damn, i forgot to update the volume of vessels...

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

I don't understand why i was got RTE in div-2 B. I just assign the size of sting s to n and it gets AC. AC link http://codeforces.me/contest/318/submission/3895790 RTE link http://codeforces.me/contest/318/submission/3888165 Can any one explain it?Thanks in advance.

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

    same thing happening to me too...but i got MLE instead of RTE..

    RTE: 3887964, AC: 3895821

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

      But i want to know what's the problem with "i<s.size()-4" instead of "i<n-4" where n=s.size().

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

        s.size() returns an UNSIGNED integer, so if s.size() is less than 4

        This statement ( s.size() — 4) won't be a negative number! It will be a really big positive number and the loop won't end and it will try to access out of bounds places in the array

        You need to cast s.size() to (int), signed int in order to avoid this..

        You can print the value of s.size()-4 when s has size less than 4 and see the output yourself.

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

          I had the same problem, and I got the answer.

          thank you guys for asking and answering the question.

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

    s.size() is unsigned, so when s.size() < 4, s.size() - 4 would be a large unsigned integer, and you'll get RTE.

    Edit: That's why some people (including me) has a predefined macro #define SZ(x) (int)x.size() :D

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

    Happened with me as well. I should never have ignored those compiler warnings.

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

the worst thing about codeforces is that the main testing takes place after the contest ,

if it would have told that my solution is wrong after running the test cases during the contest ,i would have corrected my solution this thing needs to be changes,i m not sure even after passing pre test cases whether my solution will increase or not

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

    that's why it's called 'pre'-test

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

Waiting Contest rating update.

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

I think it's A-B-B-D-E for Div 2

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

    And it seems like A-B-E-C-F for Div 1 .^_^.

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

      what do you mean by F ? F...K ?

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

        I mean it's harder than E...it has 3000 point

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

D (Div. 1) was very similar to TCO 2A Hard. I was able to copy & paste 1/3 of the code.

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

Is div-2 C can be solved by Extended Euclid?

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

    Div-2 C is simple brute force, but you need to take care of the corner cases where the answer is 0 or -1 or when one of x and y is negative.

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

      It's not a 'simple brute force'. Consider the Test Case -1000000000000000000 1 1000000000000000000. With a pure brute force this TC would definitely give TLE. The trick is to consider the case, when one of the numbers is <0 and the other one >0. And only then you can do brute force. Edit: oh, sorry, I missed the last part of your comment JuanMata

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

Can any one tell me about SergeiFedorov's solution for Problem E? ... My solution get TLE when Princess && Shadow are within a same block....

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

    Well, I could ))

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

    Idea: if we could reach point outside of the forest, than do it with both points. Then find two nearest trees on the border (one by x coordinate and one by y coordinate) and win :)

    If we stand inside the forest and could not get out of it, then just go to the position where shadow stands. Then again to the new shadow position and so on, until we reach it. Of course one should check that they lie in the same component.

    I use simple dfs to move from one point to another while inside forest. And greedy one to move to the border trees while points lie outside.

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

      ... Wow, this is better ... I have learnd a lesson ... .. Thanks ~~

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

For all those who solved problem D, where do you get the array?

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

    One way to get it is to precompute it. I left the code I used in my solution: 3891054.

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

      Or precompute it like this: 3896247 (only compute the masks you actually need instead of all; runs 5 secs on my computer).

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

Interesting round! Can't wait to see editorial for Balance.

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

when is the next round comming?

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

any hint about Div1 D ?

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

    There is always an option to find our analysis. It's not that hard (I know at least three ways to find it)...

    → Reply