GlebsHP's blog

Codeforces Round #363
By GlebsHP, history, 8 years ago, In English

Dear friends!

We are glad to invite you to take part in Codeforces Round #363, featuring some problems of the VK Cup 2016 Final Round that took place in Saint Petersburg at the beginning of July. The second part of the problemset will be used to conduct Codeforces Round #364. Of course, we made some new problems to complete the set to fulfill the requirements of the regular round and it now contains problems of the appropriate difficulty for participants of any color.

We will obey the good old tradition to publish the scoring distribution right before the start of the competition.

We wish you good luck and an interesting contest!

UPD1. Scoring distribution will be standard in both divisions 500-1000-1500-2000-2500-3000 (yes, there will be six problems featured in both div1 and div2).

UPD2. Problems were prepared for you by MikeMirzayanov, Errichto, fcspartakm, qwerty787788 and Radewoosh.

UPD3. System testing is over, congratulations to winners!

Div. 1:

  1. Petr
  2. Egor
  3. jqdai0815
  4. semiexp
  5. gs12117
  6. Vercingetorix
  7. ilyakor
  8. Marcin_smu
  9. Gullesnuffs
  10. JoeyWheeler

Div. 2:

  1. Out_of_Cage
  2. lajiniunai
  3. tweety
  4. 1e18
  5. _Madiyar
  6. zoomswk
  7. bciobanu
  8. FlappyBird
  9. IHaveInt
  10. amsen

UPD4. Analysis is almost here

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

Comments Comments (194)
| Write comment?
»
8 years ago, # |
← Rev. 2   Vote: I like it -174 Vote: I do not like it

You are a bit of shit:D

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

Very inconvenient time.

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

    As my college has started now i have to wake up early and get ready for the class and late Codeforces round make my routine little bit hactic...Thank you so much GlepsHP for choosing such a nice time for the contest.. Hoping to gear some of my rating points and wish everyone a high rating :)

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

The way the TooDifficult has been improved with past rounds , one day sure he may defeat even Petr and tourist . Waiting to see that happen.

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

    Wow!! You made all three of them Headquarters. Mike has got competitions

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

      I still don't get it. Why is his title "Headquarters" ?

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

        Because he's in the Headquarters of Codeforces

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

        So that people don't compare themselves to him.

        Also, he's the fucking admin so he can do whatever he wishes. Hell, he can define his rating as touristsrating + 1 if he pleases.

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

Yesterday I thought I'll be able to participate in two CF rounds this week... Ouch :)

Can you add part about VK Cup to the contest registration message as well?

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

SRM 695 ends just 5 minutes before the CF contest.

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

    How so, by my calculations it ends 30 minutes before the CF contest? As TC contests are 1hr35min, not a full 2 hours right?

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

      Oh yes! You are right! I don't know why the Coder Calendar chrome extension shows that duration is 2h. :P

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

Wait but doesn't that mean that the contest isn't going to be rated?

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

    "we made some new problems to complete the set to fulfill the requirements of the regular round"

    "the requirements of the regular round"

    "regular round"

    (there, tried to make that as dramatic as possible)

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

At first I was very happy about the upcoming round.

Then I noticed the starting time.

...why 16:05 and not 19:35 as always?

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

Palindrome Contest "363" :)

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

Thank you for changing the start time! The usual 16:35 UTC is in the middle of work for me and I feel guilty doing CF at work :)

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

Who are the problemsetters of the round?

UPD: thanks for adding them into the main post.

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

I think you forgot about saying this "..I want to thank Mike for legendary platforms of Codeforces and Polygon. " :D ;

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

Many user will miss this contest for unusual time

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

    Come on, do you think users don't miss contests at the regular time?

    I haven't done a contest since 351. It's not because I didn't want to, it's because almost every contest is at 2:35am here.

    So yes, I'm a little bit salty that some people get almost all competitions at a decent time and then start complaining as soon as one competition is at a different time.

    (btw nothing personal to you, I just didn't know which comment to reply to so I just chose one)

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

      Hey it's even worse (4:35am) here in New Zealand ok.

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

      Actually I tried to say that regular codeforces round always starts at a common time. For this reason some user never check the time.

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

:)

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

Very convenient time.

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

Feels good to have an early contest. :D

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

The starting time is very good for those living in Eastern Asia, since most of the CF rounds ends at 2 AM for us. I'm really happy.

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

Wow,what a special time! It's very good for us.We dont't have to stay up late for the contest. :)

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

CF can consider arranging contests at different times regularly I think. It's a big community from all over the world and definitely some times are completely impossible for some people. I am in a time zone where usual time is at 9/10 PM and this contest will be at 7pm. Very much convenient for me but this is not the case for all.

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

Но могут ли участники "VK Cup 2016 Final Round" участвовать ??!!

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

Dont know if it is true or not, but if some problems are from vk cup 2016, then it is possible that some of us already know some of the problems!

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

    The participants of final round cannot participate in this round.

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

      And the problems of the final round were not disclosed?

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

Does this contest contain original problems of VK Cup 2016 Final Round or easier version of them?

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

for the sake of tradition, is it rated?

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

i hope the problems will be short like this entry

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

This VC Cup 2016 Final Round problems will be only at div1 problemset or only at div2 problemset or both :/

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

More and more comments like " oohh .. good time " ; " bad .. bad time "...))) Despite of fixed time for constest , it be always inconveniently for part of us , but convenient for other, or it is not clearly? :D ... The earth is round and here are contestants from each part of earth , it's impossible to set a good time for all.

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

    There aren't many competitors living in the middle of the Pacific Ocean. (And those that do aren't able to code during the day.)

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

This Time i will be in top 10.

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

So excited to participate in a Div.1 round after a while.

P.S: tourist is not participating, so it could be the one(if Petr participates)!

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

    How do u know tourist won't participate?

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

      He just asked his astrologer

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

      The participants of final round cannot participate in this round.

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

Rated or not?

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

No matter what the starting time is, The servers will be slow and by the time I'm able to see problem A 100 people would get AC already, as usual. :P

→ Reply
»
8 years ago, # |
  Vote: I like it +4 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~~ :)

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

How can i register ? It shows extra registration has time left, but how to register ?

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

Thanks

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

What is pretest 5(Div2D)?

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

    I got past it when I fixed the case

    4

    2 3 4 2

    Answer should be:

    1

    2 3 4 4

    so maybe it was something similar to that. Then I got stuck on case 8 :(

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

    some thing like it

    3

    2 1 3

    answer is

    1

    3 1 3 or 2 3 3

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

I solved problem A and B very quickly, but failed C for the rest of the contest. Anyone know what test case 6 for C is?

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

    I think it is 3 1 1 1

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

      Mine gives answer 1 on this but fails Test case 6.

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

      The answer is 1, Wright? (Ahahaha)
      (People who didn't understand the joke: don't downvote, okay?)

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

Will Petr overtake tourist today? He's in rank 1 of the standings !!! If it happens, it will be after long time (does someone has the data) for someone else to take 1 in overall rankings.

EDIT : He does it infact. :D Glad to see him at the top here.

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

Does anyone know the hack for Div 2 B?

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

    4 4
    ...*
    ....
    ....
    *...
    Also 500 * 500 star grid for tle test.

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

    2 cases:

    5 5
..*..
..*..
**.**
..*..
..*..

    Answer: YES 3 3

    3 3
...
...
...

    Answer: YES 1 1 (or any other valid position on table)

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

      1st one should be:

      YES 3 3

      and 2nd one should be:

      YES 1 1

      right? Or should the second one be No cause there are already no bombs so you can't destroy all bombs?

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

        The answer for 2nd one is Yes (we can put the bomb in any position). My solution will fail this kind of test :(

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

          :( That test case had me worrying the entire contest.

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

    A cool one:

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

I am not really sure why I am getting memory limit exceeded for Div2D. Can anyone explain?

http://mirror.codeforces.com/contest/699/submission/19249990 Thanks!

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

    Seems to me you getRoot(i) can not deal with the situation when cur is a "tail" to a loop. For example: 1 -> 2 -> 3 -> 4 -> 2 if you call getRoot(1), "start" will be set to 1, but you will never reach 1 again.

    The best way to deal with this (as I read somewhere on this site before), is to have two pointers, say l and r, l goes one step each time while r goes two steps each time. If r==l for some timestep, it is a loop.

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

      Oops , that should be it, thanks! should have simply used a visited array. But with the MLE I was thinking in the opposite direction :/

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

Why this O(n²) solution http://mirror.codeforces.com/contest/699/submission/19241016 didn't exceeded the time limit? My hack attempt failed :(

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

How to solve Div1-B correctly?

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

    I managed to pass pretest with union find — disjoint set.... but I think there may be some corner cases that I haven't handled

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

    this is how my solution work : iterate ocer all i : 1 -> n et for each i , if it isn' t marked " visited " , you use a recursion to search for his lowest unvisited ancestor : if you find a cycle in the tree ( same method as searching for cycles using dfs ) , you push its root ( highest parent ) into a vector v containing root of different connected componnents .... after iterating over all i , you sort v such that for i < j , cyc [ v [ i ] ] <= cyc [ v [ j ] ] to make sure that you make less changes and you consider v [ 0 ] as the root of the only new tree ...sorry for my bad english link : http://mirror.codeforces.com/contest/699/submission/19261372

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

    Good day to you, here's my approach:

    A) Try to find "ANY" root (node which points too itself)

    B) Re-edge all other roots to it

    C) Do cycle-finding dfs (Open+Closed states) from all nodes (going to parents). If a cycle is found, re-edge ANY node which is in the cycle to "chosen" root.

    If none root chosen in "A", then promote the first one found in "C" as "chosen root".

    Here is link to solution (anyway not self-documenting :'( )

    Don't hesitate do discuss more of it, if not understood anything or if you have doubts :)

    Complexity O(N)

    Good Luck & Have Fun ^_^

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

      I was thinking again, and you can avoid step "B", if you forbid visiting "chosen root" in dfs (because in "C", the self loops will do the "B" step automatically — silly me)

      New (but almost same) code.

      GL & sorry for the inconvenience ^_^

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

    I think it only have two case like number 6 (loop) and 1 (or a point) :)) :)) The first line ans is total tree — 1 (if have at least 1 tree like number 1) or total tree (if all tree like number 6)

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

I guess that we will have an another unlovely system testing with a lot of wrong answers on main tests.

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

Div 1 C — DP with matrices?

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

    Nope :D

    Since the operations are completely independent, try making them in reverse. Now question is "what is the probability that i is among the first k videos accessed in the first 10^100 hits?"

    But it is extremely likely that you will access at least k videos before you do that many hits, so you can simply ignore the last part and answer "what is the probability that i is among the first k videos accessed?"

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

      Well.. This seems easy. But what then? I got stuck on writing DP in less than O(2^n * n^2)...

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

        Well, you only care about the current set of "activated" videos and the next video you add, O(2n * n). But I think O(2n * n2), whatever the idea is, could theoretically also pass TL...

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

          2^n*n^2 is 4*10^8 so if the constant factor is large it will fail. In this problem we need double computation so it is not surprising if it fails.

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

      What do you mean by making operations in reverse? Could you elaborate? It seems to me that processing request in reverse is a totally different game.

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

        Well,the fact that moves are independent of each other helps much. Don't take into account the LRU game,the problem reduces to the last k different videos in the end.

        Take it this way: I want to know which are the last k videos <=> I want to know which are the first k videos looking from the end. BUT the moves are independent,so the probability of choices x1,x2,..,xn with fixed y1,y2,...,yk at the end is the same as the reversed one with fixed y1,y2,...,yk in the beginning.

        You can also see it as a bijection,pointing a sequence to the reversed one. If video i is in the last k videos of a sequence,it is surely in the first of the reversed one. So the answer for video i will be calculated correctly.

        Making the reverse problem may not seem different,but it is much easier. There is no game to apply now,as we calculate the answer for bit masks with at most k 1 bits. So no need to remember the order of videos ,which was a pain.

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

How to solve Div 2 D ? My approach was to count total components and number of such components which are cyclic among them. If all components are cyclic then answer is No. of components and then we can assign root to any vertex and then print parents accordingly. Now, if at least one component is non-cyclic then answer is No. of components-1 and main root can be assigned to the any vertex which is root in its corresponding non-cyclic component. But it fails on pretest 5. Any hints where I should think more ?

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

    I followed exactly your method and managed to pass pretests. Must be some small bug in your code. And I think my solution may also fail in main test. I can't shake off the feeling I missed some corner case :/

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

    You forgot about jellyfishes ( cycles with "legs" attached to various nodes on a cycle). You can't assign root to any vertex. It has to be a vertex belonging to the cycle.

    For example in this graph below you can't set 3 as root.

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

I think it is better if an example about how LRU algorithm works couble be added on the Note part of problem LRU.Just discribing it by works is a little bit ... confusing.
Like this :
We have 4 videos and 3 caches
the queries are {4,3,4,2,3,1,4}
at first the caches are 0,0,0
ask 4,then become 4,0,0
ask 3,then become 3,4,0
ask 4,then become 4,3,0
ask 2,then become 2,4,3
ask 3,then become 3,2,4
ask 1,then become 1,3,2
ask 4,then become 4,1,3

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

In todays contest, Div 2D/1B considered only sample 1 as non penalising pretest, which is slightly unexpected and odd. I think such cases should be mentioned in the Problem Statement(I got -1 due to this). It was also slightly confusing as I thought it wasn't same as Sample 3 and something else instead.

Jury's reply for this

UPD: Sorry, my bad. I always thought all samples were non penalising. I'm not sure why they wouldn't be? Is there a good reason behind this?

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

    The only time that you don't receive a penalty for a problem is on Test Case 1 (whether it be Compile Error, Wrong Answer, Time Limit Exceeded, etc.). Even if Test Case 2 is a sample and you get it wrong, it will count against you.

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

    In all problems and all rounds only sample 1 is nonpenalising.

    It says that somewhere in the rules, which you confirmed to have read when you registered for the round, so you must know them by heart, right?

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

What is N equal to in Div2A test8?

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

BLUE?

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

    Purple?

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

      Yeaaaah! Grats to your purple. Switching to C++ has made me more powerful (see my new pic)! No more random time outs like with Python.

      So close to solve Div2 F... but close is not solved (unless you are at Hackerrank where you sometimes get 72 out of 80 with brute-force)

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

semiexp and I think the testcase of F is weak.

In our solution, We check only the map is surjective, not injective. Our solution get WA on the case N=14, p[5]=7, p[14]=14, and others are zero. The answer should be zero but our solution outputs some positive value.

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

    It's my fault, I'm very sorry for that. I will add this exact test today, for upsolving. The already accepted submissions won't be rejudged (of course). If you have some more thoughts about this problem (any particular big tests that should be added?), please write PM to me. Thanks for sharing.

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

That moment when you have to switch to windows to hack, because your ubuntu doesn't have adobe flash player >_>

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

Isn't it a bit strange the N<100 for Div2C. I kept on thinking that my solution (which is correct) must be wrong because the time constraints can't possibly be so lenient. :(

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

Petr > tourist!!!!!

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

My solution for D failed for a really minor bug, such a weak pretests :(

P.S: Was backtracking intended? Mine got AC in practice.

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

Finally Petr Beats tourist

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

Now Petr Top Rated 3597.

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

Petr got rating 3597 now! It's rank 1!

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

So tourist has to settle for second on CF even after winning the official VK Cup Finals. #JustTouristThings

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

Can someone please help me. The output is correct but it says the formats mismatch. submission for div2-B

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

    I believe that is caused by the extra space at the end.

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

      Oh! But it never was there in other problems right? Dunno why is it called "format" then..

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

      Thanks man! It indeed was the problem. Corrected solution worked.

      I always thought the judge is lenient about "\n" and " ". But I did learn my lesson with 1 hr of contest time. Should be careful in the future.

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

        This shouldn't have happened. :( Judge should usually ignore trailing white-spaces.

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

          Is it possible to tag some admin to see this post so that they notice this and it doesn't happen to anyone in the future?

          1 hr of contest time is significant...

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

            I don't know actually if this will work or not:

            MikeMirzayanov, can you please look into this matter?

            And desikachariar, you may write a blog entry explaining what happened.

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

        Whether format about whitespaces matter depends on the checker of the problem. It's obvious that for this problem, the author needs to write a checker by himself.(The checker cannot just compare tokens like yes/no, integers or floating point numbers) And it tends to has less tolerance about wrong formatting.

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

It is jqdai0815 when you Top3 but still fell in rating..

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

So.... What is test 107 in problem D, i can't seem to have any idea why i am giving wrong answer

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

    Here is a shorter test, your answer is 25 but it is possible to get all 26:

    test

    The idea is that you have to first kill (9, 3), then it opens paths to both (6, 0) and (12, 0), and finally, you can get to (18, 0).

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

      Thank you very much for the test!

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

        To make (18, 0) safe, add something like (9, 4), right above the center monster. There will be 27 monsters, but only 26 will be endangered. (This is an answer to rev.1 of the comment.)

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

          Thank you very much! Both test cases work well with my solution, but I still get WA on test 5.

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

            Consider this example, where the last monster (5, 0) is unreachable: 2 3 1 0 3 0 2 0 4 0 5 0

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

when will be editoral?

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

Can someone explain me the dp solution for the Div2-C/Div1-A ?

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

    dp[i][0] :- Represents answer when you choose gymming on ith day. dp[i][1] :- Represents answer when you choose contest on ith day. dp[i][2] :- Represents answer when you choose to rest on ith day. Clearly, dp[i][0] = min(dp[i+1][1], dp[i+1][2]) dp[i][1] = min(dp[i+1][0], dp[i+1][2]) dp[i][0] = min(dp[i+1][0], dp[i+1][2], dp[i+1][1]) + 1

    Do this for all i b/w n-1 and 0. Finally answer is min(dp[0][0], dp[0][1], dp[0][2])

    http://mirror.codeforces.com/contest/699/submission/19242139

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

Petr _/_ won SRM,won CF round same day!

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

After seeing nice codeforces round problems eager to see nice editorial soon to learn from my mistakes. PLEASE upload it quickly can't wait more.I think other people are waiting too :)

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

Congratulations to Petr for becoming the highest rated person at the codeforces site. <3

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

Gosh, forget to set a good value of maximum in Div.2 Problem A gets me a WA.

My ratings...

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

Can Div2 D / Div1 B be solved using Disjoint Sets?

Could you please tell me how it is solved?

Thanks

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

    First find out that there can be any root of the given tree(if any make ans = -1 otherwise 0)

    ans = -1 is for when you have p[i] == i case , the root of the tree.

    For every i , check whether (i,p[i]) are from the same set , if it is then make the parent of i as root(if any or create this i as root ) and increment ans each time when you find they are from same set.

    Here is my code : 19259242

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

E was such a beautiful task <333

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

    Are you kidding? :D

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

    I'm surprised I was the only one who used Python's builtin time libraries :P

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

In B problem (Div 2) for test case:

2 2 .* *.

My answer is: YES 2 2

But the system said: NO

Why my answer is wrong?

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

    You are mistaken.

    The case is that your answer is NO

    While the right answer is :

    YES

    2 2

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

Still wondering why my code fails for test #45 of Div2 B. The report says "There is an obstacle after the bang". Can someone give a simple testcase that breaks my code? 19245284

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

    There are still a wall left after the bomb placed. E.g.

    4 4
**..
....
....
.*..

    give answer 4,2 and wall at 1,1 still survive. It should be placed at 1,2

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

Thanks everybody for participating, especially all those guys who were so glad to let me into top-10 without participating in a contest :)

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

Div2 D,
19261965 Where did I go wrong?
This test case has 0 roots.
Can someone please help?

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

    Good day to you,

    I'm not sure, whether this will help you, but here's a more simple TC, which it might fail:

    Input:

    4
2 1 4 3

    Your output:

    2
2 2 4 3

    Well it seems you counted "2" changes but made only one (2 is correct but well... :))

    Good Luck!

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

we need one more nice tradition: to announce when editorial will be published can't sleep without editorial :( awhhhhhhhhhhh sorry for my impatience

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

Finally the legander of tourist had destroyed. petr became the first in codeforces

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

I think copied code not only skipped your submission. I think should subtract rating of copier code. (sorry my bad EL)

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

Why does it seem that Petr has improved dramatically recently based on CF rating, while tourist seems to be plateauing a bit relatively? It is a bit surprising given that Petr is older, and one would expect greater improvements in younger contestants. Of course I guess question could be a bit meaningless given variance in contests.

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

Hello people, Can you give me a code, which shows my mistake in Problem 2, Division 2: http://pastebin.com/HsG1G5YV

The test that breaks it does not show fully.

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

    I just brute forced Div2 B. Store how many walls are on each row and column at each x and y, then iterate through each pair of x and y. If the amount of walls on the row of y and column of x (I use y for 'i' and x for 'j') subtracted by the overlap wall in the intersection of the row and column (if there exists one) equals the total amount of walls, then you know that pair of x and y is a viable place to put the bomb. If you don't find a working pair then output "NO".

    19242096

    Hope this helped. :)

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

      Thanks, plenty of good solution out there, but I am just interested in why my solution fails. Unfortunately, the test on which it fails is too long and codeforces have not written it at whole. Thus, I can only guess.

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

        Your welcome! There is a large variety of good solutions to learn from out there. As for your solution, I can't read C# so I'm not exactly sure what you are trying to do. Hopefully you figure it out. Debug will help out a lot too :)

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

Can anyone please tell me how to solve div2 D?

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

    Let us make the graph from the sequence given in problem. You can make diagrams and see that in any component there can be at most one cycle, I don't have a proof.

    Now for all components, when you get a cycle, just direct any edge of it towards any root(that is present in a component without a cycle). If all components have a cycle, just take any component and make any node on that cycle as root, and do the above things.

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

      The proof is simple. If a component is tree it would consist of n — 1 edge. So the maximum wrong edge in the component is only one.

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

So...Since I started programming, tourist was always on the top. But now something is different!

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

Waiting for Round 364 :)

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

Congratulations on semiexp for becoming IGM in only 7 rounds!

I guess that is the fewest number of participation on becoming IGM in CF history!!

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

Can I solve problem D by choosing the root ( any vertex such that (p[i] == i) ) , and choose any vertex from each Cycle in the graph and merge it with the root ? . Thank you in advance :D

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

    Yes , but not when there is no i such that p[i]==i. In that case, you need to pick root as one of the vertex forming a cycle.

    → Reply