NBAH's blog

Codeforces Round #367 (Div.2)
By NBAH, history, 8 years ago, translation, In English

Hi everyone!

Codeforces Round #367 (Div.2) takes place on 11th of August at 19:35 MSK. As usual, Div.1 participants can join out of competition.

This is my first round on Codeforces! I advise you to read all the problems. Hope everyone will find something interesting.

I'd like to thank GlebsHP for helping me in preparing this round, Yury_Bandarchuk and IvanVan for testing tasks. Of course, many thanks to MikeMirzayanov for great Codeforces and Polygon platforms.

UPD: Scoring is 500-1000-1500-2000-2500

UPD: Editorial

UPD: The contest is over. Congratulations to the winners!

Div.1 winners:

1.anta

2.W4yneb0t

3.sugim48

4.uwi

5.Kmcode

Div.2 winners:

1.jiangzixiao

2.Shining

3.BurningHuie

4.AwD

5.stjepanp

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

Comments Comments (271)
| Write comment?
»
8 years ago, # |
  Vote: I like it -74 Vote: I do not like it

kiram to tarrahe in contest

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

Simple brief statement, thanks a lot and hope high rating change for everyone =D

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

And as usual... scoring will be announced later! (maybe just before the contest! or after the contest!) Whyyyyyyyyy?!

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

Hope this contest will be better than last Div2 only contest. Hope there won't be such a long queue during the contest because of so many people. (Hate the feeling knowing the contest is unrated after a 2hr-hardwork at midnight)

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

    How do you know about last contest? Oh it's your new Div.2 account...

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

      maybe he had new girlfriend ??!

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

      Round he's talking about was unrated. I think that's a reason he is still out of rating.

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

        Look at his profile "Registered: 25 hours ago" -_-

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

short GL & HF, I hope statement will be short as this :))

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

Hope for nice problems and strong pretests :)

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

    Could someone explain to me the reason for downvotes on this comment?

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

      It's Codeforces. You never know what happens to your comment.

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

        Well said Tweety. (y)

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

          Maybe you are new! but you can use up and down vote buttons instead of this comment!

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

            Well said TD. (y)

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

              In hindsight

              Maybe you are new! but you can use up and down vote buttons instead of this comment!

              FYI, I downvoted

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

                but downvoting others won't decrease your negative contributions.

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

                  I hope the community loves me again :) I wrote a lot of stupid downvote worthy stuff to earn -47. Guess I won't be doing that again.

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

                  actually we upvote a comment if it is useful, fun, interesting ,... and we downvote a comment if it is useless, spam, ugly,...

                  if you want upvote then interest us!

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

                  That's not how this works. You never know which comment will be upvoted and which ones will get downvoted.

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

            Downvote doesn't seem to work for me whenever I hit downvote the comment rating stays the same, is there any reason for this?

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

              because others upvote simultaneously...

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

Today, give a stranger one of your smiles. It might be the only sunshine he sees all day.

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

I hope this round will be more interesting than previous one)

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

"Are we poisonous?" the young snake asked his mother. "Yes, dear," she replied — "Why do you ask?" "Cause I've just bitten my tongue! "

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

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

      I think They are using their time for coding :P so, they don't wanna waste their time and using random comments :P

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

MSK means??

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

Round of div2 member?

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

Fact : 367 is a prime number

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

a round without the IOIers ?

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

    Not many of them are Div2 anyways.

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

      Did you just assume their division? triggered

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

is it rated ??

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

    Why everytime there is someone ask that?

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

    if a contest is unrated, they will tell it in announcement ... maybe as an update

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

I hope this contest won't have so many commercials for games and movies. Just clear tasks.

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

    You think the one about avengers was with help of commercials?, u think they ask codeforces community to create probs about them?..

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

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

Too late for Asia......

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

    Too familiar :)) :))

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

    Ah

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

    I have a dream, that there will be more contests ends before 12 m.n. in my local area for me to get at least a purple... At this rate it would probably take several months to wait for a contest which my brain can function normally.

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

Randomness of likes and dislikes will one day be used as a random number generator :v

Like if you disagree :v

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

Today is Codeforces NBA match ;) Wow!! That's great to play on computer too. Thank u very much NBAH. Best of performance for everyone in this match :)

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

Is there anyone who could help me to solve this problem or give any other approach.Thanks in advance http://codeforces.com/blog/entry/46505

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

[user:jibancanyang]Come on,believe yourself,and tonight you must be the candidate master!

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

    a;;;;;;;;;;;;;;;;flbgoqwgowqeiufhhdvbka;bdkasbf;efowofowjo#inwohndlandsfl!

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

      I guess you will be hidden again.... 0.0

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

Anyone here knows how to unregister I'm not sure if I will be able to write codeforces today PELASE HELP

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

    Just don't submit anything or open page of participants >> find your handle >> click the red (X) button to the right of your handle to unregister yourself

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

    If you don't submit, your rating won't be affected.

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

We should wait 9 days for next contest :((

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

    And two week for next div 1 contest!

    So far!

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

      wow! it's a long time for you!!!

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

      You can still practice with div 2 contests, and it's more comfortable since there's no rating on the line.

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

The Olympic season is here and we have some Codeforces rounds scheduled too. We should have an Olympic themed contest.

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

Wish Good luck to all :)

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

Queue is back. :/

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

my source is still in queue for long time. does this happens to anyone else?

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

Codeforces queue :/ . Please do compensate for the time we have lost in this and are still losing.

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

queue 2 : the nightmare

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

make it unrated:/

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

i hope it's not going to be unrated again!

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

Auto comment: topic has been updated by NBAH (previous revision, new revision, compare).

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

20 pages of unjudged solutions

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

I guess it's another unrated contest, unfortunately.

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

I thought the queue problem was solved! I submitted B. Waited for 5 minutes, still in queue. Went to solve C, submitted C, found out B was WA. And now C has been on queue for 3 minutes. wtf! -_-
Thank god it's unrated for me. I'm out.

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

My solution to C is not even in the queue. I am not able to submit it! -_-

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

    Finally was able to submit by uploading the source file. I am having this problem since many days, not able to submit code that is copy-pasted in the editor.

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

Please, don't make it unrated.

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

    It would be unfair for participants who got WA after one hour. :/

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

      Who told you life is fair ;)

      Besides, it will be unfair to those who got their solutions judged in time. Its just like contest time. Some countries benefit from the time, some have troubles. You won't complain about that would you?

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

        if there's long queue, no one will get their solutions judged in time. and really a wa verdict after a long time makes it unfair for the contestant.

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

      R u sure u got wa after an hour? I really think what ur saying is false..All my submissions passed is <=10 mins...and just look at the number of people who solved each problems.. the stats say ur lying

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

      One hour :o ? I submitted program at 5min, 10min, 30min, and 70 mins. I had to wait for more then 5 mins for pretests only for 2nd (which was at 10 min) Rest all submissions were quick in judging (less then 5 mins for sure)

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

    Congrats, good work! ^==^'

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

Wow, really great curve of number solved. And this is only halfway through the contest.

a

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

On a completely off topic, how many people on codeforces follow Silicon Valley (TV show) ?

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

    Well, I don't think you can get your answer if you ask this question here. After some yes/no, people will stop replying due to negative votes (spamming). You should rather create a poll externally and give the link here.

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

C was a dp problem right? I was starting to get it but I didn't have enough time to debug :(

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

    From the fact that it was called "Hard Problem" and that some people submitted it in 4 minutes, I am guessing there is a non DP solution but sadly I don't see it. Can anyone share their solution?

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

      Can you explain what your DP solution was? Just so I know if I was on the right track (if you don't mind).

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

        d[i][t] = minimal cost with last element i, and t = 1 if we don't reverse it, t = 2 if we reverse i-th string.

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

          Glad to know I was pretty close lol. Thanks for the help.

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

            انت مخنث ؟

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

              Lol I like my hair though so I think I'll keep it (if you're making fun of my hair).

              Edit: Also I'm 100% male.

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

                العق مؤخرتي

                بندوق مغكر حالك بتعرف تستخدم google translate ?

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

                  Don't even bother replying him.

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

      Apparently some people did write dynamic solution in 5 minutes e.g. #19788803. I'm impressed.

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

    Yup. You could view it as a graph problem and then it is finding the shortest path in dag from 1 to n that could be done in O(n + m) There are 2*n vertex and every vertex has max of 2 outgoing edges.

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

      I was considering representing it as a dag too. Thanks for the help.

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

    let's call l[i] is the list of strings and r[i] is reserved string of l[i]. Then we have dp[i][0] means min cost of list from 1->i that l[i] is not reserved, and dp[i][1] means l[i] is reserved. First dp[i][0] = Inf, if l[i] >= l[i-1] dp[i][0] = dp[i-1][0], if l[i] >= r[i-1] dp[i][0] = min(dp[i][0],dp[i-1][1]). Then dp[i][1] = Inf, if r[i] >= l[i-1] dp[i][1] = dp[i-1][0] + c[i], if r[i] >= r[i-1] dp[i][1] = min(dp[i][1],dp[i-1][1] + c[i]). Res = min(dp[n][0],dp[n][1]). If Res = Inf then Res = -1. That is my solution and it passed present test.

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

    I implemented a 1D DP solution. Here is the link to the solution.

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

I don't like man :P. When I get 20 minutes penalty and a WA just because I wrote a statement twice . :D

And by the way was it only me who took Manhattan distance in Problem A and passed 6 pretests? :D

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

    I used taxicab geometry too, and I found out I was wrong about it on the 7th pretest :/

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

    same same :P

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

Got response from judge after 20 min from submission.(long queue)

Also sad as i got to know it was wrong after 20 min. :(

Will this be a rated contest?

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

How to solve D? Thank you.

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

    I solved it using Trie

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

    It can be solved by trie, easily. I supposed that you know task to find the biggest xor of two elements in array ( you can find solution on internet easily too). Here you only need to story how many times you went through some node ( because sometime you must delete some edges).

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

    Look at Problem 1 in this article: Trie Tutorial

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

    In my solution we write every number in binary using 35 bits, we use leading zeroes if required.

    I let the map M[i,j] save how many integers x satisfy that when you only look at the bits in the first j positions you get i.

    Both updates and queries can be done in time

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

      Dang I wish I'd thought of this I made a mess trying to implement a Trie

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

    Use Binary Trie.

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

    This is my idea, haven't tried it yet.

    Convert every input(number) to binary system. Put it in BST (1s go right, 0s go left). Make sure that all numbers in binary system are the same size. So 6 -> 110, but if max value is 1e9, it became 0000....110.

    When you search start from leftmost digit and go through BST and pick side different than current digit. When you reach the last node it's your answer.

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

      It looks like greedy solution, can you prove that it right in all cases?

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

        2^t > 2^(t — 1) + 2^(t — 2) + 2^(t — 3) + ... + 2^0.

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

        That part is not so hard, because the every bit is clearly more important than all of the bits to its right, combined .

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

        Thanks.

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

      It's efficient for searching. But wouldn't it be hard when we're gonna do deleting operation on the tree?

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

        I would do same as search, when you reach last node, go up.

        while (true) {
  bool check = parent_has_one_child
  int digit = node_value
  go to parent
  delete child with value == digit
  if (!check) break;
}
        → Reply
»
8 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Wow, CF servers are fast, my first hack on this submission (19791945) takes over 5 × 109 iterations and it ran in sightly less than two seconds.

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

    It's not the "extremely fast servers", but probably the O2 optimization that cut the number of iterations.

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

Had no idea Tries were this standard, so many people solved D.

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

I think my rating will drop to below 900 :/

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

    you guessed right

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

      It is ok I am only doing this for fun for now.

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

        you mean you get fun by solving 0 problem?

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

          I solved 2 actually just couldn't get them right within the contest time and 2A got rejected during testing(WA on test 41) because I didn't set precision to 7 digits after decimal point.

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

            well try to upsolve the rest 3 as well. It won't help unless you gradually develop some new techniques, will it ? :/

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

Anyone else think that the time limit for E was a bit too strict?

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

    I don't know but if the target was split O(q(n + m)) and then it was not strict.

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

      There was a solution in q(n+m)? Wow... at least I managed to implement a working treap for the first time

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

        I wrote the same O(q*n*log n) with treaps as well. I think it was a bit too tempting to come up with some online algorithm that uses treaps of segment trees to fairy solve this problem.

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

        Yep, The good intuition to this solution represents the structure as beads that connecting by a thread with a neighborhood, in this case, you can split O(n + m) thread and connect it by another way.

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

          So, basically a quad-linked list? Thanks!

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

            Yes

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

              any full description of "quad-linked list"? is it smth like sqrt-decomposition of list? Google gives smth strange.

              Thanks in advance

              Tried treap but TA11:(

              UPD just wondering how the hell is possible to distinguish fast c++ qmlog(n) from slow java qm...

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

                Basically there is set of nodes representing the fields of the matrix. Each node is connected via a pointer to its upper, lower, left and right neighbor.

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

                  Statement that rectangles doesn't share common side makes so much more sense now ;) Actually I'm surprised that not much people came up with this solution, as it isn't complicated at all.

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

                  Ok thanks, already read it in solution, seems to me that coded something similar once

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

          Thanks! So trivial yet so hard to think!

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

      What about this O(QNM) solution?

      http://codeforces.com/contest/706/submission/19802812

      I know, this solution utilizes the fact that modern machines are very good at copying large amounts of memory around.

      This just proves that the time limit itself, although the problem and its solution are very interesting, doesn't make any sense.

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

This round is totaly interesting :) Although I couldn't solved problem D (wish that i could learn Trie earlier) but today it is fine!

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

That moment when ur solution is in queue for more than 15 min. And On top of that you get a verdict as a wrong answer . Ruins everything :(

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

i always thought that the feature of rejecting the exact same submission was useless. after this contest i really appreciate it. it saved lots of precious 50-points as i had to submit 10 solutions to see one of them got into the queue.

okay really codeforces what the fuck is happening!

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

i get WA after 30 min from submit ! :)
it should be unrated like Eran Contest

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

    yup...i got WA after 20 min of Submit.

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

      Same Here :(

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

      Yeah now lucky people who didn't get Wrong answer will vote down this comment :)

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

        if someone solved their solution correctly at one go, it doesnt make them lucky, it makes them more aware and smart

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

          they are smart because they didn't get WA ?
          they are smart yeah but they are lucky too because they don't wait 20 min and lose many points and resubmit solution also lose 50 point :)
          in 20 min i can solve B instead of fix small mistake in 'A' problem
          smart only isn't enough

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

            Just solve all problems and your rating won't decrease:D

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

Does anybody know why my submission 19801619 got compile error? Thank you!

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

the queue was so long in the start of this contest please consider this.

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

Who else has used graph to solve C?

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

I spent an hour implementing D using multiset, so I guess this will be my motivation to learn trie finally :D

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

    Do you mean that you did it using standard multiset? Can you post a link please

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

    exact same thing happened with me .... difference being that I could debug my solution after the contest ended :(

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

I see many solutions who got WA#5 in problem D, like me. Good round!

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

I knew that the problem D could be solved by using Trie but I failed to implement it ;(

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

    same here...I had bugs in my remove number function...got it working 5 minutes after the contest ended. :(

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

    This is the second time I know that a problem can easily be solved by trie but failed to implement it. I think tries are tricky to implement so people must have coded them once and use their own code every time I guess.

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

Solved D 5 minutes after the contest ended! I'm too slow!

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

I think, this contest should be RATED.

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

I quite don't understand what everyone is so distraught by long queue of +/- 15 minutes. Every major competition. APIO 2016, CEOI 2016, JBOI 2015 all are really famous for their judging fuck ups. Why does CF need to make this unrated simply to prevent decrease of people's ratings, when such major competitions often end up deciding people's future and college etc.

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

    The competitions you mentioned don't have time penalties.
    When there are fuck-ups in our local onsite contests, we usually blame the system saying to the organizers that in respectful contests like Codeforces rounds such things would be considered very wrong and wouldn't be allowed. Codeforces should stay an example for a good platform with good contests.

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

It was a really bad idea to make Eran's contest unrated. Cuz now a lot of people are upset with the system's speed and it would be kind of unfair to leave it as it is.

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

E was very similar to problem G from Petrozavodsk Winter 2012 (standings)

(the problem is great anyway)

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

I think this contest should be rated. Judge lags were not bad than past contests.

umm... I wonder how to hack Q1. How did you hacked Question No.1?

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

Making this round rated proves how unserious this website is

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

Submissions are being judged after 20 minutes. I came to know about my run time Error of question after 20 minutes. This round should be unrated. Many people would have been affected by this.

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

What is the approach for D?

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

Any idea what Test 41 in A is? I assume it's one of the tests that was used to hack a bunch of solutions in A.

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

    Precision Error,

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

    One of my friend that has almost same solution but used float instead of doubles got WA on this test.

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

"In queue" for 15 minutes after submitting the question, has becomes a permanent feature of codeforces :(

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

Make it rated please i have solved A and B under 20 minutes. and i am happy to do that !

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

    19793914 00:20:53 Hazemzz A - Beru-taxi Java 8 Accepted 20 mins, 53 seconds is not ''under 20 minutes'' :)

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

      Make it rated please i have solved A and B under 20 minutes 54 seconds. and i am happy to do that ![user:latvian]

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

Nice contest! Brief statements. Unfortunately, finished D solution two minutes too late :/. Thoroughly enjoyable nonetheless.

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

In Problem C. I marked my dp[100005][2] with INF as 10e15 it gave a run time error. But when i use INF as 10e14 it works. Language used C++. Can anyone explain ? Thank you.

Edit1 : It's behaving in a weird manner. Sometimes i get correct answer but sometimes i get run time error in custom invocation. I will update once i get to know the reason behind it.

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

    There are 10^5 numbers, so if you add 10^15 10^5 times, you get long long overflow. Maybe that's why

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

    In c++ upto 1234567890123456789 is accepted(>1e18)..then its not possible that 1e15 will give any kind of runtime error :D Check again may be some kind of segmentation fault error must be there.

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

    Always better to keep it as -1 and then add additional checks :). I have made the same mistake before.

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

Only I get #WA41 on A?

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

    "Print a single real value — the minimum time Vasiliy needs to get in any of the Beru-taxi cars. You answer will be considered correct if its absolute or relative error does not exceed 1e-6."

    cout just give the answer that its absolute or relative error does not exceed 1e-5.

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

A solution for D without using trie (though it hasn't passed the systests yet). Let's store all numbers in STL multiset. To perform the third operation, we can find y that gives maximal xor going from the leftmost bit to the rightmost. Given the 10^9 constraint for x, 30 to 0 is enough. Let's say we know some binary prefix of the answer, and that a number in multiset with such binary prefix exists. If x has 1 in this bit, we can just find the the minimal y with such prefix (using multiset.lower_bound()), and if it has 1 in this bit, then add it to the answer. If x has 0 in this bit, we can find lower_bound(answer | (1 << i)) and see if it does exist and isn't greater than answer + (1 << (i + 1) — 1), in order to guarantee the existence of such prefix in multiset, then add to the answer.

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

It will be unfair towards Eran who has created good problems, if this contest is rated

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

    the lag in this contest wasnt as bad as the lag in the contest you are referring too, at most it was ~20 min, you could have moved on to some other question while it was in the queue

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

    No it won't. Just enjoy solving the good problems and stop complaining. The queue wasn't long enough for the contest to become unrated.

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

I got a weird WA61 on problem C. I am sure about the idea, and probably the WA is because of checking whether we can have an answer. Why is my check wrong?

I've changed the way for checking the possibility to have an answer and now have an AC. Does anybody know why did this happen?

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

O(nmq) solution for E. AC in 2464 ms =)

Can be improved to 2121 ms and 1669 ms with SSE.

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

Can we expect editorial today itself??

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

will there be an editorial ?

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

Here was my approach to D.

It is easy to keep up with the set by using std::set and std::map to count the multiplicities.

The real deal is how to deal with the query ?.

First, change the given number to binary. We notice that we can take the high-value digits greedily.

Therefore, we do the following. We set X as the optimal number in the set. Iterate through the bits 29 0. If the binary form of the given number is 0, we want 1 there. If not, we want 0 there. If there are no numbers in the set that satisfies this, we would have to go with alternate path.

Here's an example.

Assume that 111011, 011000, 101000, 000010 is in the set, and the original number is 001101. We want the first bit to be 1. Indeed, there are two such numbers — they are in the interval [32, 64). How do we check that there are numbers in that interval? By using lower_bound!

So we chose [32, 64). Now for the second bit we want 1 as well. Such numbers are in the interval [48, 64). We see that there is one. We want 0 to be the third bit, and such numbers are in the interval [48, 56). However, there are no numbers in that interval! Therefore, we would have to go with the third bit 1.

Continue this, and we would have our optimal X. Now compare ORIGIN XOR X and ORIGIN and return it. Complexity is

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

Kindly have a look at this test case generation program for Question 2 . I was unable to figure out why it was showing (invalid input verdict ) when I tried to hack this submission . (http://codeforces.com/contest/706/submission/[submission:19798157])

My code :

#include<bits/stdc++.h> 
using namespace std;
int main()
{
	int n=99999;
	cout<<n<<endl;
	for(int i=1;i<=n-1;i++){
		cout<<i<<" ";
	}
	cout<<n;
	cout<<endl;
	int q=88888;
	cout<<q<<endl;
	for(int i=2;i<=q;i++)
	{
		cout<<2<<endl;
	}
	cout<<2;
	return 0;
}

Please comment below if any one know the reason. I don't want to do that mistake again. But I was unable to figure out my mistake. (http://codeforces.com/contest/706/hacks/246947/test)

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

in C anyone got WA in test case 18?

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

nice contest ,but slow system testing :P hoping to get high ratings

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

    Sum of lengths of strings <= 100000.

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

    The sum of lengths of all strings is at most 10^5, not the length of every string. So the worst case should contain all the strings with length , something like 315.

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

    Total length of all string is 1e5. Incase n = 1e5, length of each string is just 1. Totally it is O(n).

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

    It was given in the question that the total length of the strings won't exceed 10^5.

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

    Why did you change your comment? Nobody answered your question so far.

    The number of operations is linear because every string is compared a constant number of times.

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

Thank you guys for making this awesome contest.The difficulty of problems is moderate for Div.2 contestants and have great and beautiful "solved" distribution.I kept thinking and implementing the whole contest.It's really exciting and fun.

Some personal experience: I got 2 RE on D for missizing the trie node pool and got 1 WA on C for a typo.When I start to handle E, I first thought to cope with it by splay tree(considering the difficulty of previous rounds) and failed to finish it.Right after the contest I figured out a better way(maintaining the position of original elements and do some interval add/distract, which can be completed in O(n) time because there is no online requests).

Long queue appear again in this contest.I guess this is caused by problem A.Maybe the special judge part in A make the judging machine laggy.

This contest is made by and for Div.2, this is awesome.Although the difficulty may seems lower than previous Div.2s(finish 3 and you and done, finish 4 for a high rank,finish all to go Div.1 directly), but it is really enjoyable for Div.2 contestants.

Hope you guys can make more great contests.

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

    I don't hate this contest. I'm just expressing my bad opinion about the problemset, which I didn't enjoy, authors did their best anyway.

    I do not consider this contest as "good". Here's a yellow point of view:

    -A was okay, like normal A

    -B was such a standard task...

    -C yet another DP with same pattern. There was even a pretty similar problem on CF once.

    -D come on, "code a trie" problem. There are many such problems in the internet. Seriously, even "find maximum xor" typed in Google would probably result in finding the solution immediately.

    -E that was a fun one. Nah, just kidding :P If coding N treaps is a model solution, then wonderful problem 10/10. MrDindows did something awesome, check it out!

    I'm not saying this contest was bad. But IMHO this contest should have been an Educational Round.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it 
      C yet another DP with same pattern. There was even a pretty similar problem on CF once.

      Which one?

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

This problem set is so much interesting. Really I enjoyed it to much.

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

Somewhat structured and verbose code for D: http://pastebin.com/Md2EtNXF (submission)

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

Can someone tell me why my solution to C (java) timed out?

I saw some other recursive solutions also passing, so did I make some mistake in the implementation?

Here's the code : 19801924

Thanks.

Edit : I got my mistake.

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

Someone can help me? In problem D, I'm use basicly pointers, in my computer it is ok, but in CodeForces gives Runtime Error.

Submission

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

Why my all solution change to 'skipped' and I out of competition ?

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

Why I get different answers between custom invocation and problem test?

In 19790402 I got WA on test 79, However, I thought I got the correct answer when I used Custom Invocation.

What the problem is???

I passed this problem by replace %ld with %d, but I do want to know Why I get different answers between custom invocation and problem test?

By the way, I'm glad to know how to cause this WA, since I thought there is no different between %ld and %d in GNU G++11 5.10 :)

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

Got 141 points, wow!

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

Thanks for such a nice contest :)

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

where is the problem set ?

→ Reply