KAN's blog

Codeforces Round #476 (Div. 2) [Thanks, Telegram!]
By KAN, 7 years ago, translation, In English

Hi everyone!

digital resistance

Tomorrow, on the April 25-th, 2018 at 17:35 UTC we are holding Codeforces Round 476 (Div. 2) [Thanks, Telegram!]! The round will be rated for the second division participants, members with higher rating can take part out of competition.

I give the floor to MikeMirzayanov to announce the round:

This round opens a series of thanks-rounds to those who significantly supported Codeforces in the crowdfunding campaign for the 8th anniversary. Although Telegram is not explicitly present on the list of donators, for us this is the first and most important friend. We express our gratitude to Telegram and personally to Pavel Durov for the constant support and send regards from programming contest community. Now that the medieval inquisition against Telegram and all the free Internet has been declared in our country, I admire and express support for Pavel's principled position on protecting our rights and freedoms. Thank you, Telegram!

I join the thanks to Telegram, and also want to thank FalseMirror and Livace who helped me with the problems for the round. Also many thanks to vintage_Vlad_Makeev, GreenGrape and 300iq for their help in round preparation, and arsor for translation.

Good luck!

Congratulations to winners!

Div. 2:

  1. Akylbeek — solved all problems!
  2. kolkulator
  3. reeWorld
  4. 16bit075
  5. teamskiy

Div. 1:

  1. uwi
  2. quailty
  3. bicsi
  4. Barichek
  5. Adalbert

The analysis is here.

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

Comments Comments (82)
| Write comment?
»
7 years ago, # |
  Vote: I like it +81 Vote: I do not like it

Codeforces Div-2 Rated Contest after more than a week. Now, It's like oxygen for me.

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

How many problem will be there?

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

C'mon It's Bayern vs Real Madrid tomorrow, move that round one/two hours earlier please :(

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

Thanks Telegram!

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

I started to feel bad for my hair

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

Here it says contest time is 17:35UTC, but on the contest page it says 12:35UTC. Is there something I am missing?

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

Not a good time for East Asia participants.

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

    Yeah, I'm in China and I didn't take a close look at the lime when I registered. Then I realised it actually starts in midnight (1:35 in the morning). I mean, come on, you wouldn't expect me to stay up for 6 hours just for a contest?? I need to go to school too...

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

      I know I can start a virtual contest, or I can just solve the problems in the problemset, but I've never participated in a CF contest before and it should be my first one if it doesn't start in midnight :(

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

This round opens a series of thanks-rounds

→ Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it +29 Vote: I do not like it

No time to sleep!

  1. CS Round #78
  2. CF Round #476
  3. Champions League semi-final
→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It's 2:30a.m in Bangladesh !

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

    Isn't it 11.30PM? Your time zone is UTC+6, right?

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

      Yeah! But aforementioned link shows 2:30a.m !

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

        The link shows time converted from 20:35 UTC. Perhaps the author edited the text appeared in the blog entry, but forgot the link, by mistake.

        KAN, perhaps you should have a look.

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

          It seems now the link is correct. Contest starts on 17:35:00 (UTC).

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

            It is correct now.

            Thanks for the response!

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

Wow,3 awesome things in one day(Avengers:Infinity war,Read Madrid vs Bayern and round #476).

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

Remembered a good old song "Telegraph".

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

I heard that Russia is forcing out Telegram. But seems not every guy agrees to do so...

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

Every contest is very late for me in China. I have been stayed up late for about five times to enter the contests and always felt sleepy... (And this contest is later than usual)

However, I think the contests is very good for me and it improves my coding a lot! Thank to Codeforces!

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

How many problems will be there?

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

    Most likely 5, unless they will mention something else

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

It would be nice if you posted no of problems and score distribution :)

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

Now that the medieval inquisition against Telegram and all the free Internet has been declared in our country, I admire and express support for Pavel's principled position on protecting our rights and freedoms.
Is that safe to say?

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

[Thanks, Telegram!]

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

It is so tiring for staying up late.

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

how to solve C?

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

    What I did was for each value d between 1 and D, calculate with binary search minimum x such that there won't be more than d "rounds". Once I know that value, do another binary search to find maximum x such that there will be exactly d rounds. With that value I'd get x * d candies. Keep the maximum among them all.

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

    Notice, than d <= min(n, 1000), so we can do like this: for(int i = 1; i < d; i++){ cnt = i * k + 1 — how many people will get candies, i — amount of cycles we make (+1 — Arkady) x = n / cnt — how many candies will get each person if(x > m) continue; answer = max(answer, x * (i + 1)); } if(d == 1) cout << m; else cout << max(m, answer);

    it works on Pretests, but hopefully on real tests to.

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

      :P im sorry man . Congrats on becoming Expert :)

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

        Thank you, man :)

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

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

How to solve E?

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

What's pretest 5 for C? :'(

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

Can anyone provide me a solution for E?

I'm thinking of Trie and some greedy sorting for the string list, but not very sure about the accuracy of this approach...

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

    Trie and BFS failed

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

      I tried to hack myself but failed.

      Can you give a counterexample?

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

        5 aba ac aca acaa acaaa

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

          I sorted the strings based on their length and used a greedy approach using trie. Can you plz tell bug in this method. Thanks in Advance.

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

        i wish i knew

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

    You can make trie and use multiset for saving all current depths for answers (initially each depth is equal to string length). After this, for current node in trie you will try to put some element from its subtree ( make some prefix shorter than before) — you will put one with biggest depth. For good complexity, you should always merge bigger multiset to smaller. Total complexity O(nlog2(n))

    I used long doubles in the third task, I believe it will be enough precise :)

    Very nice problemset ! Thank you !

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

      Why putting element with biggest depth will be always correct?

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

        Well I think that is really easy. You will put one with biggest depth becuase it will decrease answer for the biggest value ( I know you are not stupid ). But if you think we could put maybe that one somewhere up in the trie, that is also correct, but actually there is not difference which one is in node x and which one is in node y. Just sum of depths of occupated nodes should be smallest possible.

        I know that still I didn't tell you something crucial. But maybe you do not understand my algorithm, I am going down -> up and updating current node with furthest in its subtree.

        Sorry If I am unclear, but I do not know to explane better. Somehow it is obvious to me.

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

      not necessary to merge smaller to bigger, because every end of the string occurs in that string only, so total complexity O(sum of words sizes)

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

What is pretest 5 in C,any idea?

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

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

This is the weirdest order I've ever solved problems in. (the reason i failed A was because I set max in binary search as 10 million instead of 100 million)

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

Wow, system tests in C got almost everyone!

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

When you've given up all your hopes, but you returned and realized other people's system test failures gained you nearly 220 additional ranks.

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

Can someone please tell me where I am logically going wrong in C code

Thank you

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

    The function f is not an first increasing then decreasing function. Therefore you cannot use ternary search.

    Actually if you plot it, it looks something like this: link

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

Can anyone please help why this code is wrong on Pretest 4 for Problem A.Thanks in advance http://codeforces.net/contest/965/submission/37614312

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

    If you only put the code inside of your if, I think you'll get AC.

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

      Yes thanks its same but still why? Very discouraging couldnt move forward,why its giving wrong still it will give right..?

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

        You can't put in else: if(ans%p!=0)

        Like in if statement, you need some variable to rember ans before you divide

        Here is fixed submission for your problem

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

For B it could be bigger constraints, e.g. n = 500. To let solve it with .

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

After system alalysis, my C question failed. and I thought it's very easy to implement in python. and so many boundary test cases to be handled in c++ .

But, guess what, Just changing long long to long double , gives you correct answer.

http://codeforces.net/contest/965/submission/37606838

http://codeforces.net/contest/965/submission/37620212

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

My solution to E: put a priority queue with first element no of tries and then how much do we try to shorten the word. {a,b} If we can shorten the top element on priority queue, then we do it, and we insert {{a+1, 1},shortened_string} back. If we can't shorten the top element, then we insert {{a+1,b+1},string} back. However, it gives WA #7. Can anyone hack it with a simple test case, pls, so I can understand? 37620587

→ Reply