STommydx's blog

Codeforces Round #457 (Div. 2)
By STommydx, history, 7 years ago, In English

Hello Codeforces!

I'm proud to announce that Codeforces Round #457 (Div. 2) will be held on 19 Jan, 14:35 UTC. The problemset is authored by southball, longhuenchan and me (STommydx). It is our first round in Codeforces and hope you all find the problems interesting.

We would like to thank the following people as the round would not be possible without their kind help: vintage_Vlad_Makeev for coordinating the round, Arpa for testing the problems and MikeMirzayanov for the great Polygon and Codeforces platform.

The contest will consist of 5 problems and you'll be given 2 hours to solve them. The scoring distribution will be announced close to the start of the round as tradition.

Let me close this blog post by answering the most frequently asked question in Codeforces. This round is rated for all Div. 2 participants. As usual, Div. 1 participants can join out of competition.

Good luck and high ratings!

UPD:

Scoring distribution: 500-1000-1500-2250-2500

UPD2:

We are extremely sorry for the situation for problem B. We are figuring out a correct solution for problem B. I hope you all enjoy the rest of the problems.

UPD3:

The round is over. Congratulates to the winners!

Div2:

  1. ustatt
  2. HanaElhami
  3. SorryBahadir
  4. ntv
  5. Om_nik

Div1+2:

  1. eddy1021
  2. chemthan
  3. nhho
  4. fmota
  5. ustatt

The editorial will be available tomorrow.

UPD4:

Editorial is ready!

  • Vote: I like it
  • -251
  • Vote: I do not like it

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

Is it the first cf round whose problems are prepared by Hongkongers??

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

Why it doesn't appear in the main page? UBD : its Now :D

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

Finally the wait is over.

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

Good luck, high rating

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

I wish a high rating for all.

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

enough time limit for problems

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

"Good luck and high ratings!"
Usually after these words there is always something very bad happening.

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

Good luck!

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

thi cho vui chứ tạch VOI rồi :(

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

    Next time, please use English or Russian in public Codeforces blog posts.

    Anyway, there will always be a second chance. Keep fighting, as long as your heart is still on for competitive programming. ;)

    (P/s: For those who don't speak Vietnamese, he said he'd play for fun, as he thought he'd fail the Vietnamese Olympiad in Informatics, which occured recently.)

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

    VOI is not the end, ACM is waiting for you.

    .... And strong teamates

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

They mentioned unusual start time in the mail....What's the usual start time?

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

The problem B's standard solution has a error.

Input:1 7

Output should be -2 -2 -2 -3 -4 -5 -5 instead of -2 -3 -3 -3 -3 -3 -3.

http://mirror.codeforces.com/contest/916/hacks/399042

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

    It is the same with 19 5 The answer shoulf be 3 3 1 -1 -1 and it is 3 2 2 1 0

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

    That might be why I always Wrong Answer on pretest 5 For the standard is wrong.

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

    Wow, this is a SERIOUS problem. The round should be unrated.

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

    Wow, I'm right. I've got stuck in B for 30 mins.

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

    Would you please explain the idea behind this?

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

      I got the wrong solution but got passed using priority_queue, just like the standard solution

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

      because -2 -2 -2 -3 -4 -5 -5 is lexicographically greater than -2 -3 -3 -3 -3 -3 -3, and there is no way you can get an answer with the largest number smaller than -2.

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

        Why -1 -2 -3 -4 -5 -6 -6 is wrong?

        -1 -2 -3 -4 -5 -6 -6 > -2 -2 -2 -3 -4 -5 -5

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

          y, which is max(Ai) must be minimized. In your case, y=-1, while in second case y=-2. Your y is not the minimum.

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

            I think B is only a greedy problem, try to change the number to binary system, and for a pow(2,m) can split to 2 pow(2,m-1) until the limit reached

            Am I right? Can I show my code here?

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

    Why it should be -2 -2 -2 -3 -4 -5 -5 ?

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

      Is it because those are negative numbers?

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

      It should be -1 -2 -3 -4 -5 -6 -6 I think.

      edit: no, need to minimize the max value as well

      basically a modification of the original idea should work: keep breaking into two till remaining length is greater than current count, i.e. it will lead to a minimum max value.

      Then, keep breaking the smaller end.

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

        max(-1 -2 -3 -4 -5 -6 -6)=-1

        max(-2 -2 -2 -3 -4 -5 -5)=-2

        -1 > -2

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

    agree!

    stuck on pretest 5, and i think my code is right.

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

      Exactly, I don't know what Pretest 5 is, but it seems to be very big because I received a RTE when I make my array size very small

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

    The link doesn't work. How did you figure out what the juri's answer is?

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

      The hacks link is invalid until the final standings are published.

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

    should output be -6 -6 -5 -4 -3 -2 -1 of 1 7

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

      no. -2 -2 -2 -3 -4 -5 -5 is correct.

      since -2 < -1 (the max value shoudl be minimized)

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

        with 1 7, I had the output: -2 -3 -3 -3 -3 -3 -3

        Actually I don't know what is the right answer

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

I presume you have overestimated the power of Div 2. A bit.

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

Obligatory rage comment about round being unrated.

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

How did people manage to get pretests passed on problem B? :D

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

    a priority queue solution passed.

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

      I was getting memory limit exceeded with priority_queue.

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

        Check for some runtime error in your solution. Sometimes undefined behavior causes element to be added indefinitely and hence the memory error. (Its just one of the causes, perhaps the real bug may be different )

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

          https://ideone.com/cyxHGX

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

            You are not at all dealing with cases where no answer is possible. Check out the case "13 2" in sample input of the problem.

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

              Sorry...I edited that...https://ideone.com/1HOrNz

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

                What is the problem? I see you passed systest. Can you please elaborate on whats the problem/issue?

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

                  The Problem is when there are negative values.....Input:1 7 Output should be -2 -2 -2 -3 -4 -5 -5 instead of -2 -3 -3 -3 -3 -3 -3...as -3 < -2....

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

                  Thats because you are always picking up the max element, popping it and putting in element-1 2 times.

                  How your queue works is as-

                  1 i -(input)

                  0-->-1,-1>>-1,-2,-2-->-2,-2,-2,-2>>> (similarly the 3 of the "-2" turn into "-3,-3" and we reach limit of 7,after which the for loop exits).

                  What you may try to do is, after the final size is obtained, for any 2 same elements, which are not the max elements, do this-

                  1. Remove those 2 elements, add 1 element+1.
                  2. Remove the last element. Add 2 "Last element-1" again.

                  So, what it will do is, for "-2,-3,-3,-3,-3,-3,-3", the steps will be like-

                  -2,-3,-3,-3,-3,-3,-3==>-2,-2,-3,-3,-3,-4,-4==>-2,-2,-2,-3,-4,-5,-5.

                  I think this should be correct (any improvements are appreciated :) )

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

                  @vijju123 you cant always do (1).

                  it might increase your max value. -2 -2 combining to give -1 as the first element.

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

                  What you may try to do is, after the final size is obtained, for any 2 same elements, which are not the max elements

                  I took care of that condition there.

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

                  @vijju123 should work

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

    If you write it to do lexicographic ally smallest instead of largest, you will pass pretests.

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

      I did it by priority queue, wrote the output with largest lexi and still pass

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

      absolutely true. I didnt even realize it until u said it

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

Un...f***ing rated?

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

Shit, if pretests of B are correct(?) why do you make round unrated?

My solution is passed and I think my solution is correct. Probably there is problem in checker that gave wrong answer on correct solutions which printed something different...

I found mistake in my solution xD

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

    I think the main solution in the problem package were wrong, therefore maybe not all of the pretests have correct answers.

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

    I suppose they were not + even if, there are hacks

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

    Pretest 5 is wrong

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

    Their solutions probably aren't, so that would affect anyone who wrote a right answer.

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

    pretests aren't correct. yours passed because both are same wrong answer.

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

I felt that B was a really bad problem...

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

RIP writer contribution score

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

    Currently it is : -57

    whereas it was +1 earlier (google cache), certainly it did fall to rock bottom.

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

Most unfortunate because of a serious issue. Anyway, still thanks for the contest, other problems were good! ;)

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

Round unrated but Interesting Problems. Making it unrated in last half hour of the contest is little disappointment.

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

Fucking shit..How the fuck some people solved B?

I went mad solving that problem.

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

    I think that problem C is easier than B. And both are really cool!

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

      Oh no..It doesnt matter. I wasted my whole contest just to get B accepted. I was not able to think of a logic to sort number lexicographically which does not exceed time limits.

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

      are really shit*

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

    Their mind works like the red coder who coordinated this round.

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

    emm... I can understand how upset you were after the round declared unrated, but don't you think we should keep a good environment for Codeforces, therefore, no f***ing... And sorry for my poor English...

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

uhhhhhhhhhhhaaaaaa, I have done 7 successfull hacks and this round will be unrated:)

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

    uhhaaaaa, i'm on the 4 place and this round will be unrated...

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

      I would back Div.1

      sss

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

      I think it can be rated for people who got increasing rating.

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

        It would be unfair. Your rating increased even though your code was wrong and ours was correct.

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

          Maybe you misunderstood me or I am really wrong, I mean the rating under the correct tests.

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

Even though the round will be unrated, I liked the problems a lot! Kudos to the authors!

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

3 problems got pretest passed and the round is declared unrated!

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

:( I was frustrated by lots of WA from pB...

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

My algo for B was absolutely right and the only problem was there in implement lex. sort which was exceeding the time limit.

I went mad when I saw some people solving it with time of about 15ms.

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

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

I hate of hearing "The round is unrated" in the middle of the contest and I prefer not to go on.

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

Kuttar baccha , notir pola , tor bal taina taina chirbo ajke , specialist hoite partam , bal falao ??? jotoshob

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

It's a shame, because D and E seemed like very interesting problems.

Apart from B, I thought the problem set was good (perhaps a little too straightforward with C). That said, I was going crazy trying to figure out how over 1000 people got B.

In any case, mistakes happen, so it's not a huge deal.

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

    lol, E is a boring implementaion

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

      Oh is it? I thought there was going to be some type of clever preprocessing involved. Oh well.

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

        it is boring preprocessing with finding LCA and updating on subtrees,I made it a lot of times

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

          How do you deal with 1st query?

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

          Ah, so it is LCA. My gut told me LCA but every other time my gut has told me LCA on a tree preprocessing problem it turned out to not be the answer lol.

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

          Is it? I thought it is non-trivial to update subtrees with a dynamic root, and it should takes a few case analyzes to compute the answers based on the pre-computed data structures.

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

            Updating subtrees with a dynamic root is an updating some more subtrees with a constant root

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

              Oh yeah, you are right. I thought it requires HLD to update but it seems precomputing the euler tour is enough.

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

      Not so boring. I learned quite a lot today and implemented new stuff.

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

    D is just boring persistent DS as well?

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

What was the issue in B? I did not understand the explanation.

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

My dream is to be an expert, and the day I have the opportunity, you destroy my dream :(

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

    You're really close to it, so don't worry. If at first you don't succeed, try try again! ;)

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

    No one can destroy your dreams. Except You!

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

    que drama do carai hahaha

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

interesting problem, anyway, could someone tell me the right solution of problem B? I solve B with the wrong solution, but get passed

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

You should not write at least the closing line of the blog. :(

→ Reply
»
7 years ago, # |
  Vote: I like it +254 Vote: I do not like it 
"Jamie is preparing a Codeforces round. He has got a idea for a problem, but does not know how to solve it. Help him write a solution to the following problem:"

Problem B. Jamie and Binary Sequence
*****
Unfortunately, the writers and coordinator solutions for the problem B are incorrect. The round will be unrated. We apologize.

D and E are pretty interesting (shoutouts to D) but I think they probably take too much time to code when put together in the same round.

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

    Best comment 2018

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

    Unrated — Predicting

    Google Chrome should have this extension

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

it was a realy good contest despite that problem B

→ Reply
»
7 years ago, # |
  Vote: I like it +33 Vote: I do not like it 
if(rank<=300)
    CF="UNRATED";
else
    CF="RATED";

:)

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

Any1 wanna solution for B..

Here it is

https://ideone.com/0HvwUB

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

Plz make the round semi-rated :(

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

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

Can D be solved using implicit persistent segment tree?

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

    Even the round is unrated, you shouldn't do this during the round. Am I right?

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

    Not everything that could be made persistent is a segment tree.

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

    Maybe, but i don't know how to deal with condition xi ≤ 109

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

    I think it can be solved by persistent trie on the values (x(i))

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

After a week of no contest We got "Unrated" one disappointed :(

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

Why turning the round unrated?!

Make it unrated for only those who got affected by problem B.

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

    yeah removing problem B from the contest is better than unrating the round

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

      removing problem B isnt a good idea someone who know the correct solution might waste lots of time on it

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

    It'd be unfair to those who spent time on problem B and not on other ones.

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

    how do you know who got affected?

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

    Do you realize you are selfish?

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

      CS Academy just did that on their last round

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

        you're right what CS Academy did is another good way

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

          The reason for you getting high rating is others find the problem is wrong but you not. That is why i speak you are selfish.

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

        but that requires a new checker immediately available for rejudging submissions.

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

        The reason for you getting high rating is others find the problem is wrong but you not. That is why i speak you are selfish.

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

    I wasted 80 minutes on B then moved to C and solved it in 5 mins.

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

So what will happen to problem B? Will it be deleted or will the solution be corrected?

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

So next time, Never ask if the contest is rated or not .. Who knows anyways xD

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

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

B is tough. C is lot easier than B

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

A and C got AC ;)

is this why B has some mistake :P

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

when you did your best on the contest and it's unrated!!

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

Unfortunately both author and my solutions for today's problem B were based on simple, nice (and incorrect) greedy idea so they are incorrect. Now we found correct solution for this problem, but answer for some pretests differs, so it's impossible to make this round rated. Of course I did some stress testing for this problem, but my bruteforce was really slow, so it was impossible to check solutions on most of the tests and greedy idea seemd clear and correct, so there were nothing to worry about. However the most simple greedy is incorrect here (it minimises y, but doesn't produce lexicography maximum sequence). You can check your solution on test "1 7". Answer for it is "-2 -2 -2 -3 -4 -5 -5". Of course we will desribe correct solution in the editorial. We are very sorry about it and will try to make everything to make this not happen again.

=========================================

К сожалению и моё и авторское решение к сегодняшней задаче B были основаны на простой, красивой (и неверной) жадной идее, поэтому они оказались неверны. Теперь мы уже знаем верное решение для этой задачи, но ответ для некоторых претестов был неверен, поэтому невозможно сделать этот раунд рейтинговым. Разумеется, я провёл стресс-тест решений к задаче, но мой перебор был очень медленный, поэтому было невозможно проверить решение на большинстве тестов. Кроме того, решение казалось очень простым и понятным, поэтому ни у кого не было повода волноваться по поводу решения. Однако наиболее простая жадность тут неверна (она минимизирует y, но не выводит лексикографически максимальный ответ). Вы можете проверить своё решение на тесте "1 7". Правильный ответ для него "-2 -2 -2 -3 -4 -5 -5". Конечно мы опишем правильное решение в разборе. Мы приносим глубочайшие извинения и постараемся сделать всё возможное, чтобы это никогда снова не произошло.

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

    is it correct for input 1 7 ? Yes -2 -3 -3 -3 -3 -3 -3

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

      No.

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

      lexicographical order

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

      He mentioned it already. Here " You can check your solution on test "1 7". Answer for it is "-2 -2 -2 -3 -4 -5 -5""

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

      sayedgkm output is same as mine, but it seems to be hard to understand what problem said now

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

    Even though I also made same mistake as the authors and you, and got AC. I believe that this mistake must be only made my idiots like me.

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

    My solution gives -2 -2 -2 -3 -4 -5 -5 which is correct but I fail on pretest 5 so I'm assuming it's one of the pretests that they got wrong

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

      how did you solve?

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

        Consider the binary representation of n For each number i that 2^i is in the binary representation put i in the answer list.

        now update the answer list as follows until it's size is equal to K

        while (len(list) < k):
  if (len(list) + count(maximums) <= k):
    remove all maximums and put two (maximum - 1) for each one you remove
  else
    turn a min element into two (min - 1) elements
        → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    I am getting the same answer for the aforementioned test. And I was getting wrong answer in test #5. Can you please reveal the pretest #5?

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

Unfortunately, the writers and coordinator solutions for the problem B are incorrect. The round will be unrated. We apologize.

WTF! -_-

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

I found problem B very interesting and loved the priority queue solution. I thought it was completely correct and had no clue it could be wrong, so I'm not surprised at all that authors did not realize the incorrectness of this solution too.

Please, don't be angry on them. I enjoyed this round a lot :)

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

Probably author solution fails in test n=20, k=4. Correct answer is {3, 3, 1, 1} while my passed gave {3, 2, 2, 2}.

Oops, sorry, didn't see above comment of vintage_Vlad_Makeev.

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

Those red in top 10 who got B correct should be moved back to Div 2.

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

1500+ people did the same mistake as the setter's solution?? :o

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

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

The round is rated....

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

"... Let me close this blog post by answering the most frequently asked question in Codeforces. This round is ..." 0-rated

On a more serious note, setters should not sub estimate easy problems. I had a similar experience with my problem KNICOV at CodeChef. The moral is that we have to double check greedy problems and have a formal proof.

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

Come on guys, no need to be so harsh.

Everyone makes mistakes. Maybe they had a rough day and didn't properly check their solutions. Look at the number of up votes for this announcement before and after the UPD.

It is tougher to come up with a quality question than to solve it so we have to appreciate them.

Good job guys!! Make sure you double check your solutions next time ;)

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

I think the correct answer is more important than rating.

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

Why "Idleness limit exceeded on pretest 1" in http://mirror.codeforces.com/contest/916/submission/34316902 ?

UPD: This happens because I am trying to read an integer in queries and removes

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

    side note: Wouldn't your memory requirement become quadratic? vector ?

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

      The vector just keeps a pointer, so no .

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

Can someone please explain solutions for problems D and E?

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

    For D, you can use a implicit persistent segment tree to keep the values of the words and another to keep the amount of words with value equals to X.

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

      i know persistent segment tree and implicit treap but what is this implicit persistent segment tree what are it's applications ?

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

    for D, i think just use pbds and some implement... but i didn't do it before the end of the contest

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

    For E, let's solve a simpler problem, suppose you just have to change the root and query the sum in a subtree, if we preprocess the sum of subtrees with the tree rooted at X, there's only three cases to handle when answering queries to a vertex V,
    if (current_root = V), the answer is the sum of all nodes
    if (current_root in V subtree), the answer is the sum of all nodes minus the sum of nodes in subtree of vertex that leads to current_root in the sons of V
    if (current_root not in V subtree), the answer is the sum of the nodes in the subtree of V

    To process the updates you have to find the lca(u,v) considering the tree rooted in current_root, the vertex is one of the nodes in {lca(u,v), lca(u, current_root), lca(v, current_root)} and then you process the update similar to the queries, to update a subtree and to query the sum in a subtree, you just need a bit and euler tour.

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

      Thank you. That is quite hard (idea and implementation).

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

    and these are very interesting problems for me

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

      I agree. D and E are very interesting.

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

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

How about the system test for B?

Can the first successful submission be considered as the last submission? (for time and for score)

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

problem setter make bug in problem B program and this round unrated if the solution of problem setter can accept, I think the problem is a good problem But problem D, E are very trouble, I don't think DS and long code and many details can be contest good if the round is div 2 , please problem setter use some hard and not template problem

so if the solution of problem setter can accept B, I also think this round should be unrated

the contest value > the contest rating :)

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

Nice contest dudes too bad it's unrated but the problems were good!

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

Alternatively u guys can fix B prroblem description to "Of all satisfied sets with elements sorted in non-increasing order, print out the lexicographically smallest one. THEN greedy sol would be correct.

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

    Can you please explain why this would work for lexicographically smallest one.

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

Common guys mistakes happen. Don't discourage problem setters

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

Is it good idea to change statement of problem B — only minimize max(a_i)? In this case problem is good for div2B and all solutions will get ok.

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

    Yes , Then the question gets quite easy right , just calculate the exponent of 2 for which (2^exp)*k >= n (i.e all k terms are exp initially) and exp will be the max a_i and decrease the remaining a_i's such that sum = n and print them .

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

Lesson to problem setters: If you are including a greedy problem, write a Formal proof of it. If you say after contest that the greedy solution seemed correct, I think it straight away implies that there was no formal proof written / verified.

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

Pretest 5 of Problem B gives me another chance to look my life again, how almost competitors wrong here?

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

    "It's a div2B so 90% of the time it doesn't require deeper thoughts" <--- Probably why

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

It was the first experience of contest setters. Sure, in the next time they will make better contest. Everything is ok.

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

You guys need to calm down a little bit. In the end, this is just one round that, in the long run, will have very little impact on your life. Everyone makes mistakes. There's no need to curse out the problem writers, who clearly worked hard to make interesting problems. I can't imagine the difficulty it takes to write a set of problems that have absolutely no flaws in them, and most people complaining can't either, since Div 2 people rarely write rounds.

It's not the end of the world if one round you were doing well on goes unrated. If your performance was part of a trend, you'll do well on future contests. If your performance was an outlier, then future contests would have corrected your rating anyway.

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

Because problem B and the unrated contest they got more than (-100) on this post

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

    Actually I still don't know how I can receive a WRONG ANSWER ON PRETEST 5

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

      we will see after testing ends.

      it's -135 now

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

        Before contest: About +190 or higher

        After unrated: wait for it...

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

why system testing is too slow ? -_-

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

For problem E, is it:

1. dfs the tree and build LCA and record the dfs order
2. build segment tree
3. do query

?

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

worked on B for quite a long time but can't solve. feel released now.

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

Over 250 test cases for problem A... personally I think 50 would be enough and thanks to that judging time would be much shorter :P

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

Can you please reveal the test #5 of problem B?

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

I wish I was the writer of this round, so I can get a lot of downvotes.

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

Very cool round!(no)

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

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

You end up in fourth in the contest and then the contest was declared unrated, so sad

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

    you know that you are not in div2,right?! :))

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

How to solve D and E ?

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

i don't get the point of putting Persistent Implicit segment tree in the D problem if someone has a decent template of it he can solve it in a little under 30 minutes i think putting a problem that required more thinking would have been better.

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

    i don't get the point of putting Euler Tour Tree in the E problem if someone has a decent template of it he can solve it in a little under 30 minutes i think putting a problem that required more thinking would have been better.

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

Don't you guys think that putting a persistent data structure problem on Div. 2D is not suitable ? I was going to compete in a Div. 2 contest for fun. However, got stuck on problem B and D........ :(

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

    I agree with you.I have no idea to D and E. They are not friendly to us newbies.

    I also made lots of small mistakes when I held a small contest in my school for the first time. So I believe the tiny flaws of this round are acceptable. I wish the authors,coordinators and testers will prepare a better round the next time.

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

    Coincidentially I was first exposed to "persistent" data structure problems was also a div2D.

    http://mirror.codeforces.com/problemset/problem/707/D

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

    I remembered I saw a problem which is several yrs old and is a div2E. It's just dfs order. Now it is dfs order + segment tree + lca. So we can conclude that the average intelligence of human beings is increasing right? haha

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

ваша тестирующая система некорректно работает, у меня ответы все правильные которые вы выдаете за неправильный ответ!!!

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

expected that situation after phrase "He has got an idea for a problem, but does not know how to solve it."...

→ Reply