AGrigorii's blog

Codeforces Round #484 (Div. 2)
By AGrigorii, 7 years ago, translation, In English

Hello, Codeforces!

I'd like to invite you to Codeforces Round #484 (Div. 2). It'll be held on May/17/2018 19:35 (Moscow time) and Div. 1 participants can join it out of competition. Please pay attention that round starts in the unusual time!

Me and Andrey API Pikas prepared the tasks for this round.

Great thanks to Nikolay KAN Kalinin for helping us preparing the contest, to Mikhail MikeMirzayanov Mirzayanov for the great Polygon platform and Codeforces and also to Kirill kittylover Samelyuk, Nikolay Apollon76 Permyakov, Dmitry Krainov_Dmitry Krainov, Andrey GreenGrape Rayskiy and Alexey Um_nik Danilyuk for writing solutions.

You'll have to solve six tasks in two hours. The scoring distribution will be announced later

Good luck!

UPD Score distribution 500-1000-1500-2000-2500-3000

UPD2 Congratulations to the winners of the division 2:

  1. Kotori_Is_My_Wife

  2. vosptu

  3. ez_zkj

  4. relativity

  5. iordache.bogdan

And also our congratulations to the winners of both divisions:

  1. Claris

  2. Benq

  3. Kotori_Is_My_Wife

  4. kmjp

  5. vosptu

UPD3 The editorial will be published tomorrow.

UPD4 Editorial

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

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

Is there div 3 and is div 3 rated?

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

    Div2 rounds are rated for people on div3 too

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

    Questions about div3 is getting more annoying than "Is it rated?". Seriously, stop.

    "Div 3" means there is the special contests rated only for people under 1600. Nothing more. "Div 3" does not exists anywhere except for the special "div 3" rounds.

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

Great :). You could fix timeanddate.com link to make it display time in user's timezone. Take a look on Mike's comment: http://codeforces.net/blog/entry/59322?#comment-429178

Displayed time screenshots of #483 and #484:

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

Yeaaa! Round by my favourite problemsetter! I waited it so long. <3 <3 <3

I think, I can become Candidate Master tomorrow.

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

    Hi, bro! It seems that I can upgrade my color too!

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

Third palindrome round in 2018 !!

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

    What do you mean?

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

    The first square round in 2018!

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

      The first square, whose each digit is a power of two, the second digit is the first time two, the third is the second divided by two, for division two, and each digit of the square root of the round number is two, and dividing the square root of the round number by two gives a number whose digits sum to two.

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

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

        Damn, I forgot that the sum of the digits is a power of two, more precisely 2^2^2.

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

        In case you didn't have enough...

        484 = 222

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

          never enough ...

          22 = 17 + 5 : date of contest ² = div 2

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

...

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

I smell a lot of hacks

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

Q. Why do you start blushing when a new Codeforces round is announced?

A. It turns me Red. ^_^

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

    How can div. 2 only contest make specialist a gradmaster? Does this make any sence to you?

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

      It is a joke. I am not talking about myself.

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


Reading comments be like...

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

is it rated for purples ?

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

Should have a contest on yesterday. 13,14,15,17....why missed 16??

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

What about for Div 3 members?

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

    Most contests in Codeforces:

    1) Div.1 + Div.2: Candidate masters and higher (1900 and higher) will be in the first division while experts and lower (lower than 1900) will be in the second division

    2) Div.2 Only: Candidate master and lower (lower than 2100)

    3) Div.3: Specialist and lower (lower than 1600)

    So please stop commenting the same question every contest.

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

Wish high ratings to all.

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

I hope this round won't be like that 1vldm8

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

    Guess I'm a faithful guy...

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

    Hacking is such a ridiculous thing, maybe good for some guys but unfair... But not always bad, the stress and excitement is cool, agree?

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

better starting time for Bangladeshi contestant....

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

Can't open problem C and D. Showing Error !!

→ Reply
»
7 years ago, # |
  Vote: I like it -12 Vote: I do not like it
The comment removed because of Codeforces rules violation
→ Reply
»
7 years ago, # |
  Vote: I like it +66 Vote: I do not like it

How to solve F?

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

    If we look at the dfs tree of the graph:

    • If we got any backward edge (an edge connecting a node to one of its ancestors) then the answer must be one of the nodes between the two endpoints. If there is not such edge then answer is -1.
    • If we got another backward edge then we need to find the intersection (or remove nodes from solution which are ancestor of the other node or are not ancestor of the current node). For example, 1 -> 2 -> 3 -> 4 is a cycle, and 2 -> 3 -> 5 is another cycle. Both 4 -> 1 and 5 -> 2 are backward edges.

    • If we got a cross edge (edge connecting a node to another that is neither its ancestor or descendant) then if the other node is in cycle and topmost node of the cycle is a parent of the current node, we need to erase the nodes that are neither parent to the current node nor descendant of the other node. For example, 7->4 is a cross edge.

    Submission as a reference: 38382900

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

      Hi there, I am struggling hard with this problem. So I studied your code quite a bit, and found a mistake in it. Try the following test case:

      6 9
1 2
2 3
3 4
4 1
4 2
3 5
5 6
6 4
1 6

      Solution should be 4, but your program answers -1.

      The last edge 1->6 in this test case is a cross edge. So you have to delete all vertices on the cycle 1->2->3->4->1 that are anchestors of 6, but not of 1. Finding the lowest anchestor of 1 on the cycle works (it is 1 itself). But finding the lowest anchestor of 6 doesn't work, since you argument with the height h of 6, which has nothing to do with the ancestors.

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

How to solve problem D?

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

    You can brute force for all posible k using sets in O(nlogn).

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

      what is the test 5 ?

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

        I used co-ordinate compression. I got WA TC #5 when I was printing K in terms of the compressed value instead of the real value.

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

          I got WA on test 5 for a different reason.

          My answer: 57209037

          Judge: 45567032

          My algo iterated a values as candidates for k. When a is sorted by size, these values are consecutive in the input:

          57209037 (found best solution at this value)

          45567031 (found worse solution at this value)

          Obviously, the best solution can also be found at 45567031+1.

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

            Can you please tell me what's wrong in my code 107085887. I am getting WA on test 36 !!

            UPD — Solved It :))

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

        If anyone needs complete test 5 input, I've put it here: https://pastebin.com/vHuv6LE4

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

      What is stored in the sets? Also... Brute force requires to iterate through the whole array right?

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

        We can store lengths of locations and when they are reached, with a array or bst like std::set or std::map. To do this we can sort the sequence and enumerate k from 1 to n, using disjoint sets.

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

      Can you elaborate please?

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

      based on this we can simply use an array instead of std::set, thus we can do this step in O(n).

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

    And of course k can only be equal to a[i] + 1

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

      I got the k=ai+1 part during the contest but can you tell me about how to brute force ??

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

        I have one set to store segments of elements less than k and one multiset to store lengths of all segments in first set. Then i add all a[i] from the smallest to the biggest, where current k = a[i] + 1. When you add one there're three scenarios: it forms a new segment, it unites with one segment, it merges two segments together. I think it's clear how to do updates and how to keep multiset of length.

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

          Oh thanks I get it.

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

          Alternately, start with the segment [1...n], and add a[i] from largest to smallest. This way, it's guaranteed that the only operation happening is breaking up an existing segment, which makes implementation easier.

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

        So when at some step segment set size is begger than it's sizes at all previous steps and when all elements in multiset are equal I update the answer with a[i] + 1.

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

      I thought of this, forgot to implement it because the samples didn't need it, and managed to implement it with about 10 seconds to spare in the contest.

      ...Needless to say, I wasn't able to submit in time :(

      Ah Codeforces, thou art a cruel mistress...

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

    Maintain a dsu of active indices and process the indices with increasing order of values. At each step, let cur_k be value + 1. Check if neighboring indices are active and accordingly merge them. Also maintain the count of total active indices for a given size of set. Update the answer if the current size is equal to total active indices.

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

the solution to problem c was available at https://www.geeksforgeeks.org/maximum-edge-removal-tree-make-even-forest/

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

    I took 30mins to solve it. Authors need to be more cautious before preparing a problem. :(

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

    striver_79 try to solve problems rather than searching for problems

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

      haha, if I was to search for the problem, I would have got all the pretests passed in 5 minutes. I tried for an hour, but when I did fail for it, then I was searching for the DFS part when I came across it. Learn to observe before saying something. :)

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

        Looking for the dfs part and then came across that nice explanation btw what are you looking in DFS. "WHAT TO OBSERVE". I also type DFS in google but I didn't came across that question maybe your browser is a legendary one.

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

          I do not owe an explanation to you that is for sure buddy. And stop blaming someone for pointing out a link which seems similar. :) I guess you learn everything without googling. You got so much of inner talent :)

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

Problem E can be solved by the fact that this rectangle can be mirrored adjacently on the coordinate plane.

No, I didn't solve it.

I've done a similar problem in Google Foobar. If I had been given 40 mins I could've solved it. :(

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

What is the 6th pretest in C?

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

Problem C is available at Hacker Rank: Your text to link here... . Check this out..

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

I read "connected components with equal size" instead of "even size" in C. Yikes

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

Feedback:

C: nice

D: A bit ambiguous, I needed two clarifications to understand it.

E: The mirroring trick is very standard. I think I've seen a very similar (maybe the same) problem in uva.

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

    C was a direct copy from geeks for geeks

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

    Mirror trick? Can you say sth? I solve it using Chinese remainder theorem.

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

    Do you know if there's a name for the mirroring trick? I've seen a solution that used it in the past, but I wasn't able to understand it then. I'd like to find more information about it and learn it now.

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

      just consider each side of the table as a mirror and copy the table based on its picture in the mirror. So anytime the ball hit the side it enters the new table and continues its direction.

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

        I don't understand what algorithm follows this. You calculate the intersetcion point of rectangle and a straight line. If you hit the origin or a corner, you are done. If you hit the wall, you reflect the whole rectangle and keep going.

        You repeat the above 10^9 and tle.

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

          The point of the reflection isn't to simulate the process: that can be done without the reflection at all. The point of the reflection is:

          1. You can now travel in a straight line

          2. You get generalized coordinates for the corners: for example, using the labeling in Morphy' picture in the other comment, point A will have coordinates (2mk, 2nl) for integers k, l.

          You can get similar generalized coordinates for the other 3 corners, and then it's simply checking whether integers k and l exist such that the point given by them lies on the line you have, in the direction you want.

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

            Can you please provide a resource link to learn it? Thanks in advance.

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

              I'm sorry, but I don't have an online resource for this sort of thing.

              Given the context, I'm pretty sure that there'll be a few problems of this type discussed on AOPS, so look there maybe?

              To be honest, this is my first time seeing the reflection being used in a coding problem. I've only used it in maths problems before, but it seems like a nice Olympiad problem trick, so AOPS seems like the place to look.

              I'll look around a bit and see if I can find something more concrete.

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

              This link might be helpful for the proof and solution of diophantine equations.

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

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

    I agree with you and saw a couple of problems like E. (e.g. in Google foobar) I'm wondering why did I read it at the end of contest! :-/

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

I used tree dp to solve C but now i find out that there's some simple solution -_-

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

So are you sure what you want us to find in D is what D's statement says?

Thus, in the sequence of n days we can find consecutive nonempty segments when the shark traveled the distance less than k in each of the days: each such segment corresponds to one location.

Shit in bold's true but it it's not true that each location has a corresponding nonempty set.

Now getting back to what the problem asks for:

Find such integer k , that the number of locations is as large as possible.

And at the same time, what you want us to do is find the k which maximizes the number of nonempty sets, not the number of locations.

Even after the announcement, which was too late anyway, nobody bothered to actually update the statement.

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

    This is because if a shark travels 2 days in a row, he will still be at a new location on the day in between, correct?

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

    After reading the problem statement I thought the answer to this test case 8 1 2 7 3 4 8 5 6 should be 0 as it satisfies all the conditions asked i.e 1) the shark was in each location the same number of days, 2) the number of locations is maximum possible satisfying the first condition, 3) k is smallest possible satisfying the first and second conditions

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

      I have the same confusion regarding this problem (but not anymore). Let me help clarify this. Assume the answer is k, one location is counted as non-empty consecutive segment which every number in it is strictly lower than k.

      For first sample case, if the answer is 7, the number of location is 3, that is {1,2}, {3,4}, {5, 6} and valid because each segment size is two. If you choose 0 as the answer, the number of location is zero. So there's a better answer than 0.

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

Happy Ramadan holiday to all. I wish happiness and health to everyone.

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

This statement didn't exist at the beginning of the contest. My solution was hacked because of it. and there was no clarification about it!!!!!!! AGrigorii [ ](Ca)

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

    it did exist

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

    MikeMirzayanov

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

    Actually we missed initially that the note was incorrect for n = 2. The mistake was fixed a few minutes before the round, as soon as MikeMirzayanov spotted it, and the update was pushed from Polygon to CF. It takes some time, but for me the statement opened a minute before the contest already contained the fix, so I decided that everything was ok and I did't have to make an announcement. It turned out that for some people the old, cached statement opened without the fix. Luckily almost everyone understood what we meant correctly.

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

      Till I submitted my solution ,the fix didn't exist. I wrote my solution based on what I read in the statement. It wasn't my mistake.

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

      You can`t re-test only A problem without test with size = 2? I think it would be fair

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

      So this is over and my rate decreased beacause of a mistake which is not mine.

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

        Stop crying over dumb shit. Mistakes happen and this contest is not the end of the world.Also its just -20 which can be recovered very easily.

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

          As for me, this worsened my result by 45, but I totally agree that this is just a rating, but it's not very pleasant either

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

A question copied directly from geeksforgeeks, wtf ???? Contest should be unrated.Its a big disgrace.

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

    The practice shows that it won't be unrated. There was a case when absolutely the same problem appeared twice even on codeforces itself but the round was rated.

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

      If I am not wrong it was in an educational round, in which the ideas can be common. And it did not affect many div 2 coders. I might be saying this since I performed bad in the contest. But still C was just google and first link and it shouldn't be the case.

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

        I think there were plenty of "just google and first link" cases too. But still I think we should let coordinators decide whether it's fair or not.

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

        I have seen many times(I guess at least 3) where exactly same problem was in other contest, but mostly all of such contests were rated.

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

Was not able to open all problem statements in one window :( Bug

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

Does this solve F? https://www.quora.com/Given-a-strongly-connected-component-can-you-determine-in-linear-time-if-the-removal-of-a-single-node-turns-the-SCC-into-a-directed-acyclic-graph

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

How to solve C?

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

o.O

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

    I think only his last solution got hacked, and all previous solutions were marked as hacked.

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

    did he cheated using clone account?

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

What topic should i learn to solve C div2?

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

Almost same as today's Problem C Is there any difference conceptually ???? May be it is not what the contestant expect from the problem setter..

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

    In the yesterday contest, solution for C was also in Wikipedia.

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

How to solve C if it would have been a graph with cycles ?

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

    tree hasn`t got cycles

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

      I know that. I am just asking how would one go about solving the problem if it would have been a graph with cycles as the approach used for solving the tree one will not work here.

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

        Sorry, I did not understand correctly what you mean

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

        I may be wrong but in case of undirected connected graph we have to consider only those edges which if removed results in more than one connected component otherwise clearly if removal of an edge does not divide the graph then answer depends on n is even or odd. Now for the previous one you can have a look at bridge in a graph --> https://www.geeksforgeeks.org/bridge-in-a-graph/ Removing such edges and doing the same what we did in actual C question should do the thing.

        But Edges might be of order which does not satisfy the constraints if n is 1e5.

        By doing the same thing (which i wrote above) i mean that edge should be removed only if it divides two parts in even number (each).

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

          The approach seems fine but I think finding out Bridges and removing would give "minimum" number of edges required for deletion and not "maximum".

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

            No removing bridges does not govern whether we get minimum or maximum edges. When i say that you remove edge only if it disconnects the graph and both sides nodes should be even. So automatically all the edges which satisfy this property will get counted and that's what we did it in given C we count all those edges which divides the nodes into two even halves. Please correct if i m wrong !!

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

      in case of a connected graph ???

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

About the choice of wording in condition 1 of A

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

In Question B why doesn't 3*nlogn pass the test cases. I tried using maps in c++ but it is showing time limit exceeded in test 45 . Can someone point out mistake in my code : Link

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    while(used[cnt2]==1)
cnt2--;

    This part doesn't looks like O(1) or O(log n). I think, it's O(n) at worst case (because of "cnt2 = cnt1;" six lines higher).

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

Yay, I became master, but sadly only because of div2 rounds.

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

    What is the difference? Master is master. If you don't want to participate in div 2, then wait for div1...

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

      well actually its opposite, there are some purples that skip div 1, because they don't want to be beaten up by reds and yellows and join div 2 to compete with blues instead.

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

        They can be beaten up by blues then.

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

    I don't understand why everybody is complaining and thinks that it would be easier to get to 2100. The only true thing is that there will be more opportunities to get there. It doesn't mean it would be easier. If you don't deserve 2100 you won't get it, one way or another.

    For example I already managed to lose a lot of points in div 2 contest on Monday. And today I was 122. If there were no violet coders, I would have been 25'th which would have given me much more rating.

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

      Lol You don't understand? Before this shit revolution, to get Master(old) you need to most likely solve 3 probs in Div 1 which is equivalent to all div 2 problems. Now get just good ranks which in most case is possible with just 4 div 2 problems. As you can see in this round, 370 officially solved 4th hardest, you think thats good enough for someone Master?

      "I don't understand why everybody is complaining and thinks that it would be easier to get to 2100" Because it actually is faggot. If you don't understand, then compare how many users have got there maximum rating in past div 2 only rounds.

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

        "to get Div 1 you need to most likely solve 3 probs in Div 1" — makes sense. Sorry about my previous post.

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

    You've became at least, not like me :D (9 points)

    Congradulations!

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

      At least you have a chance to participate to next Div2 round, not like me :D (passed to master with 11 points).

      Congratulations!

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

It looks very strange that O(nlogn) solution for D works without any used memory: 38374872.

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

Problem C is a duplicate problem: https://www.geeksforgeeks.org/maximum-edge-removal-tree-make-even-forest/
Problem F is a duplicate problem: https://sio2.mimuw.edu.pl/c/pa-2015-1/p/kon/, https://www.quora.com/Given-a-strongly-connected-component-can-you-determine-in-linear-time-if-the-removal-of-a-single-node-turns-the-SCC-into-a-directed-acyclic-graph

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

    That claim about F is totally ridiculous

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

      Sure. https://sio2.mimuw.edu.pl/c/pa-2015-1/s/89776/source/ 38363244

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

        The Quora answer is wrong and comments don't seem to give any hint to actual solution.

        As for the Polish problem, the translation shows that it is a harder version of Problem F. However, it isn't possible for problem setters to verify that their problems don't exist even on non-English sites.

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

        Yes, it's the 4th time that I came across this problem.

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

      It is not. I didn't realize this and now I checked that my incorrect solution to kon (9/10) is accepted after 2 small modifications (for 2 or more disjoint cycles and for empty list of cities).

      Though I am not sure if I would have been able to figure out the first one during the contest...

      Anyway, top 5 has gone...

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

    Sorry but I have to say that CF won't care about such a thing!

    Sometimes CF copies exact problems from itself though.

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

      It's not copying if the second setter didn't realize that the idea for the problem was already used before.

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

speed of light coder !! ****

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

I think systests on D are very weak. I found a big mistake in my code after submit but surprisingly gave me an AC. My AC code: http://codeforces.net/contest/982/submission/38384511 A simple test case when my output differs from another AC submissions: 11 7 9 8 100 1 2 3 200 4 5 6 There something invalid in this input?

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

    n = 1488 in systests

    Problemsetter is the best ❤️.

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

    My AC submission give output 10 and your code output 7. Maybe your code do any undefined behavior?

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

In Problem B What if the number of extroverts(1) at any point becomes greater than number of introverts(0)? Many solutions will fail then ![problem:982B]

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

    It is mentioned in the problem statement itself that there is always a suitable seat for an extrovert, So no such case will occur.

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

    It is guaranteed that the number of extroverts equals the number of introverts (i. e. both numbers equal n), and for each extrovert there always is a suitable row.©

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

Can someone help me in understanding D ...??

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

    For each different k[i] = a[i]+1, you check the size of all the contiguous days with a distance covered strictly less than k[i].

    You go through all the a[i] in ascending order.

    if a[i] does not have a neighbour lower than him, it creates a new contiguous day sequence of length 1. Then, you merge it with his neighbour(s) (if they are lower than a[i]), which destroys their sequence and creates a new sequence of length 1 + total length of the sequences of the neighbours. It's important because you need to keep track of how many different lengths of sequences you have at all time, cause you will need it at each step.

    To keep track of how many different lengths of sequences you have after each a[i], you can create a table that tracks how many sequences each length has, and a variable that tracks how many lengths you have (that you increase by one each time you insert a sequence whose length is not represented yet, and decrease whenever you remove the last sequence of a given size). If there is only one length in the table, then you know that the number of sequences for k[i] is (number of distances <=a[i]) /(only length of sequence represented).

    The answer is the minimum k[i] that leads to the maximum value of this ratio. You can do the merge with an union/find, making the merging a O(n*log(n)), and computing the ratio each time can be done in constant time, leading to (I think) a solution in O(n*log(n)).

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

AGrigorii When is the editorial gonna be published? If it's already published in Russian, please do provide the link. Thanks

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

I found a surprisingly simple solution for F. The key observation is that if you have a node with an outdegree of 1, you can delete that node and push all incoming nodes to the successor (with a special case for self-loops). This process can reduce the number of edges if an incoming node was already pointing to the successor node.

As an example, node 3 in the image below can be deleted since it has only one outgoing edge:

Which results in:

Note that this reduced the outdegree of node 1, making it now eligible for deletion.

If you have more than one node remaining after this reduction, then the answer is impossible. I haven't tried to prove this, but it resulted in an AC submission. :)

For each node, it is essential to maintain an unordered_set for incoming and outgoing nodes to detect duplicate edges. This makes it slightly slower (due to the set operations), but it's fast enough to pass in C++ (albeit not in Java, from my experience). My accepted submission: 38409568.

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

    I thought about a proof of your solution, and I think it is correct. If anyone find any wrong with it, just point out the wrong point.

    The first part is about the validity of deleting the point with one out-degree. We can think about a point u that satisfies the requirement and we call v is a point that have a direct edge to u. We can easily find that every circle that pass the edge u-v must pass the point that u can only arrive at. So we can think u is useless and delete it from the graph (of course it contains the process of changing some edges).

    The second part is about why the answer is impossible when there are more than one point remained. Now, the graph satisfies every point has at least two out-edge, of course we can remove arbitrary out-edge to make every point's out-edge is two. Then we build the dfs tree of the graph, and it is a binary tree. We only need to discuss about the out-edge of the leaves. We assume that this graph is valid for answer. Then we need to construct the out-edge of the leaves by a optimal way to make the graph is valid. So we can first make every leaf link to the root, and the other out-edge link to the next leaf in a way you like. But we will find that one leaf can't make another link because it wouldn't be valid no matter where it connect to. So we can prove this part.

    This solution has a drawback is that it can't output all the points that satisfy the problem. But it realy easy to type.

    (If there are many grammar errors, please don't blame me. Because my English is realy not good.)

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

I did not manage to solve div2-C using Python 2. My submission 38369140 got runtime error. I think the issue is recursive calls. Is there a trick in Python to get this code AC?

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

Who can tell me what's the meaning of 'even size' in Problem C. The 'even' means equal? or %2==0？？

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

Request: Please post the editorial link with problems for this contest. Had a hard time to find this post to find editorials.

→ Reply