oversolver's blog

Codeforces Round #256
By oversolver, 10 years ago, translation, In English

Hello, CodeForces community! I'm happy to tell you about upcoming 256-th round, which will be held for the participants from second division. Participants from first division can take part out of the competition.

I hope, for all this anniversary round. For me it is the first round in which I am the author, in this I will be glad to see everyone. Want to say thanks Gerald for help with preparing contest, Delinur for translating, and of course MikeMirzayanov for CodeForces project.

I am from Krasnoyarsk, and the hero of tasks will be our team talisman Bizon-the-Champion. Hope you like to spend time with him :) See you and good luck!

UPD. Few hours before the start. Score distribution will be dynamic (see more information here)

UPD. Round is over! You can find editorial here.

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

Comments Comments (108)
| Write comment?
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Your forgot to say something about the score distribution :)

This famous sentence in Codeforces community: Score distribution will be announced later.

Good Luck.

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

Such a significant round without T-Shirts? How real is this? :)

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

    i think it would be a good idea to give out T-shirts to the top 256 contestants.
    but then again, this is a Div-2 only round. so it might result in too many unrated users taking these places. not what we want to see.

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

      Deleted.

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

        T-shirts in div-2 round? RLY?

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


          ah, just wanted to leave this guy here :)

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

            alright, no more stupid pictures, sorry.

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

    I dont understand. Do they gift t-shirts? Plz give more info to me.

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

      They gave t-shirts at Codeforces Round #100 to the top 100 contestants. In fact, there were two participants at the 100th place)

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

        Ok. Thanks for info. Actually I had thought that they give shirts for every round, like codechef.com. I just asked a question. Why have i got -9 above?

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

          Do not try to understand logic of voting in codeforces)))

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

Why not codeforces round (1<<8) :[

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

    i had suggested this earlier.
    since my first "wish" was granted, i thought the second one would be too. but it seems not so. :(

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

I hope, for all this anniversary round.

What does this even mean?

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

    oh, I was weak in english

    I meant I hope for everybody this is significant round

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

It's very SPECIAL round! next 2x round will be 256 contests later, it means 256 * 4 = 1024 days, ~3 years!

UPDATE: It's last 2^2^2^2^2... round you will ever seen in your life :( next such round will be 65280 round later, it means 65280 * 4 = 261120 days later, ~800 years. still no T-shirts?

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

    A slight mistake: last ((((2^2)^2)^2)^2)... round

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

      basically, the last 22x round.

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

        :)
        1 << (2 << 2)

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

          i actually meant 224 (i.e. 1 << (1 << 4)), but u are also right.

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

Give T-shirts to top 256 contestants who are not unrated ?

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

    Good Idea.

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

      Ok not good. i hav understood. Because the div 1 group has better people and deserve "more".

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

        Lol. Chill man. You don't have to respond according to the number of upvotes/downvotes your post gets.

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

Again, please take the time to write a meaningful editorial.

→ Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it -30 Vote: I do not like it

Oh... A codeforces round by a BUG MAN (oversolver)
God bless us... :D

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

Please don't make the pretests too strong so that hacking is possible .

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

It's a special Round. I think it will be an interesting round.

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

    You really mean the round is interesting?

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

To be honest I was gray for nearly two months.Really upset story... So I just want to be unrated again and see if I can rise up from this new beginnig...

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

    You mustn't create more than one account. See Help.

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

      Yeah,you are right. I am so sorry to the whole CF community. I will turn to that original account :) though it has been gray for more than one month :P

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

        You participated in the round with this fake account . This account should be banned !

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

What happened to CodeForces ? Why the rounds are not beginning from 19.30 ? :( Why all the contests are starting from 18:00, 17:00.. 19:30 was good :)

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

    For some eastern countries 19:30 is not comfortable, because contest ends too late. However I would like 19:30, too)

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

Since this round is sharply before the "NOI" Contest in China, some use their minor account to participate in this round>_<

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

hope an easy contest ! :)

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

Top 20 this time around. No doubt about that.

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

From my experience I'm not lucky in dynamic score :(

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

More than 4000 people have registered! Isn't this the highest till date?

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

    Bang! Not exactly. A more ' popular' one is Zepto Code Rush which 4663 participants took part in :)

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

Very interesting problems which cover a lot of fields! And it seems that if you think deeply, you' ll get AC. What a pity that I waste too much time on D( and can' t ensure I' m right) which means can' t think over C and E :)

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

The pretests for the suffix question were too strong ! Not even a single hack

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

    Not exactly.

    1815 Pretest Passed

    1449 Accepted

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

in D, shouldn't the problem ask for the k-th smallest number (not k-th largest)?

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

Is it possible to solve C with segment tree? This was my idea:

Find the minvalue of the segment [1-N] and number of elements which are equal to minvalue, lets call it mincount. If, minvalue is smaller than mincount, it is better to brush horizontally. That way we remove mincount of numbers for only minvalue cost. Otherwise, better to do vertical brush.

If we are successful with horizontal brush, then we subtract minvalue from the segment. After that, some elements will be come 0. We the split the segment over the positions of 0 and repeat for the above for each new segment created.

So, perhaps doing this greedy was wrong? I got WA of Pretest 4.

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

    your implementation might have some issues, the greedy strategy is fine :)

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

    I did exactly the same and it passed pretests. By the way, it can be done (and it's easier this way) without segment trees.
    One my friend got WA4 because he didn't repeat the procedure for the rightmost segment created if its right coordinate was equal to the original segment's right coordinate.

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

    Seems like my assumption for using horizontal stroke only when minvalue <= mincount is wrong. Apparently, res = min ( using horizontal brush even when minvalue > mincount, using vertical brush ).

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

there was a ghost in the 5th pretest of B! what is the solution of B???

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

    Check your "automaton" case.

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

      if(a.find(b)!=string::npos) -> automation !!!! wasn't it enough? what is the result of "a" and "a" ? my code tells me array :( i think that's my bug, is it?

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

        Answer is automation.

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

        The problem statement states that

        Words s and t are different
        → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i agree.

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

      the main keyword was "only". I missed it for a long time and lost important time and points :(

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

No spoiler but please give some idea about intended solution for C and D.

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

    d — binsearch

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

    For D my solution is simple... I tried to devide the whole map into three right triangles, and sort all the numbers between two adjacent triangles...　Well it' s a little bit complex to explain the progress( and can' t make sure that it' s correct)

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

      can you give me the code? just paste it into pastebin.com, and give the link.

      thanks.

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

        According to the system test my solution is wrong so... :(

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

can anybody please explain how to solve D.. thanks

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

    General idea is binary search. You need to guess what whether a number X is the kth smallest number in the multiplication table. Hence, you need to count the total number of elements in the multiplication table which is smaller or equals to X.

    On the first row, there are min(X, M) numbers which are less than or equals to X. On the second row , there are min(X/2, M) numbers which are less than or equals to X. Generally, on row i, there are min(X/i, M) numbers less than or equals to X. Compute this number for every row to find out the total number of elements smaller than X.

    With the above calculation, we conduct binary search from 1 to 500000^2 to find the first number which has k numbers smaller than or equals to it.

    Something like 7137779

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

      Thanks! That' s clear enough! :)

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

      sorry iamnoobi, but i don't get it yet...

      what is X and M here? and i also confuse with the loop macro pattern in FOR(i, 1, n+1)

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

        X is the number that you are guessing as the k-th number, m is the number of columns. The macro means iterate from 1 to n.

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

      Thank you, that's a great explanation!

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

    This problem is a classic problem . It's called Young tableau , you can search it on the internet :)

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

      I googled but could not get how this is Young tableau. Would you explain DylanJiang?

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

Has anyone see someone hack problem B ? i didn't see a single one

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

thanks for the fast system tests

I am happy to know that B's points became 1000 rather than only 500

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

Changing Score is unfair!!

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

    This is dynamic score distribution. :)

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

    You can see this blog if you want to know details about Dynamic Score Distribution. :)

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

First time in top 20 ;)

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

Simple round but I messed it up big time!

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

Why hasn't the new rating been updated yet?

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

    be patient. it usually takes about half hour after system testing finishes.

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

.....So unlucky.....The "Verdict" is "skipped"....The all..

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

    Did you copy and submit someone else's code?Admins will change a user's all submission to skipped if the user cheated in the contest.

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

In problem B I was printing "automation" instead of "automaton". I was not able to debug this during contest :(

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

kindly improve your test cases for PRETESTS. For problem a(that was the easiest problem) i did a blunder still pretests passed. Look at the last line of this code.

if(cup%5==0)
s1=cup/5;

else if(cup%5!=0)
s1=cup/5 + 1;

if(med%10==0)
s2=med/10;

else if(med%10!=0)
s2=cup/10 + 1;

s2=cup/10 + 1; i was supposed to write s2=med/10 + 1; but in hurry i did this blunder. MAIN concern is that this code PASSED all PRETESTS. I think this is harsh. I know my mistake. But still this is really very harsh.

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

    since this didn't pass the system tests, you can't really complain too much.
    PS: this happens, don't get demotivated. u found ur mistake, that's the most important thing. :)

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

As usual, Country wise standings here [Unofficial participants not included]. Hugs and Bugs here.

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

Please make the pretests more comprehensive i.e introduce at least 10 pretests.

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

whats wrong with test case 36: boosss osos output is: both

test case 5: abacaba aaaa output is: automaton i think in test case 5: answer should be "both" instead of automaton my submission id is 7141893 plz correct me if i am wrong.

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

    By applying Automaton you can delete a single char. Now if we apply automaton on abacaba 3 times and delete b,c,b the resulting string will be aaaa. So by applying only automaton we can transform abacaba to aaaa.

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

Why my problem B only submitted once and pretest passed, but my submission was skipped?

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

I receive a TLE from my D solution. I have no idea how to make it better. Who can help me on the problem? My submission in the match: 7137602 I improved it later, but still TLE 7138146

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

    Oh, I have realized there is something wrong in my binarysearch, which leads to an endless iteration.

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

There are a lot of unrated participants in the top of the rank list again ! I think codeforces must have some rules like this : "Unrated persons cant take part in Div2 only contests."

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

Edit: I wanted to comment this in round 257

→ Reply