HolkinPV's blog

Codeforces Round #123 (Div. 2)
By HolkinPV, 14 years ago, translation, In English

Welcome, friends)

We are glad to introduce you regular Codeforces round #123 for Div.2 participants. Everyone can traditionally participate in it.

Problems are prepared by command of authors: Ivan Fefer (Fefer_Ivan), Igor Kudryashov (Igor_Kudryashov), Pavel Kholkin (HolkinPV) and Gerald Agapov (Gerald). Also thanks to Pavel Kunyavskiy (PavelKunyavskiy) and Alexander Kouprin (Alex_KPR) for their help. And traditionally thanks to Michael Mirzayanov (MikeMirzayanov) for Codeforces system and Mary Belova (Delinur) for translating problems.

Score distribution is standard: 500, 1000, 1500, 2000, 2500.

We wish you success and high rating!

Congratulations to winners:

  1. bmerry
  2. adrian.jaskolka
  3. cheshire_cat
  4. alexej
  5. psw

UPD: the tutorial is here

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

Comments Comments (42)
| Write comment?
»
14 years ago, hide # |
 
Vote: I like it -56 Vote: I do not like it

I am students.

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

Good luck to all. :-)

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

I hate problem C.......

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

Will n log n time out in problem D? Mine nlog n timed out. Is there any o(n)?

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

Problem B. You should mention that if m is 6, for example, (m + 1) / 2 equals 3 or 3.5.

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

In problem C I used Scanner and it not even passed the first test case..Then I used BufferedReader and it got accepted..Could anyone explain why?? Scanner BufferedReader

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

    I could be wrong, but you should use nextLine() for entire lines.

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

      But I changed the Delimiter to "\n" ..So it is the same I guess..

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

        nextLine() reads characters until the end of a line, so after reading the first integer in the first line, you should put an extra nextLine(). Then a "carret" will be moved to the next line and you can read an input as expected. Otherwise the last line will be skipped. Here is the corrected solution that passes: 1781961

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

          Can u please make it more clear for a dumb head like me.. I made a similar mistake on 1 more problem and I want to rectify it now ..plz..

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

Problem E,I can't understand "angle"...what is that?

It means parallel to the X axis ?

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

In problem C:The program may have spaces at the beginning of a line, at the end of a line, before and after a bracket, a comma or a quote mark. But I got stuck in cin.getline(s,55,'\n'). I don't know why it reads more lines than you data gives.

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

    The second t.cha[len] = '\0'; should be t.msg[len] = '\0'; Oh, and maybe you should consider putting a cin.getline(s,55,'\n'); instead of getchar() after reading n too just to be safe.

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

For problem A, I was looking at bmerry's solution but I don't understand why the formula he used is: down_time = (c*a + b - 1) / b

A lot of solutions I studied use this formula or some variation. I was trying to solve the problem using some kind of simulation but was unable to, but everybody's I've looked at uses some kind of formula.

The other thing he does is subtract c from downTime, and the answer is max of 0 or that difference.

Can someone explain how to come up with this formula? Thank you.

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

    I simulated problem A. You can take a look at my code here

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

    brute force solution here

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

    What I'll tell is effectively the same solution.

    If b ≥ a, then we can wait 0 seconds and still there will be no delays in the streaming.

    Suppose that b < a. Consider the moment when the streaming has finished. By problem statement we must have (t + c)b ≥ ca (the amount of data received in t + c seconds is not less that the amount of data in c seconds of the video).

    Lemma: If (t + c)b = tb + cb ≥ ca, then also for any 0 ≤ t0 < c it holds that tb + t0b ≥ t0a (the amount of data received in t + t0 seconds is enough to play t0 seconds of the video).

    Proof:

    tb + cb ≥ ca
    tb ≥ ca - cb
    tb ≥ c(a - b) ≥ t0(a - b)
    tb + t0b ≥ t0a, 

    because $0 \geq t_{0} < c$ and b < a.

    Consequently, we only need to find such t that tb + cb ≥ ca is true, and the rest will follow. The smallest integer t that satisfies this inequality is

    Finally, for integer division that is equal to

    You can also take $c$ out of the numerator, which gives you bmerry's

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

Will there be an editorial ?

→ Reply