BigBag's blog

Codeforces Round #373
By BigBag, 7 years ago, translation, In English

Hi everyone!

Codeforces Round #373 (Div. 1 + Div. 2) will take place on 23 September 2016 at 16:05 MSK. Please note that the timing is unusual.

This time tasks for you were prepared by me (Matvey Aslandukov) and my brother _XuMuk_ (Andrew Aslandukov). It is our first codeforces round and we hope you'll enjoy it. We want to say special thanks to Seyaua (Ievgen Soboliev), AlexFetisov (Alexandr Fetisov) and winger (Vladislav Isenbaev) for testing the problems, GlebsHP for his help with the contest preparation, and MikeMirzayanov for the excellent platforms Polygon and Codeforces.

Coincidentally, the date of the round falls on my birthday, so I am very happy that I can spend that day surrounded by our friendly community :)

There will be five problems and two hours to solve them. Traditionally, the scoring distribution will be announced later.

Good luck!

UPD1:

Scoring:

Div. 2 : 500 1000 1500 2250 2250

Div. 1 : 500 1250 1250 2000 2500

The problems are sorted by difficulty but as always it's recommended to read all the problems.

UPD2:

Contest complete! Thank you all for participating :)

Unfortunately, as noted Um_nik, many solutions of div.1 B task, including the author's, were incorrect. Now we are working on this problem. If we still manage to find the right solution and answers on pretests will be the same, the round may be rated. Otherwise, it will be unrated.

Thus final results significantly delayed. We apologize for the situation. If you have thought about the correct solution — write to us.

UPD3:

We made a decision to start system testing with the current solutions and tests. The question will be round either rated or not is still opened.

UPD4:

After considering different option and estimating their pros and cons, Codeforces team decided that the main factor to make a decision on whether the round should be rated or not is how much the bug affected the results.

In the second division, only two participants managed to implement the correct greedy algorithm for the original incorrect version of the problem D, thus we consider the effect of this problem on the final standing to be negligible. The contest for division two will be rated.

Things are very different for division one, as there were plenty submission to problem B and problems B and C took the most part of participants worktime during the contest. Assuming this fact we suppose that this bug affected the final results a lot and there is no way to consider its influence on each particular participant. As a result, the contest for division one will be unrated.

The only thing left to do is to apologize to the participants. We will do our best to avoid such situations in the future.

UPD5:

Congratulations to the winners!

Div.1:

  1. enot110
  2. Egor
  3. KrK
  4. UsedToBe
  5. IvL

Div.2:

  1. Adenium_Rose_Of_Desert
  2. sk_aswd
  3. haqkux201
  4. MemoryLimitExceeded
  5. immortalCO

Editorial is ready!

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

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

Happy birthday BigBag

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

    Big like for your phrase! CF :our friendly commiunity :) and Big like for your reason of happiness! : I am very happy happy big birthday. ;)

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

      a unrated contest on your birthday! :D hope to see contests on next birthday of your life! :D

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

        how many times do you submit it?)

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

          oh! there is a problem in judge! correct! :D

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

Why is the timing unusual? Quite early for working day.

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

    ah...For us is at 9:05 PM..It seems much better than 00:35 AM as usual……

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

If it could be delayed it would be better

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

I hope that this becomes the usual time, or at least please hold more contests at this time, so that my students can participate. The usual time 12:35am — 2:35am local time is too late for them.

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

    I totally agree with your idea too. The usual time (1:35am — 3:35am) is definitely harsh time to participate for our country. I'll be really appreciated if there are more chances to join contests for other time-zone coders:)

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

      Obviously in such a situation, there simply cannot be a fixed time that suits everybody. What would you do in such a situation? Definitely set a time that suits a majority. Some people have to face the circumstances because of low participation from that area and different time zone.

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

        You should rotate starting times, not pick a time that always screws the minority.

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

Duh, last contest was 6:35 AM for me and this is 6:05 AM, things are getting worse :P.

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

Contest will start at 20:05 UTC+7 in my area. Best time for me (y) . Happy Birthday, man!

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

tomorrow is also my birthday,a good time of the contest,it will start at 21:05,at the end of birthday,i can enjoy the contest.thank you for preparing the contest.

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

Contest will start at 21:05 UTC+8 in my area.So I can spend at most 5 minutes on road.

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

The only good thing of being a Syrian, is as much as the timing is unusual, It's always great in here :D

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

Something is wrong with the registration. Number of registrants there and there are diferent. + my registration was cancelled.

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

    I think you should reload both pages to get it fixed. It is OK!

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

Happy Birthday BigBag . Waiting for your dishes.! :)

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

Happy birthday.

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

BigBag Many many happy returns of tomorrow like tomorrow! :)

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

Many Happy returns of the day.

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

    Wow, now even wishing someone is wrong too(go on don't be shy downvote this too).

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

Double Comments post.

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

Happy Birthday BigBag.

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

Happy Birthday, BigBag!

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

Happy Birthday Matvey Aslandukov[user:bigbag]!!!!!

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

GLHF

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

Happy Birth Day, hope the problem will be amazing as your birthday gifts :D

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

We want your birthday treat by easy problems to solve and good ratings. And Happy Birthday to you BigBag.

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

As a Chinese student, late Codeforces round make my routine little bit hactic...Thank U so much for choosing such a nice time for the contest.. Hoping to gear some of my rating points and wish everyone a high rating~~ :) and happy birthday BigBag

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

happy birth day, bigbag

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

Happy B'day.. BigBag

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

HBD BigBag :)

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

Happy Birthday Dude !!!

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

Happy Birthday, BigBag! :)

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

It is my birthday too Happy birthday to BigBag and me Wish everyone can have a good rating after the contest (Ps:The time is very good)

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

Happy birthday :D

Where is the dishes ? :P :"D

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

Great timing! Wish everyone many accepted solutions, and happy birthday BigBag :)

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

You are advised to read all the problems :D

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

Happy Birthday BigBag! :P

So where is the scoring distribution?

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

Do I get rated if I have registered for this contest, but I'm not able to participate due to unstable internet connection?

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

    If you didn't submit anything, then you rating is not affected.

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

Problem A's pretests are so so weak!

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

Why Q, why!

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

submission in queue , it's been more than 5 minutes

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

    It seems the judge server is even down now...

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

    it seems BigBag is celebrating his birthday right now

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

What happened to the compiler? Submissions are in queue for almost 10 minutes already :(

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

LOL I've been watching the Status page for >10 minutes and NOT A SINGLE QUEUE has been processed????? :)

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

in queue for 10 min !!

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

Thank you for weak pretest in Div2. A. It feels amazing to hack people :D :)

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

[del]In queue! What is wrong?[/del] It seems to be fixed, thanks.

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

I have nothing against hacks on Codeforces, but when problems div2 A or B have so weak pretests, solving problems pales into insignificance. As I think, solving skill should matter more in final standings than hacking skill. So pretests for problem A shouldn't be as weak as we see.

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

    I agree. It would be nice if the system had a limit of hacks on a specific problem, so people wouldn't climb the rank so high because of silly details.

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

      or a hack limit for each contestant, in my room the first guy had 19 hacks !!! and left no chance for others to hack :(

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

        That's a great idea.

        because some people (like the guy in your room) gets 19 hacks and the solve A and take about 500 points that's 2400 it's like solving E at the start of the contest that's not fair to take 2400 points form only div2 A.

        that way the contests will be better and nobody will get to the top only from hacking.

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

          Maybe a reducing function of hack points with number of successful hacks for each problem...

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

It is about 20 pages of submissions in queue now!!

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

There is a mistake in the announcement. Problems are not sorted by difficulty :)

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

BigBag's Birthday is a HACK day!!

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

I had to resubmit 11 times in C until I noticed pretest 6 had really large number before . :/ rip 550 points

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

So many people solved Div.2 E. Weird, looks completely unsolvable to me :D

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

    Div.2 E is a great problem. You can consider the well-known method to calculate large Fibonacci Numbers , i.e., Matrix multiplication with doubling acceleration.

    Let the first matrix being A, second matrix being B, then you will get fi by ABi.

    You can build a segment tree maintaining the matrix B (or matrix AB, as you like).

    When facing the update query, simple commit an interval update — multiplying Bk to the corresponding interval of each segment tree node. Multiplying a single number into a certain interval is not a hard job, then multiplying a matrix into a certain interval will not be hard either. ( You should use lazy marking technique to make your amortized time complexity O(log(n))).

    When facing the sum query, simple extract the interval sum of matrix B (or simply AB, if you decided to maintain it rather than B) from segment tree and you are done.

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

      How do I use the lazy marking technique on a range? This matrix multiplication works only on single values, not sum of values, right?

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

        Hope this snippet helps.

        ls --> left son, rs --> right son

        lz is the lazy mark, update ready to pass to son.

        t is the segment tree node saving matrix AB

        init1(); is the function to put a matrix into identity matrix.

        void down(int rt){
    lz[ls] = lz[ls] * lz[rt];
    lz[rs] = lz[rs] * lz[rt];
    t[ls] = t[ls] * lz[rt];
    t[rs] = t[rs] * lz[rt];
    lz[rt].init1();
}

        Segment tree is maintaining a sum of ABi, which is equivalent to the sum of fi (simply extract the [0][0] item of the matrix).Multiplying a matrix to such sum is okay due to the associative rule of matrix multiplication.

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

        Here is a good article, explaining segment tree, at codeforces

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

        Given that fib(ai) = Aaiv where:

        You can use it this way:

        First, the sum of fib(ai) in a range [l, r] can be seen as:

        Now, fib(ai + x) is the same as (Aai + x)v, which is the same as

        fib(ai + x) = (AaiAx)v

        Now in order to add some value x to a range [l, r] :

        So, you can use lazy propagation storing the Ax in each node of your segment tree, and pushing it to the children of each node when needed!

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

    You can use the following property of fibonacci numbers and this property can be used to solve the problem using segment tree with lazy propagation.
    Fib(x + y) = Fib(x + 1) * Fib(y) + Fib(y - 1) * Fib(x)

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

DIV1 C is very well-known!

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

    Was this Fibonacci property shifting F(m+n) = f(m+1)f(n) + f(m)(f(n-1)) used in Div2 E along with segment tree in O(n logn * logn) I had kind of idea but failed to implement in time.

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

      Yep, exactly, consider the fibonacci matrix-vector multiplication:

      {sorry I don't know how to write in latex}

      ([[1,1],[1,0]]^n)*[F(m+1),F(m)]=[[F(n+1),F(n)],[F(n),F(n-1)]]*[F(m+1),F(m)]=[F(m+n+1),F(m+n)]

      since this operator is linear you can use it to update any segment range (I'll proof it later).

      By the way, the optimal complexity is O(n*log(n)), in each query you can just compute the matrix expo once, and use it to update segment tree.

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

      Yes. This was the property I was using. Successfully implemented it 7 minutes before the end. Idea was to store summation of F(ai) and summation of F(ai + 1) in segment tree.

      But Sublime didn't let me submit because it couldn't fucking detect

      +query(1,1,n,l,r);

      as a compilation error.

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

    Where did you know about it?

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

      I think it's subjective, for some people (including me) think this problem is well known, If you familiar with fibonacci, and multi data segmentree, for example this SPOJ-SEGSQRSS problem, then it's just a matter of coding skill (silly bug can hurt).

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

        No.. No.. Sorry for being not clear enough but it seemed that you get me wrong :))

        I just wanted to check if he learnt it from any books, tutorials... and if yes, then ask for recommendation :p

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

For B div1 problem, does O(nmlg) pass the pretests? is there any better solution?

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

    I have I believe.

    I have no idea how to prove that it can run faster than that. See this

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

      Now i understand my O(nmlg) solution can be easily implement in O(MTlg^2) that T is max(ti).

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

        Are you sure? Because not all machines(with same values of t) will start working at same moment.

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

          the second lg is for that!

          save all times they starts working after that all n machines filled for each t, so you can understand easily by a binary search that how many copy they will make after T seconds.

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

        I don't think, that it will pass, my O(MTlog(ans)) works in 3s.

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

          it is just: 2000 * 1000 * log2(1e13) * log2(2e5) ~ 2e9.

          4 seconds will be about 3e9/4e9.

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

            You forgot about % and / operations, which are too heavy for 2e9

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

          I don't understand this. Many (Most, infact) of accepted solutions (.. so far) are NMlog(1e12) itself. But mine failed :(

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

      Sad but true: I believe that mine works in O(nm), but it is too slow as the constant is quite big. I use nm divisions and O(nm) push_backs into vector and I have absolutely no idea how to optimize it. It works 6.5 seconds on my laptop on the max test.

      See this: 20865418

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

    I think that we can use Parallel Binary Search

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

I feel like Div. 2 C had really weak pretests. I noticed my two submissions in queue were wrong before they even got judged and they were both pretests passed.

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

    Pretests were supposed to be weak. Otherwise how could we hack? :)

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

I couldn't lock my submission for more than 10 minutes in the beginning of the contest. How was I supposed to compete against those who could do it?

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

Is C a segment tree with matrices? Couldn't make it pass till the end... First, I copied my matrix structure from my library and it got MLE #10. Then replaced it with my previously written code with vectors — TLE #11. Then replaced the vectors with arrays and boom — some strange big values on the example test :D :D

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

    I used Binet's Formula and store the numbers as and directly use a segment tree. Unfortunately, it runs in 4.5s on pretests, so RIP. (and I failed some submissions because of a bug in my segment tree -_- )

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

      Thanks, I knew my math knowledge is very poor! Hope you pass systest :)

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

      I used matrices and slow segment tree, but made precomputations so for each exponentiation I needed only one multiplication. On random maxtests works 3.5s on my laptop.

      Also, you can reduce exponents modulo 2000000016.

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

      Finally got it Accepted (I failed system tests :( )

      The change I needed was to store the value that I need to multiply with directly and exponentiating before updating the segment tree.

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

    It's enough to store 2 values. But yes, I did all by matrix(2x2) multiplication.

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

      I have always thought that my codes are fast and you passed it in 1.6s, maybe I should stop copying old codes :)

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

What's the solution of B? nmlog doesn't seem to fit in this time limit.

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

    Group the copiers by processing time; now nmlog is 1000mlog, which passes TL.

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

      how to group the copiers by processing time?

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

        At first you get this problem (by precalcing first n — 1 steps): find min x such that sum{i}{(x + b[i]) / a[i]} >= Y. Then you count this sum not with loop from 0 to n-1, but with loop from 1 to 1000.

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

          what are a and b here? I still can't get how to group them since not all copiers will start working at the same time so I think we should for every query find minimum X such that sum(floor( (X-wait[i])/T[i])) >= number_of_copies_needed

          since not all those have same T[i] will have the same wait[i] how can we group them?

          UPD: I'm still interested to know how the grouping is done even if the solution is actually wrong :D

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

            For every increase of T[i] in X, number of copies produced increases by exactly one for each machine. The different wait[i]s only matter for the last X % T[i] instants of time, and you can precompute how many copies are produced in those.

            Not that this matters anyway, since everyone used a wrong method to calculate wait[i] ¯\_(ツ)_/¯

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

              I've also group the machines for their unit times to produce one copy, then If they ask me for x copies, I just care about for every type machine all the possible reminder between x and unit time of these machines.

              This is my code: http://ideone.com/dSHk6e

              Precomputation takes: at most 1000*n every query takes aprox : log(10^12)*1000*log(average size of groups)

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

            Group by (t, wait).

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

          what are a and b here? I still can't get how to group them since not all copiers will start working at the same time so I think we should for every query find minimum X such that sum(floor( (X-wait[i])/T[i])) >= number_of_copies_needed

          since not all those have same T[i] will have the same wait[i] how can we group them?

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

      Oh... Bar is waiting for me. I tried to do something with right algebraic estimation. But no hacks could help me.(

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

      Ahh so simple!

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

    I got n * ti * log(maxtime), precalc first n possible answers, for another ai make binsearch on time to use. you can do it, because all n xeroxes will be working already and you know all the information about them(how much time for each xerox needed to create next copy).

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

What was Pretest 4 for Div2 C ?

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

    edit :i guess 3.1617 or something like that ! i too got 2 wa on same !!

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

      Am I supposed to get 3.142 as an answer no matter the value of t ? I got 10 WA on same, so I want to know. :P

      Update: I got it.

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

I am giving up my "blue" color as a present to BigBag. Happy Birthday :P

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

How to solve Div.2 D?

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

For div2C check these cases for yourself:

4 1
9.45

4 2
9.45

5 1
1.055

Answers:
Case 1: 9.5
Case 2: 10
Case 3: 1.1

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

    Also:

    4 1000000 99.9

    Answer is 100

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

      I had to resubmit because of a silly mistake. In 7 4 10.4447 Answer is 11 (Like Second Test of egor.okhterov ) And I became 500 from 160 :((

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

    EDIT: Didn't see post above me until refresh I hacked a couple people with this:

    10 1 999.999999

    which should just be 1000

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

    failed on 5 1 1.055... Why didn't anyone hack me?

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

      Most people's code was atrocious for this question. I had a hard time reading through the ones that clearly didn't round repeating 9s, let alone forgot to check for rounding the leftmost available number first.

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

        Yeah same. The code in my room either looked good or it was too confusing to read (especially since I'm not used to reading c++ code) so I didn't take the risk.

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

        Well, after a second thought and reading Dabagh's comment, I found that my code wasn't wrong, and it was my brain that was wrong.

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

      Seems you were not in my ROOM :P

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

    I got :

    9.5 10 1.06

    That's correct, right ?

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

      No, in Third one the answer is 1.1 you can round at first digit

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

    All these testcases work for me but my solution is getting WA on pretest 1.

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

    Why Pixar... My code got WR for your 2 and 3 tests... you ruined my mood :'(

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

    I pass all of these tests, but still got WA on pretest 5 :( Does anybody have any idea what was special about that case? I just can't figure it out... thanks :D

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

    Isn't case 3 = 1.1?

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

    No ! You are wrong! case 3 is 1.1 that you round at first digit!

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

      Sure, it's 1.1.
      I wanted to put answers fast in my comment and made mistake in my own test case ;)

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

    in your case 3 answer should be 1.06 not 1.1

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

during the contest, there was a large queue and it cost 15 min delay in my solution's judgement and unfortunately it gave wrong answer so just a waste of time !Shouldn't this contest be unrated if many others faced the same problem ?

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

    bro same here was attempting E after a and submitted at 1:24 in hope to solve other after that but got wa after about 20 minutes and everything got messed up

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

    It's not the first time.

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

    I think an extension in time would've been a good idea since the queue was clogged after around an hour.

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

Div1-C: When your solution get WA because you wrote (re*o.im+im*o.re) instead of (re*o.im+im*o.re)%MOD... I would have a sleepless night if that is the only mistake in my solution...

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

Problem E is so beautiful, kudos to author(s). Let me describe my idea, which should give TLE.

I think I have an O(n·d5) approach where d is the size of the alphabet. From each of n positions I run BFS and for each letter I store its type: 0 if none letter of this type was visited, 1 is some letter was visited, 2 if there was type 1 in the previous turn, and 3 if there was type 2 in the previous turn (thus, these letters affect other letters within distance up to 2). It's possible to maintain types. Moreover, each of n letters belongs to one of 85 groups, defined by letters within distance up to 2 (five letters and alphabet of size eight gives us 85). If I know types of letters, for each group I can say whether all its letters are visited or none are. Btw. this solution calculates the number of pairs for every distance, but likely (?) the intended solution also can do it.

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

Can someone who solved B say answer to test:
4 1
2 3 3 3
6

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

    Answer is 8.

    • Time 2: Machine 1 finishes the first copy and gives it to machine 2.
    • Time 4: Machine 1 finishes the second copy and gives it to machine 3.
    • Time 5: Machine 2 finishes the third copy and gives it to machine 4.
    • Time 6: Machine 1 finishes the fourth copy.
    • Time 7: Machine 3 finishes the fifth copy.
    • Time 8: Machine 1 finishes the sixth copy.

    Also, the answer would be the same for query 7, because at time 8 also machine 4 finishes its copy.

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

      You are wrong. Answer is 7.
      Time 2: M1 finishes 1 copy and gives it to M2
      Time 4: M1 finishes 2 copy and gives original and copy to M3 and M4
      Time 5: M2 fin 3 copy and gives it to M1
      Time 7: M1, M3 and M4 fin 4,5,6 copies

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

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

        My bad, sorry.

        I see you got WA. I hope the reason isn't that the intended solution is incorrect.

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

          No, I can't solve it with any complexity (even something exponential) because of this test :)
          My solution says 8 too.
          I wonder if author's solution is correct :)

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

    Wooooo, nice!

    Will organizers solution pass this test? If not, should that round be unrated?

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

      If organizers solution doesn't pass this test (likely), definitely unrated :(

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

      Maybe B should be taken out of the competition and then people should choose what happens with their rating — change or stay the same (if author's solution is wrong, ofc) so that people who solved C/D can get what they deserved.

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

        Then people who solved C/D would compete only against other who solved C/D (ofc. it's a big simplification).

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

        That's completely unfair to the people who devoted time to solve it.

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

          Well, one may argue that this problem is extremely hard so it's your fault to spend much time on it.

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

            Unless the problem setter fixes the solution (I don't mean to disrespect BigBag or dismiss his work preparing problems, but judging by what you, the reds, say, is very unlikely) nullifying its' score is pretty much ignoring everyone's time spent on that question because the setter's solution didn't consider everything.

            While not a perfect solution, I think nullifying the score AND reducing the time penalty for every other submission after B (as if everyone who got Pre-AC on B never spent time on it at all), would be the second best option to making the contest unrated.

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

          It won't be fair for them anyway, that's why I suggested that you can choose to have the round unrated, at least it may be a relief.

          PS: Errichto, if you are reading this, sorry for not replying, I just didn't understand exactly what your point is. I know B is important in the current standings but still, there is no optimal solution (I mean optimal solution for resolving the mess) for this, I am just suggesting :)

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

        Another possible solution is to make the round unrated for those who think they were affected by this test and for all others change the statement to match the authors solution.

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

          That's precisely what I suggest. You know, why would I claim not to be affected by it when I am about to lose ~100 rating points and how do they really know whether it affected me? It becomes pretty much the same situation, unless we assume that everyone is honest, which is obviously impossible.

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

      Well, no, the organizers solution won't pass this test. Moreover, we have never looked at the problem from this angle, as we had another formal model in mind. But of course, the statement matches your model better and now we have to think how to treat this situation.

      Any recommendations and suggestions are appreciated.

      Results will be delayed.

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

        ¯\_(ツ)_/¯

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

        lol so either I do bad or the round becomes is unrated xD

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

          Congratulations Tweety for candidate :D

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

        Why must system testing for other problems wait?

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

        Do not make div2 round unrated.

        Just my recommendation :)

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

          I see many downvotes but isn't it quite reasonable proposal? The issue affected much smaller percentage of competitors there, and many of affected will anyway get to div1 soon (if they are good enough to solve div2-D), right?

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

            It is not just the final opinion that is a subject to judging someone's post. For me reasoning is main thing to be judged and here I see no reasoning.

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

              That is deep :)

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

              Summary of most opinions whenever the question arises

              • "it should be rated" -> my performance was good
              • "pls make it unrated" -> my performance was bad

              (Before anyone accuses me of doing the same thing, I did ask for it to be unrated before I knew I failed the n=1 corner case in D :P)

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

        Well the pertests for A and C were very weak and people got a lot of points from hacking (some people got like 1900 and 2000 that's like solving D from the start!!!) and D is unsolvable the queue was not compiling for 15 mins.

        Hmmm... not sure what are you going to do but making it unrated is the best solution I think.

        note that a contest (I don't remember the number of it) was made unrated for a queue that lasted 20 to 25 mins

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

        IMO only justified decision would be to make it unrated. Which is kinda sad because many people have looked at the problem from exactly the same wrong angle, but there's no way to fix it right now.

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

        Any recommendations and suggestions are appreciated.

        Making a round unrated is a fine solution. I think that giving everybody 0 points for B (or maximizing scores with 1000) wouldn't be terrible, though I'm sure many will disagree.

        The number of strong people who didn't solve B is significant, so I think that it isn't good to make a round unrated for those who ask — there could be too many.

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

        That's funny :) Looks like I made a bug somewhere in a greedy solution and instead of carefully check the code I have found a countertest.

        Well, it is sad but I think this round should be unrated. Or for example unrated for all who didn't solve B (because it is hard to distinguish whether a person didn't came up with a greeedy / skip problem B or found the countertest).

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

          In Div2 there are only 13 people who solved D, so...

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

            ... So other people found the countertests.:)

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

              There isn't any hack for div.2 D, why rejudge for all submissions of div.2 D (WA and AC and all) isn't enough?

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

                the problem is that the main problem with this looking will become NP!

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

              Even those who can't solve B and C huh?

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

        Ruining the whole div2 round for a problem where the number of the pretest passed solution is 13 would be unfair though.

        giving them minimal points would be ok, they're 13 but don't ruin the whole round :/

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

        In Div. 2 over 5100 people submitted solutions. I think that's the highest record, isn't it? It would be very sad to make the round unrated.
        Plus in Div. 2 too few people solved it. We can make it unrated for them if they want, but for others that wouldn't be fair, as Errichto said here

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

        well as Any recommendations and suggestions are appreciated.

        1st I read D for 30-35 minutes got this test case wasn't able to think of anything and thought its beyond my level and left it after that I submitted my 1st solution at 1:24 and 2nd at 1:30 and 3rd at 1:35 long queue of solutiona were there.Verdict for all three came after 1:50 and sadly i got 2 wa and i had o time to correct them so in my opinion round should be unrated and now when i m looking my code again I see that I had done a silly mistake in E which could had been resolved if verdict had came on time.

        So, In My Opinion round should be UNRATED

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

        Statement can be changed so that machines cannot be reused once stops working to make the intended solution correct.

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

          Let's change constraint for n to 3.

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

            That's different. Everyone solved this problem including the author (and also many who didn't solve it IMO) have this constraint in their mind while every one certainly know n can be large.

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

              My comment with n ≤ 3 wasn't serious of course. Yes, most people tried to solve the version you described. Still, it's hard to decide what to do with the round. Changing the statement won't change the fact that some people tried to solve an actual version.

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

                I think not many, maybe only 1 or 2, tried to solve the actual version. I admit that it is hard to revolve this situation but there might be a better way than to just make it unrated.

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

                  This is just not true. Everyone TRIED to solve the actual version, but no one succeeded (including the authors).

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

                  If it's indeed 1 or 2, it's reasonable to make the round rated and indeed use the version almost everybody tried to solve.

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

              It is not like "people had this constraint in their mind". It is like "everybody thought it would be optimal to do it that way", which is substantially different.

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

                Yes, your description is more precise. I mean that even almost everybody thought it would be optimal to do it that way, but some did solve it that way while others didn't. We should not say their efforts are in vain.

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

                  As long as we do not add that constraint to description I would say there is no difference to how long will you follow a path if it is a wrong path.

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

                  I agree, I actually by mistake read N <= 1000 and M <= 1000000 instead and tried to solve that (though got WA).

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

            Try this

            3 1

            1 3 4

            7

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

              :(

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

              It is even better! Because we only send copies to other machines.
              It is the version mentioned by GlebsHP, isn't it?

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

                I don't understand mentioned where, but yes, we discussed this with GlebsHP. This test was inspired by halyavin, if it is important. Or I don't understand your question.

                UPD. I think I understand about what version you a speaking. Yes, we cannot just add to the statement that machines should run contiguously. We should describe the whole greedy algorithm to make things work. And Gleb is notified about this.

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

        I think it would be silly to make the Division 2 round unrated since only 13 participants actually got the pretests. I'm not really sure about the Div 1 round though.

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

        Ok, but did it really was a problem for a lot of people? How many of them could honestly say that it affects them? It would be very sad if this round will be unrated. Problems were nice.

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

        Maybe it's stupid suggestion but if you don't want to make it unrated then assuming people who realized that the greedy is wrong are very low and most people just assumed the greedy is correct, then just change the statement in a way to make the greedy correct and make the round rated. this will make it unfair for very low number of contestants (maybe only Um_nik )

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

          Now everyone will tell you that they came up with the test too. xD
          See

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

          I will be sad :)
          Just kidding. Maybe it is a good solution.

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

          So maybe the following approach: in div1 allow participants to ask for unrated round and see what will happen. If many will demand it, make the round unrated for everybody.

          And div2 unrated without any changes or with giving 0 for B for everyboyd.

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

            That looks like a good solution. I belive in honesty of div1 contestants.

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

              I was div.1 6 days ago. I think you shouldn't :-P

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

        Well, I think to judge any answer equal to or better than the ''solution'' to ''Accepted'' is a good idea. (As I think my solution should be AC if judged with the original tests. :-P

        Also, making this round unrated is OK.

        (I don't think a rated round with changing the score is a good idea.

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

        And no one is even discussing about long queues which affected some contestents very badly

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

        Any recommendations and suggestions are appreciated.

        Instead of making it completely rated make it partially rated. If dx is change in someone's rating scale it to some factor like 0.5x . It's a Win-Win for everyone. Unrating contest with such huge number of participants doesn't look good to me at least.

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

        If there be a poll about that this contest be rated or unrated, I think many people don't vote at all! because they didn't think on Div.1 B! There were many people working on other problems and this contest was exciting for them I think!

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

          Exactly! but If we ask in poll for contest to be rated or not. many will say unrated (for any contest). Most of us are never satisfied with our performance.

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

        Can we make it optional for people who submitted at least once on Div2D to have rated/unrated? Otherwise rated for everyone else.

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

          Well, having submitted a code for it at least once isn't a factor, what if someone knew this greedy won't pass and he/she spent his time to find a better solutions?

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

        Silly suggestion:
        Problem B is very hard. Its pretests were weak. The author decided to change his identity and move to another planet before posting the editorial. Everyone failed systest on B and up to this date no one knows how to really solve it. The round was rated.

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

          Since you are blue, are you referring to Div2B?

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

            For Div.2 there are no problems with D, that's why I'm saying B :-D

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

              My guess is most people who read Div2D/Div1B and confident enough to attempt on submission consist of only a small fraction of the population. I really don't see the point of making unrated for ~5000 participants

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

        Please don't make the contest unrated. This was my best ever Codeforces round!

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

        In my opinion, not giving anyone any points for Div 2 D and keeping it rated is a fine solution.

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

        I guess everyone used this line of thinking:

        "The obvious greedy solution is to make the fastest machines work. The problem is rated B and the limits are large, so the obvious solution must be correct, there's no need to think further or try to prove it."

        You could say the problem produced undefined behavior in many contestants :^)

        tl;dr make it unrated unless you have a solution that works on the current limits with the current statement and the pretest results are identical.

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

          But did the mistake affects you? Or you used the same line of thinking? If second one, than why to make this contest unrated by request is not a good decision? There was such a precedent in codeforces.

          I think that round should be unrated when it is impossible to participate for a big chunk of participants. Otherwise, we are just ruining round expierence for 99.8% of people (though, those of them who loses their rating would be only happy, no matter from what reason they lose it).

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

            B and C had the same amount of points assigned. Deciding which one to attempt first was basically a coin flip, until later in the round when you could see the number of submissions. Those who chose to do C first have a huge advantage purely because of luck, I don't see how it would make sense to adjust ratings based on that.

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

              I don't understand what are you speaking about. I don't suggest to remove B. I suggest to change its statement and make this round unrated for those who think that they lose some time/points because of B.

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

                Ok, so everyone who blindly submitted the greedy without proving it would get +rating, and everyone who thought about it would have the contest unrated. By doing that, you're rewarding something that probably shouldn't be rewarded.

                Remember that rating is always relative to other people — if everyone except you gains rating, it's the same as when you lose rating.

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

                  The question is: how many are there people of second type? If it is only Um_nik than probably you are overestimating importance of this issue. If there are other people who has problems because of this in first div. than they should probably mention it already. By the way, if Um_nik is the only one who noticed this problem during round, than probably coordinators should consult with him and decide what to do with the round

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

          That's meta-thinking is exactly what I hate in programming contests :(

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

          Beautiful explanation of metathinking! Thanks.

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

        Can you say what was the formal model?

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

    Thanks!!!!!

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

    Hi, I sleep over the contest, problem B seems delete from the database, someone could tell me what is the original problem? (Just content my curiosity)

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

      Given N copy machines. The i-th machine can copy one file in ti seconds (either from the original file or a copy). Given M queries. Each query asks us to calculate the minimum time to get ai copies of files if we only have the original file at the beginning.

      1 ≤ N ≤ 200000, 1 ≤ M ≤ 2000, 1 ≤ ti ≤ 1000, 1 ≤ ai ≤ 109.

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

Oh.. feels like the new trend on codeforces is tough Div2 D / Div1 B problems.. So much fun in the contest. Thank you BigBag for such great problems!

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

    I feel implementation wise E is harder. Its just that lot of people just know how to do it.

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

    the sarcasm is strong with this one

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

Can you solve Div2 E/Div 1 C using Range trees?

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

    Segment Tree

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

      Can you explain your solution?

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

    It should be known that Fibonacci number can be solved by matrices,[f_n,f_{n-1}]*A=[f_{n+1},f_n] where A is easily given. If we wanna know f[n], using matrices above can do; just [1,1]*A^n is ok. Then we use segment trees maintaining the summation of A^a[i] in a segment, the rest part is easy to solve.

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

I think this contest is so great,the C problem in div1,give me great suprise!Though I don't know how to solve it......

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

What was pretest 1 for A/Div.2-C?

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

Problem C test 7 100 109.998

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

The moment when you submit your first solution at 90mins. Then during the long queuing process realize that the solution would give TLE and have no idea to optimize.

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

this contest is making me a creative guy, not only the questions, but also about the new story that i should make to tell my teacher which I haven't wrote the homework spending my time for the contest :P

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

    Tell her that homework is useless and contests are at least very fun :P

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

HAPPY BIRTHDAY! BigBag too

but I was hoping that this round will be easy :(

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

awkward moment when the rank 1 in div 2 solves 4 problems whereas the rank 2 solves 5 problems.

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

can 3 1 0.9 be a test for div1A?

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

    why not?

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

    Yes, it could and the output should be 1

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

      my solution is getting 1 two but i think i could hack someone with this :(

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

    OMG! Yeah It can be and I don't output anything :(

    EDIT: Oh ! Thanks God! I just entered 3 0.9 1 instead of 3 1 0.9, It was a HORRIBLE moment!

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

    Can 2 1 .9 also be a test?

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

BigBag isn't your birthday done ?! we are waiting for editorial, please! (And also Happy Birthday :D )

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

how to solve div2 B ? i can't figure out it for a long time

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

    The string should be transformed to either rbrbrb... or brbrbr... For each you should calculate the number of blacks and the number of reds to be changed, and the answer is the maximum of the two because you want to maximize the use of the swap operation.

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

    Think of rbrrrb as 101110.
    We need to make it either 101010 or 010101. For any input there are always only 2 possible target strings(we need to figure out which one is the closest).

    Go through your input and compare each character in input string with these two target sequences. The sequence that has fewer errors wins and now you just count how many errors there are.

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

      how does counting the no of errors help?

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

        The number of errors is essentially the answer ;)

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

        If current character s[i] doesn't equal to the target character t[i] it means that it is
        1. either in the wrong position
        2. or painted in the wrong color

        In any case we have to apply some action to it.

        If there 10 zeros which are not on theirs places and 12 ones are also not on theirs places, we do 10 exchanges and 2 painting operations.

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

when can we start upsolving?

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

Div.2 contestants who solved problem A correctly could get a decent boost in rank after system testing :D

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

    Also for Div2. C , Pretests are even more weak!

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

I tried hacking with "2 1 .9" for Div2-C, it gave "Invalid Input" though.

Prob stmnt doesn't say anything about before the decimal.

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

    Actually .9 is not a valid number!

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

      Isn't it upto the representation one decides on. I just thought this part was ambiguous and debatable.

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

Why it stays Pending system testing..

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

    Because there is something wrong with the problem B. This contest may be unrated.

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

    GlebsHP said here that system testing is delayed because the round will probably be unrated because the problem setters put too little thought into problem B.

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

Please don't make it to be unrated for just Div2

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

this div2 round is "hack war" :D just 4 fun

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

Is this testcase valid for Div 1 A?

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

    No

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

    No, because there are no digits after the decimal points. The test 3 1 9.0 however is correct.

    Edit: This test is incorrect because the decimal representation of 9.0 ends with 0 but it shouldn't according to problem statement. Thanks

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

      It's guaranteed that the grade is a positive number, containing at least one digit after the decimal points, and it's representation doesn't finish with 0.

      It only said that there will be digits AFTER the decimal points, but nothing guaranteed there will always be a decimal point (?). Hence "9" is still okay... cmiiw

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

      It isn't corre