Wild_Hamster's blog

Codeforces Round #355 (Div. 2)
By Wild_Hamster, history, 9 years ago, translation, In English

Greetings to the Codeforces community!

Regular Codeforces round #355 for participants from the second division will take place on 1 June, 19:35 MSK. Participants from the first division are able to participate out of the contest.

It is my third round on Codeforces. Hope you will enjoy this round.

I want to thank Gleb Evstropov (GlebsHP) for help with preparation of this round and Mike Mirzayanov (MikeMirzayanov) for great Codeforces and Polygon systems.

Participants will be given five problems and two hours to solve these problems.

UPD Score distribution: 500-1000-1500-2250-2250

UPD Editorial is here

UPD Congratulations to the winners!

Div. 2

  1. fake_fake

  2. __Wind

  3. Mamedov

  4. dianaasau

  5. Sorry_Daikon

Div. 1

  1. Um_nik

  2. TimonKnigge

  3. vintage_Vlad_Makeev

  4. anta

  5. kmjp

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

Comments Comments (186)
| Write comment?
»
9 years ago, # |
  Vote: I like it -47 Vote: I do not like it

nice and short announcement I think one of the problems is about shortest statement :D Have a nice contest ;) Good Luck For All

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

    Do you have a children's Day today?

    As a 8 years old's black_red boy, I must be the king of this contest ((유∀유|||)) .

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

      Are you really 8 years old's boy? Why your profile displays you are in Sichuan university?

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

        Maybe he just want to get the last place in the contribution list by collecting down-votes.

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

      Probably born on leap year, celebrating birthday once in a 4 year, so its 32 years actually

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

Good luck everyone! I hope that I'll jump to Div.1 tomorrow and never return back to blue again...

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

is it rated?

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

    here he comes...

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

    You know, It's not funny anymore..

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

      I'm still giving them up-votes :)

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

    This joke has been over-used, and you have to come up something new!

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

Vanya is in the house

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

Yes, the round is rated :p
This is answer is for those who are gonna ask "Is this rated?"

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

I am trying to solve problem from your past rounds, but when submit ( 18173020 ) it say Denial of judgement

Is the package for this problem crashed?! what is the problem in my submission?!

UPD the problem fixed.

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

How come Wild_Hamster's profile says his last visit was 5 days ago when he posted this 11 hours ago?

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

A Codeforces Round in it's usual Time now that's new :D

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

This contest is going to begin at 00:35 in china.It is too late, and staying up late is not good for my skin.but I really want to be a blue xiaoai.

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

    Man, I'm in NZ and I have to get up at 4:30 for the rounds

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

      She is a girl

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

        There's a girl who's considering participating in a contest at 00.35 just to earn rating? I don't think so.. :)

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

          In fact, I am a girl.Why do you think a girl doesn't be eager for earning rating?

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

            Oops, I was wrong then! But you can't deny that there aren't many girls who would do such thing. Anyway, good luck for the contest!

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

          @Deemo because of your profile picture , I have always thought that you were a girl
          and I had crush on you :v
          am I the first man who had crush on you ? :p

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

            Yes, you are the first one that I know about :D I had a similar feeling for dreamoon_love_AA though, so I know how you feel :))

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

            I also thought Deemo is a girl. Then I saw his name...

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

            me too ! oops :D

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

      That's a pity.Hope you have a great advance.

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

    I play it, and feel not good too.

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

Nice & short announcement . And Hope to have some nice, short & easy to understand problem statement . And all the best to every participants for today's contest .

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

Let div1 round too. Otherwise, too many fakes will div1 by the participants.

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

Too bad it clashes with another Yury_Bandarchuk's div2 oriented contest on hackerearth (everybody knows it is held on the 1st of every month).

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

    Not everybody. I didn't know. And I tried to schedule contest in such time, that it doesn't clash with another contests:

    May 28 — Codechef&gcj

    May 29 — RCC&gcj

    May 30 — SRM 691

    May 31 — csacademy beta round #6

    June 2 — Hourrank.

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

Hope this round will be my first 4/5. God bless me ^_^

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

Your previous rounds had all math problems. I hope this time there will be more balance :D

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 5   Vote: I like it -40 Vote: I do not like it

    Yes maybe all problems related to data structures. Please no more downvotes I am sorry no data structures only maths.

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

      Why people are against data structures problem?

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

    Yes, I agree with you. Let's hope this time around, we get some nice problems of algorithmic nature. After all, this is Codeforces, not IMO.

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

The email I got said that this was going to be 6 problems in 2.5 hours. Is it 5 problems in 2 hours or 6 problems in 2.5 hours?

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

Lots of math problems are coming I guess :)

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

Wild_Hamster interesting profile picture :D

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

Any update about score distribution? Or is it standard?

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

what about score distribution ?

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

Links to hack submissions do not open in >ten minutes.

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

Omg, I'm so stuck on C. Thanks god it is not rated round for me.

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

Thanks very much for the great round! In my opinion, the only criticism is that the difficulty gap between C and D was too large.

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

How to solve D? Obvious DP gives TL 19.

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

    I get TLE on 19 too, and waste the rest time dealing with this, still can't solve it

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

      I too got TL on 19th case by dp.

      I was thinking to sort the elements of each type according to their dp value. while traversing we could stop beforehand if it is guaranteed that the other elements would be more expensive.

      I don't know if it would pass or not. But I didn't get any time to implement that.

      Please share your approach if it worked.

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

        I got TL on 19 too, and I tried to improve my solution exactly as you wrote — unfortunately I was in a hurry and got WA on 10 due to some mistake. But I believe it should be good enough.

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

          I tried after the contest got over. Still stuck on 19th case

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

        This was my solution during the contest but it was TLE as well :)

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

    I was too slow to code it, and never coded Dijkstra before. But my approach would've been making a directed graph with starting point having edges to all 1's, all 1's having edges to all 2's etc. and then do Dijkstra from start to P, that should work right?

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

    I am using a similar approach as yours, the limit will be the case where p = 3 and there are 45000 elements with p = 1 and 45000 elements with p = 2, in this case it need >2s to finish so it will be TLE. To speed up the algorithm, keep the points with p = x grouped by their x-coordinate and y-coordinate respectively, then for each point with p = x + 1, we dont need to traverse all of the points with p = x, we can traverse each column and each row and find the best one using binary search, so the total time will be O(m*n*max(m,n)logn)

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

Are 99% of hacks on Div2B are of integer overflow?

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

Waiting for my D to fail...

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

How to solve D faster then O(p*(mn)^2)?

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

    I wrote solution in O(n*m*n*log(m)). But it's not fast enough :(

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

    I had a solution with time complexity O(p*(n*m)), but it failed at pretest :(

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

    I think I got O((mn)^2) by just finding differences between n+1 key and n key, still not enough (for Python at least, I think 45000**2 might be OK for C++)

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

      It won't be enough even for C#/Java/C++.

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

        Even for magic, 'cos 300^4 is 81*10^8

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

      I think you solution is actually O(n^3) ,just like mine, but this is too slow even in c++. I get TLE in case 19 too.

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

        N^3 should pass easily in like 100ms on worst case. So probably it is not N^3.

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

          I think the worst case is p = n = m = 300, and 300 chest for each type. But it's just intuition, Maybe case 19 is something else

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

            It depends on algo used.

            For some algos worst case will be p = n = m = 300, 44851 chests of two types and 1 chest of every other.

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

              44851 chests of two types you are right, I didn't notice this case..

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

            Worst case is when n = m = 300, and p is 4-5, so it's 20k * 20k * [4, 5] > 1.6kkk

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

              you are right, I'm too simple

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

I think I missed D by seconds!

I hope my solution doesn't pass. I was taking the limits small.

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

    I was getting TLE on 19th case. How did you manage that?

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

So uh, how to solve D? I was trying to think of DP but couldn't.

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

    IMO , for a point you need not check every Other point with value 1 greater. Check all the rows and columns that form a border across it!

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

    DP + Square Root decomposition

    In the optimal path, once you have collected the first k keys, you should move to a square to collect the k + 1th key. Thus we can divide the entire matrix into layers where ith layer consists of the co-ordinates of the matrix where such that a[x][y] = i.

    Maintain a value for each of these points -> the minimum distance traveled to reach it.

    Now we need to do transition from layer i to layer i+1. A brute force implementation for transition could take O((nm)2) time. Thus we take two cases -> If the size of the previous layer is greater than (nm)0.5 and otherwise. If it is smaller than (nm)0.5 we can do bruteforce, else we do a BFS with careful book keeping. Overall complexity O((nm)1.5)

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

      Hi, sorry if this is a stupid question, but what exactly are we doing in the BFS. I mean if we're doing BFS to find cells of the next layer wouldn't it still be wouldn't the BFS still be O(nm)? I read the editorial and it uses the same approach but I don't understand it.

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

        A BFS from layer i to layer j will take O(nm), but you only do it if layer i is large (larger than sqrt(nm)). Since the total number of chests is nm, you can have at most sqrt(nm) layers with size sqrt(nm).

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

    O(m * n * m * log(m * n)) with list + binary search and a little lucky!! :D :D

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

Problem C was very hard to understand. But B was hackable so I liked the contest

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

I was constantly getting wrong answer on pretest 4. Any possible corner cases? I thought of all possible scenarios, could not find anything :(

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

    same here.

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

    Test case 4 is 5 5 5 4 2 1 2 3 3 4 4 2 2 3 4 1 2 4 2 1 5 4 2 4 3 1 1 2 If we start with 4 key then we can straightaway go to key number 5 with 5 moves!! Why is the answer 9 then?

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

    I WA in pretest 4 and after that I read threads again: "All key 1 open" (not (1,1))

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

Problem D: I have Dijkstra in O(mlogn) approach based on std::set which don't passes 19th pretest. Starting vertex is cell of P type. Please any help, comments about my owful code 18199256 or your solutions for this problem.

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

    The number of edges is very high, dijkstra is too slow.

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

D seems like some pro shit. When's the tutorial getting posted?

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

What am I doing wrong at problem C?

https://ideone.com/fOMtB2

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

Nice round, I have already failed C in system test in the last 3 rounds, hope this time I can be lucky :D

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

How the hell there are more submission for D than E?

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

    that feel when didn't even get to read E because I was stuck on D. :(

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

I really hate when I miss to notice integer overflow, then get hacked 10 minutes before contest, after which I have to resubmit, thus losing 350 points. The only good thing is that after this I managed to hack one other solution :) so I got 100 points back

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

    It's better than not getting hacked at all and never realizing it :/

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

      You're right, but still it is better to notice overflow as you write the solution, not 1:30hrs later

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

        Annoying how a simple overflow can change my ranking from 150 to 1000

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

if D turns out to be simple i'm going to shit brix

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

I can't understand C

is there anyone that explain for me?

i spend most time to understand it..

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

    You get very long number in input. You should translate it in binary representation (6 bits per char in input, total max of 600000 bits), lets call it A.

    After that you should eval how many unique pairs of (X, Y) exists, so that X & Y == A. Where & is binary AND.

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

    Find & of all pair of values from 0 to 63 and then calculate answer for each character accordingly. Submission

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

    Same here, i couldn't understand it until the last 15 minutes, and got Accepted in the end :D

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

In D i was misunderstanding that it has the (1,1) chest initially.That passed three samples....TAT..

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

    *chest

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

    Same here. I tried my effort to find the nearest p+1 in eight directions for each p just like Manhattan spanning tree, submitted just before contest ended, and got WA on test 4 :(

    UPD: It seems my solution doesn't work, which got WA on test 14 :(

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

      There will be some mistakes? I thought that the proof of Mht mst based on the points were not in order. But in this problem the points are in a specific order.

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

        Of course it is incorrect, which would fail when the optimal path is on a straight line.

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

      I tried the nearest 200 points for each p , ans I got AC , I think perhaps you should try more points :)

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

How to solve problem C?

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

    Realize that.

    1 & 1 = 1 //One way to get 1

    1 & 0 = 0, 0 & 1 = 0, 0 & 0 = 0//Three ways to get 0

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

    For the pair of strings to find a and b Lets understand that if a&b=1 , then there would be 1 in both. For a&b = 0, it can happen in three ways 00 ,01,10. As number is less than 64 , it can be represented with 6 bits. So you should check the total number of zeros in every number of 6th bit representation. So ans = 3^tot.

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

    First u need precalc all the possible results, and count it in a map(or vector) Finally, multiply all the values (mod 10^9+7) example:

    s = xyzw

    ans = (m[x]*m[y]*m[z]*m[w])mod (10^9+7)

    18194600

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

I love the contest! Surprisingly most of the problems have a simple way to solve :D.

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

    Oh my god your username is the GREATEST. LOL

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

Correct me if I'm wrong.

Task E: nothing prohibits non-positive d (it says three integers, not positive integers). With non-positive d set of items under given constraints is empty. So, technically, answer for all zeroes must be one and not zero?

My solution that prints 0 passed, and I think some solutions that printed 1 failed, seems not fair if I'm right =)

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

Problem B says, that each second Vanya does the following:

1) If there is at least one piece of potato remaining, Vanya puts them in the processor one by one, until there is not enough space for the next piece.

2) Processor smashes k centimeters of potato (or just everything that is inside).

So at each second Vanya checks if the next piece can be accommodated. Most of the solutions that I saw, first add whatever can be accommodated, and if at i_th index, ar[i] + remainingAmount > h, they add to the answer remainingAmount/k. But it is also possible that after some seconds that is less than remainingAmount/k, we get enough space to accomodate ar_i. It is clearly given that Vanya does the above two mentioned things each second. Do both of these solutions give same answer? Am I missing something?

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

Can you please explain the time complexity of problem D?

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

How do you people solve problem E?

I thought 10003 divided by a good constant is just fine for three seconds, but my initial attempt took 2x more. Eventually, I managed to squeeze the O(n3) solution into the time limit. Perhaps it's even easier with a superior optimizing compiler such as GCC.

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

    For each center binary search the maximal radius such that you don't pick up any zeroes. Count the number of 2's and 3's in a cross with this radius. Use partial sums to quickly get number of 0's, 2's and 3's in a cross.

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

      Thanks. That's and not much more code than O(n3) with the 45 degree rotation — nice!

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

I will not use int anymore, I will write all my future solutions using long. this is the second time I fail system test because of using int. is there any disadvantage of using long?

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

#fastreading

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

I think that D sucks a lot. The time limit was chosen very badly. Some solutions with the same complexity: O(n*m*max(n,m)*log(n*m)) passed and some failed because of that.

Besides author provided theoretically strong pretests. People got busy trying to improve their solution as it was getting TLE on pretests. It created an impression that the pretests are strong in terms of performance and once you pass them you should just worry about the correctness.

Surprisingly I spent some time optimizing my solution just to discover that it was failed because of tle in the final tests.

Either time limit should be higher — 3 seconds or pretests should be weaker so that nobody wastes their time improving something which was going to fail anyway.

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

    I didn't analyse many solutions and you may be right about adjusting TL. But, I don't agree about pretests. It's awesome that pretests were strong and it should help many people. People with slow codes can check their solutions with Custom Invocation anyway. So, in general they shouldn't do it not to waste their time? It's risky to implement complexity which won't obviously pass and one must take it into consideration. I don't see why telling someone "hey, your solution is wrong" is bad. I know that later there is info "hey, your solution may be OK because passed pretests" but it doesn't guarantee anything.

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

      I think that I was one optimization away from the acc, so if the pretests were stronger it would be also ok.

      The problem is that they were chosen in such a way, that they were engaging people in solving this problem. Contestants were spending time trying to pass pretests instead of solving other tasks. It was a false help. If they were stronger it would be a real help. If they were weaker, nobody would complain about it as passing pretests guarantees you nothing. But also nobody would bother spending so much time on this task.

      Besides we are speaking about n*m*max(n,m) (obviously pass?) and n*m*max(n,m)log(n*m). In my opinion both should pass easily. If somebody is trying to differentiate solutions worse by factor of log it means that he wasn't confident that the problem was difficult and interesting enough, so he made time limit more restrictive.

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

        It was a false help for some participants, a useful help for others (I had many things wrong and catched them one by one, thanks to pretests). That being said, I see your point now. But I think it's hard to adjust pretests so perfectly.

        Unfortunately, if you want to allow O(n3·log(n)) to pass easily, then it may also allow squeezed O(n4) to pass. I think that the chosen constraints were ok — there is intended O(n3) (passes easily) and one may risk and write O(n3·log(n)) carefully, to also get AC. Fine for me. One may get TLE a few times but in the long run it isn't a big deal and I don't see a better solution.

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

Okay Wild_Hamster, you beat me this time, well done!

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

    it's your 2nd contest , take it easy , it took me 55 contests to get here and you just did in 2 , you're a monster hahaha , div1 is waiting for you next week good luck .

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

Thank to all for such contest. It was really unexpected thing for me to be in top-10. :D

I was writing it normally, solved ABC, then got TL #19 on D. Then I thought: "I need to get maximum points here" and started hacking. :D When I opened my room there already was a guy with 1 hack. After 1 refresh I saw +2 near him. Then +3 were near me. :D And when I only refreshed my page, it said "Sorry, your balance is X, you can't surf internet anymore". As you already understood, X is some negative number. :D I ran from home to nearest terminal, which is not near my home, :D put cash for my dear internet provider, came back, made 2 more hacks, optimized my TLed D solution in some shitty way and it passed systests. :D

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

Perfectly right submission http://codeforces.net/contest/677/submission/18209483 calculating 3^n. WTF test 9 has no input. I was lied. they said length was more than 1? In contest solved two problems but shouldve used long for t in 2B but i used int for a perfectly correct answer :(

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

    The input is a lots of underscores ('_'). You should have processed the input char by char instead of using slow BigInteger class.

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

is there anyone that explain to me D?

testcase #4

5 5 5

4 2 1 2 3

3 4 4 2 2

3 4 1 2 4

2 1 5 4 2

4 3 1 1 2

why answer is 9?

what i understand is 2: (1,2) -> 3: (2,1) -> 4: (2,2) -> 5: (4,3) thus ans = 7

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

    you need to go to 1 at (1,3) first

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

Congratulations to Div. 2 user fake_fake who wins the round! 1st place from the 3rd try! Nice progress, man...

→ Reply