HolkinPV's blog

Codeforces Round #123 (Div. 2)
By HolkinPV, 12 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?
»
12 years ago, # |
  Vote: I like it -56 Vote: I do not like it

I am students.

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

Good luck to all. :-)

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

I hate problem C.......

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

    I hate string parsing. Problem C is just colateral damage :)

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

      Seen at the last moment that the string can have '\t' in, and no time for correct it... Those kind of problem is not bad, because it teachs you to prevent all possible cases, but it's often very frustrating...

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

        really frustrating... i used regular expression. i knew little about it before

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

        I used %[\n )] in scanf to match the keyword. Forget \t should be my error :(

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

        Test does not contain '\t' symbols as I know. Only ' '.

        → Reply
»
12 years ago, # |
  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
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    nevermind

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

    Yes, they was o(n), you should find all X where line intersect OX axis, number of unique point — it's a answer)

    → Reply
»
12 years ago, # |
  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
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    3.5

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

    children in first grade are told what symbols '/' means

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

      It's ambiguous as to programming languages.

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

        the problem statement was in English language, not a programming one

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

    Couldn't you ask it?

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

    Problems are written in English language, not C++ : )

    Usually, . But .

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

    It doesn't really matter because even if you use integer division, you still take the basket with the lower number in case of a tie.

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

      Counterexample:

      • if M=4, mid=2.0, the order of baskets is: 2, 1, 3, 4
      • if M=4, mid=2.5, the order of baskets is: 2, 3, 1, 4
      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oops. You're right. Anyway, I used integer division, so I guess that was the intended meaning. Is there any other explanation why it worked? I can't find any.

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

          You may have interpreted it as integer division, but your code skips the issue entirely by multiplying out both sides:

          abs((M + 1) - 2 * a.second)

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

            Oh yeah, I totally forgot. At first, I wrote it abs((M + 1) / 2 — a.second) and then changed it. I had a bug, but then I realized that it was something else. It turns out that I was pretty lucky because I just tried it with the division and it fails "2 6". So we have our answer :)

            → Reply
»
12 years ago, # |
  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
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← 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
      • »
        »
        »
        »
        12 years ago, # ^ |
        ← 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
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            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
»
12 years ago, # |
  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
»
12 years ago, # |
  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
  • »
    »
    12 years ago, # ^ |
    ← 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
»
12 years ago, # |
  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
  • »
    »
    12 years ago, # ^ |
      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
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    brute force solution here

    → Reply
  • »
    »
    12 years ago, # ^ |
    ← 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
»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Will there be an editorial ?

→ Reply