Блог пользователя GlebsHP

Автор GlebsHP, история, 8 лет назад, перевод, По-русски

Дорогие друзья!

Мы рады представить вам Codeforces Round #363, который пройдёт с частичным использованием задач прошедшего в начале июля в Санкт-Петербурге VK Cup 2016 Final Round. Вторая часть задач чемпионата будет использована при проведении Codeforces Round #364. Разумеется, мы дополнили набор задач до полноценного раунда Codeforces, чтобы каждый мог найти задачу подходящей сложности, которая ему будет интересна.

Не желая изменять доброй традиции, мы опубликуем разбаловку непосредственно перед началом соревнования.

Желаем вам удачи и удовольствия от решения задач!

UPD1. Стоимости задач будут стандартными 500-1000-1500-2000-2500-3000 для обоих дивизионов (да, в обоих дивизионах будет предложено для решения шесть задач).

UPD2. Задачи были подготовлены для вас MikeMirzayanov, Errichto, fcspartakm, qwerty787788 и Radewoosh.

UPD3. Системное тестирование завершено, поздравляем победителей!

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. Разбор уже здесь, планируется в скором времени перевести его на русский язык.

  • Проголосовать: нравится
  • +444
  • Проголосовать: не нравится

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится -174 Проголосовать: не нравится

You are a bit of shit:D

»
8 лет назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

Very inconvenient time.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится

    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 :)

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится -10 Проголосовать: не нравится

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.

»
8 лет назад, # |
  Проголосовать: нравится +39 Проголосовать: не нравится

Я так понимаю что призыв не участвовать в ближайших 2х раундах тех, кто участвовал в онсайте отсутствует, потому что он очевиден.

Тем не менее, единственное упоминание что в этих раундах будут задачи с финала VK Cup только в этом посте. Никакого предупреждения в соглашении об участии нет и зарегистрироваться на раунд мне тоже дали. Поскольку и раунды обычные и нумерованные, полагаю что можно совершенно случайно пропустить блог пост и принять участие в раунде, заметив знакомые задачи только во время контеста.

»
8 лет назад, # |
  Проголосовать: нравится +59 Проголосовать: не нравится

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?

»
8 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

SRM 695 ends just 5 minutes before the CF contest.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +35 Проголосовать: не нравится

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

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится -17 Проголосовать: не нравится

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?

»
8 лет назад, # |
  Проголосовать: нравится +46 Проголосовать: не нравится

Palindrome Contest "363" :)

»
8 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

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 :)

»
8 лет назад, # |
Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

Who are the problemsetters of the round?

UPD: thanks for adding them into the main post.

»
8 лет назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится -35 Проголосовать: не нравится

Many user will miss this contest for unusual time

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +125 Проголосовать: не нравится

    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)

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +19 Проголосовать: не нравится

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

»
8 лет назад, # |
Rev. 3   Проголосовать: нравится -28 Проголосовать: не нравится

:)

»
8 лет назад, # |
  Проголосовать: нравится +44 Проголосовать: не нравится

Very convenient time.

»
8 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Feels good to have an early contest. :D

»
8 лет назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

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.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится -6 Проголосовать: не нравится

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

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +65 Проголосовать: не нравится

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.

»
8 лет назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

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!

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится -29 Проголосовать: не нравится

for the sake of tradition, is it rated?

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

i hope the problems will be short like this entry

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +34 Проголосовать: не нравится

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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    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.)

»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

This Time i will be in top 10.

»
8 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

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)!

»
8 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

Rated or not?

»
8 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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~~ :)

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Thanks

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Уже второй раунд подряд предлагается 6 задач. Это новая традиция?

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

What is pretest 5(Div2D)?

  • »
    »
    8 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

    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 :(

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    some thing like it

    3

    2 1 3

    answer is

    1

    3 1 3 or 2 3 3

»
8 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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?

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +36 Проголосовать: не нравится

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.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Does anyone know the hack for Div 2 B?

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
Rev. 5   Проголосовать: нравится +9 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

How to solve Div1-B correctly?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

    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://codeforces.com/contest/699/submission/19261372

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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 ^_^

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 ^_^

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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)

»
8 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Div 1 C — DP with matrices?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +24 Проголосовать: не нравится

    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?"

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +13 Проголосовать: не нравится

        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...

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        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.

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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 ?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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 :/

  • »
    »
    8 лет назад, # ^ |
    Rev. 9   Проголосовать: нравится +3 Проголосовать: не нравится

    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
    
»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
Rev. 4   Проголосовать: нравится -37 Проголосовать: не нравится

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?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +32 Проголосовать: не нравится

    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?

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

What is N equal to in Div2A test8?

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

BLUE?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    Purple?

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

      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)

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +76 Проголосовать: не нравится

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.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится

    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.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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. :(

»
8 лет назад, # |
  Проголосовать: нравится +101 Проголосовать: не нравится

Petr > tourist!!!!!

»
8 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

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

»
8 лет назад, # |
  Проголосовать: нравится +73 Проголосовать: не нравится

Finally Petr Beats tourist

»
8 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Now Petr Top Rated 3597.

»
8 лет назад, # |
  Проголосовать: нравится +35 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

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

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +11 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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...

      • »
        »
        »
        »
        8 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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.

»
8 лет назад, # |
  Проголосовать: нравится +70 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +59 Проголосовать: не нравится

    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).

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Thank you very much for the test!

      • »
        »
        »
        »
        8 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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.)

        • »
          »
          »
          »
          »
          8 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            8 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +35 Проголосовать: не нравится

when will be editoral?

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    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://codeforces.com/contest/699/submission/19242139

»
8 лет назад, # |
  Проголосовать: нравится +74 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 :)

»
8 лет назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

My ratings...

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

Could you please tell me how it is solved?

Thanks

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

А за сколько решение D работает?(например такое 19256185)

  • »
    »
    8 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится +10 Проголосовать: не нравится

    Несложная оценка сверху на перебор N·K!·(K - 1)!: для каждого из N монстров запускаем рекурсию с маской из K единичных битов и одним этим монстром в качестве цели. Каждый вызов функции с X битами и Y целями повлечёт не более X·Y вызовов с X - 1 битом и не более чем X - 1 целью. Получаем (K·1) × ((K - 1)·(K - 1)) × ((K - 2)·(K - 2)) × ... × (2·2) × (1·1).

    Получается 1000·5040·720 = 3 628 800 000. Естественно, на практике будет на порядки меньше вызовов, потому что далеко не любой выбор пары (бит — цель) порождает множество целей максимального для этой глубины рекурсии размера.

    Ещё есть предподсчёт: для пары (точка — монстр) найти набор монстров между ними. У Петра это место за . Можно тривиально реализовать за N2·K.

    Update: ещё я читал в решениях (19249890), что один из факториалов не нужен: можно класть цели в стек и всегда убивать верхнюю на стеке. Тогда и рекурсия не нужна. Тесты это прошло.

»
8 лет назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

E was such a beautiful task <333

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

http://codeforces.com/contest/699/submission/19240157

Почему оно работает?

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    You are mistaken.

    The case is that your answer is NO

    While the right answer is :

    YES

    2 2

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +107 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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!

»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится -19 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

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.

»
8 лет назад, # |
Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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. :)

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 :)

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone please tell me how to solve div2 D?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
8 лет назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

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

»
8 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

Waiting for Round 364 :)

»
8 лет назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится

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!!

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.