Vovuh's blog

By Vovuh, 4 weeks ago, translation, In English,

Hello! Hope you missed me :) As far as some people say, because of copy-pasted announcement this round wouldn't be interesting. But the real thing is that I'm very sick now and I'm very glad that I prepared this round at all. Hope you will enjoy it. Good luck to all!

<copy-pasted-part>

Hello! Codeforces Round #550 (Div. 3) will start at Mar/31/2019 17:05 (Moscow time). You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. Probably, participants from the first division will not be at all interested by this problems. And for 1600-1899 the problems will be too easy. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 (or 8) problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

  • take part in at least two rated rounds (and solve at least one problem in each of them),
  • do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Mikhail PikMike Piklyaev, Maksim Ne0n25 Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

I also would like to say that participants who will submit wrong solutions on purpose and hack them afterwards (example) will not be shown in the hacking leaders table.

</copy-pasted-part>

UPD: Editorial is published!

UPD2:

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 WNSGB 7 206
2 kaixinqi 7 335
3 _sysjuruo 6 188
4 Moririn2528 6 206
5 CarusoX 6 212

Congratulations to the best hackers:

Rank Competitor Hack Count
1 wanderer163 21
2 tokitsukaze 14
3 nazarov.shohrukh 6
4 SMit_mangukiya 4
5 VikasChandak 4
93 successful hacks and 132 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A anurag918273 0:02
B probIem-solving 0:07
C ProPan_without_Pro 0:05
D vnquynh_hac_am 0:12
E probIem-solving 0:28
F sjcakioi 0:16
G izone 0:20

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

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

It hardly matters if you are sick.

Your rounds are always good enough Vovuh

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Get Well Soon Vovuh. Your rounds are always interesting. Looking forward to this one.

»
4 weeks ago, # |
  Vote: I like it -12 Vote: I do not like it

what is mean by copy pasted round ????

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    Sometimes some members of community says that, the announcement of div3 round is always identical. vovuh just pointing out this by saying "copy-pasted announcement"

»
4 weeks ago, # |
Rev. 3   Vote: I like it -12 Vote: I do not like it

Why it copypasted part, if every time Vovuh change something. He downplay his work :)

»
4 weeks ago, # |
  Vote: I like it -19 Vote: I do not like it

Div 3's are always a great way to boost up the ratings.

»
4 weeks ago, # |
  Vote: I like it -16 Vote: I do not like it

Could you make the contest late 1 or 2 Hours cause I Have an exam And I want enter the contest I'm travelling so i Can't get in time I Would be grateful. Thank you :) Vovuh

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Better try virtual. Community love Codeforces' professionalism.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it -17 Vote: I do not like it

      I want to enter it life and also get good rate so i'm asking that if he could make it late only for 1 or 2 hours so that i can get in time thanks for replying me :)

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +15 Vote: I do not like it

        There are thousands people who want to take part in the contests, all over the world. There will never be a time that is good for everybody but there is another contest tomorrow and more contests coming up in the few weeks. There are lots of contests.

        A time that is good for you will be in the middle of the night for somebody else. A time that is good for someone else will be a bad time for you. This is because this planet has more than one timezone. It is not possible for all the contests to be at a good time for you.

        In the meantime, why don't you try practice problems so that you will get a better rating in the next contest that is a good time for you? There are some ladders sorted by difficulty to help you get stronger. That's what I'm doing.

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thank you for your time but to get straight I'm practcing so hard and i know what are you talking about I Respect you all geys and hope haigh rating for you all ❤

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            Good luck! I hope there will be a contest at a good time for you soon, and wish you a high rating too.

            • »
              »
              »
              »
              »
              »
              »
              4 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Thank you ❤❤ I will try my best to finsh the exam quickly so that i can participat in this contest with you all :) i wish to get in time .

              • »
                »
                »
                »
                »
                »
                »
                »
                4 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                I hope you can finish the exam quickly to enjoy the contest

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
          Rev. 2   Vote: I like it +1 Vote: I do not like it

          all times are good for middle-east .. hahahah

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope this round will focus on your problem solving skills rather than speed :) Really love your contests Vovuh :)

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Wanna refresh your algo paradigms? Go for a Vovuh round :)

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Will there be any interactive problem?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

This is gonna be my first contest

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Bug happened! Hope it will be solved soon

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    refresh,because I haven't seen it on my computer

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Refreshed but still visible in my screen

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you tell us about the exactly number of problems? ~Don't tell me 6 or 7 or 8.~~

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    7 problems this time. Hope this information will help you, but I don't know, how it can help.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      I wish you can tell us the number of problems in the round like other rounds.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    this is a mind game bro

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

hello codeforces. gl & hf ♡

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I am outside and may not participate in today's contest or can't join in time. Though the contest is not rated for me, still I am hurt and that's the love for contest not for rating.

And if this was a rated round for me I must postpone my work to participate in the contest, that's the love for codeforces rating.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

My CF account automatically logs out sometimes. Anyone else having this problem? Someone might miss a last minute submission during contest because of it.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Yeah was facing the same issue, to deal with it I had clicked on "remember me for a month" during last login, and now its working fine for me .

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the testcase # 8 in D ??????

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve E and F?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    F looks like bipartite

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    F:

    For every node, either all edges can be directed towards it or directed away from it. So, set the orientation of edges on any random node say X, which will also set the orientation for all other nodes as the graph is connected. Check if the orientation is consistent or not. If not, change the orientation of X and check again. If not, no orientation of edges is possible.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      WAT. I thought the solution is always possible and couldn't figure out how to do it. Jokes on me for not reading it properly.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      There is no need to change the orientation after it is found that it is not consistent in the first go.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Right. It's unnecessary, didn't strike me during the contest.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    E: treat s and t as base-26 integer, then ans = s + (t — s) / 2

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think it can be solved using the fact that for any edge u-v. If there is already an incoming edge for u, then u must have incoming edges only so edge will be from v to u. We can start from first edge and assign it any direction or maybe you can try for both the directions for first edge and solve for remaining edges according to above observation.

    Same will be true for outgoing edges too. For u-v if u already has outgoing edges, u must remain to have outgoing edges only.

    Please check it is correct or not as I have not made any test cases yet. If incorrect, please revert back the test cases for which it fails.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +2 Vote: I do not like it

    F: Here is a pretty simple solution. Use dfs to color every node with white or black so that no two adjacent vertexes have the same color. Then iterate each edge to see whether the color of the vertex on that edge is the same. 52118506

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Did anyone get stuck in TC 15, problem F?(counterexample would help)

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the logic for D. I thought of max repeating element as the no. and got the wrong answer at TC: 8

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Notice that the function basically makes 2 adjacent numbers equal to one of them. Then, find the most frequent element and make all the numbers in the array equal to this number.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I am getting wrong answer on Test case 8 whrn I applied the logic. Can u please tell what I might be missing

»
4 weeks ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Can someone tell me, why every time is vector<pair<int,int> opU size zero, when i printed, but when i compare it is non zero? See final if. 52121225 52120971

Thanks.

I find problem.

»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve G?

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +113 Vote: I do not like it

    Maintain two sorted arrays. For a new element $$$x$$$, if it can be appended to only one of the arrays, do it. If it can be appended to neither, the answer is no. If it can be appended to both, check the next element $$$y$$$, if $$$y>x$$$, then append $$$x$$$ to the increasing one, otherwise append $$$x$$$ to the decreasing one. One can prove this is always optimal.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it -18 Vote: I do not like it

      could you prove it!?

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +57 Vote: I do not like it

        If $$$y>x$$$ and instead we append $$$x$$$ to the decreasing one, we can only then append $$$y$$$ to the increasing one, which is obviously worse than appending $$$x$$$ to the increasing one and $$$y$$$ to the decreasing one. The case when $$$y\leq x$$$ can be proved in a similar manner.

    • »
      »
      »
      10 days ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      I am also from Nanjing(秦淮区)

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Another solution using LIS. Find the LIS and the rest of numbers should be Decreasing, if not we can prove that you only need to swap one number from LIS with one of the rest and there are a few valid cases for swap. 52133834

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      Why is it possible with only one swap? any intuition?

      • »
        »
        »
        »
        3 weeks ago, # ^ |
        Rev. 4   Vote: I like it +6 Vote: I do not like it

        UPD: So basically that I meant in the previous revision is that exists one LONGEST Increasing Subsecuence such that after eliminating it the rest of elements are decreasing or not exists any solution.

        I will try to make the explanation more clear:

        Let $$$DS$$$ be the rest of the elements that are not in some $$$LIS$$$.

        • If $$$DS$$$ is decreasing you are done!

        If not:

        • You can't transfer two or more elements from $$$LIS$$$ to $$$DS$$$ (because you put a increasing subsecuence in the $$$DS$$$)

        • So at most one element from $$$LIS$$$ should be changed to $$$DS$$$:

        1. If none of the elements of $$$LIS$$$ is transferred to $$$DS$$$, then no one from $$$DS$$$ can be transferred to $$$LIS$$$, because this increase the size by one, which is a contradiction because the $$$LIS$$$ is the longest.
        2. If one element of $$$LIS$$$ is transferred to $$$DS$$$, afther added them in $$$DS$$$, $$$DS$$$ still invalid, so it's necessary send some (only one) element of $$$DS$$$ to $$$LIS$$$ (only one because if I send two or more the size of $$$LIS$$$ become greater that the longest increasing subsecuence => contradiction)

        The elements that you need to swap are (it's easy to see that if you not swap these elements, then the solution still invalid):

        • Find the first time in the $$$DS$$$ that there are two elements that increase consecutively, try sending one of them to $$$LIS$$$, then when the element is inserted in $$$LIS$$$, try to move the element to its left or right to $$$DS$$$ and finally check that $$$DS$$$ is decreasing and $$$LIS$$$ is increasing for all the above four combinations.
        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          How is 1. Invalid??we can add element from lis to ds.

          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            If DS is invalid (not is a decreasing subsecuence) and you add one element to this, then DS still invalid because you doesn't remove the elements that maked it invalid

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

A contest of applying sorting algorithm :3

»
4 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

To be honest, this was the most balanced problem set, in recent contests. Even though yesterday's one was also quite balanced, this one was a perfect set.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Please can anyone tell why this code for problem E gets MLE? 52124262

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

I code in C++ and I was having a little trouble in Problem A. When I tested my code on my own compiler (I use the GNU GCC Compiler on CodeBlocks) for the given test case, I obtained the correct answer. However, when I submitted the same using the G++14 compiler on CF, the judgement showed a wrong answer for test 1.

After the contest had finished, I saw that the answer printed by the CF compiler was different from that printed by the CodeBlocks compiler. Since then I have tried all C++ compilers available on CF and none of them gave me the desired answer. Does anyone have any suggestions on how I can fix this problem?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    • If you do the following modification the code will work:
        //fflush(stdin);
        getchar();
    
    • It is undefined behavior to use fflush(stdin) -> More Info
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Your code is currently a mess, especially the I/O. Just learn how to do it in C++ instead of mixing C I/O with C++ I/O. Here is an example of your code rewritten in C++. Also

    Never use gets(). The problem is that gets can write outside the allocated memory so you should never use it. "The function provides no means to prevent buffer overflow of the destination array, given sufficiently long input string. std::gets was deprecated in C++11 and removed from C++14." link

    Btw I suspect that the actual reason why your code fails is because fflush(stdin). Depending on the compiler it can be undefined behavior. If you switch fflush(stdin) with cin.ignore() everything does work.

»
4 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Really great contest! Enjoyed the problems a lot.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can u please tell the mistake in logic for my code: https://codeforces.com/contest/1144/submission/52126510

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      The number of changes you make does not matches with the jury answer. So clearly the line "pn(n- max)" is faulty. I copied some section of your code to see if you are calculating "max" correctly, and my code passed. I don't know anything about java. So best i could advice is, use dictionary or frequency array to find the most frequent element.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thank you for ur suggestion. I am implementing this with the way u suggested.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      There is not a mistake in logic, if you change:

      b[i]==b[i-1]
      

      For:

      b[i].equals(b[i-1])
      

      It works.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can u please teel the mistake in logig for my code: 52106504? Failed on test case 7.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Just check if the graph can be Bi-colored, if is not possbile then print 'NO' otherwise for each edge assign '1' or '0' depending on how you have colored the nodes 'u' and 'v'.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I forgot to put abs around (odd.size() — even.size()) in problem B. Go ahead challenge it. https://codeforces.com/contest/1144/submission/52089891.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Could somebody tell me what is traversed edge in problem F, I had think some time but fail to work out it, I just want to know what’s the traversed edge mean,Thanks

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't know how to hack my second solution of problem G.52114369

My first solution is to find the longest increasing subsequence and check if the remaining numbers satisfy the decrement. Or find the longest decreasing subsequence and check if the remaining numbers satisfy the increment. If not, it is No.

The solution was hacked by test 30:

6

1 2 100 3 101 4

Because [1 2 3 4] was found when looking for the longest increasing subsequence. When looking for the longest decreasing subsequence, I found [101 4].

Then when I look for the longest incrementing subsequence, after the penultimate number, I find the largest number and replace the last one with it. This finds [1 2 3 101], which just passed test 30. In the same way, when looking for the longest declining subsequence,find the smallest number and replace.

This is my second solution.I think there are still some mistakes,but I don't know how to hack it.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any way to boost this python solution for E? I think the time complexity is good enough, just the problem is in the performance of Python itself.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    In no way is that a problem with Python. What you've written there is essentially a $$$O(n^2)$$$ algorithm. Every time you mult by 26 or divide by 26 it has to do the calculation on the entire integer. As the integer is already $$$O(n)$$$ big every operation takes $$$O(n)$$$.

    There are ways to get around this. Python's int(str,base) allows you to read a number in the base 26 in $$$O(n)$$$. But unfortunately there isn't any built in way to print a large integer in base 26 in $$$O(n)$$$ as far as I know.

»
4 weeks ago, # |
  Vote: I like it -26 Vote: I do not like it

actually, I have two accounts in codeforces(one account is for my school homework(rmo) and one account is personal(izadidoostroham). last day I do not have enough time to write different code for problems, that is why I copied code. please give my rating back. thanks.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone point out where's fault in my code for problem c , i think it should be right, but it wa on 8.(lol) here is my code

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    The integer variable "temp" is default initialized to 0, but this can be troublesome as elements of the array can indeed be equal to 0 in some cases. Just initialize the value of the temp variable to some negative value, and enjoy the beautiful green colored "Accepted" on top of your screen :).

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

for problem g is this correct approach? let say i have two array X(increasing),Y(decreasing) and A is Merge(X,Y). Find the longest increasing sequence of A this sequence will contain X and atmost one element of Y and after removing that element from Y Y will still remain decreasing.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    The solution is correct in the case where the length of $$$LIS$$$ of $$$A$$$ is equal to (length of $$$X + 1$$$). The reason for this is, as you said, after removing one element from $$$Y$$$, it still remains decreasing. But, when $$$LIS$$$ of $$$A$$$ has length equal to length of $$$X$$$, then the remainder sequence $$$R$$$ (after removing $$$LIS$$$) may not be decreasing. Consider the case where $$$Y = [4, 3, 2]$$$, $$$X = [2, 3, 4, 5]$$$, $$$A = [4, 2, 3, 2, 3, 4, 5]$$$. $$$LIS = [2, 3, 4, 5]$$$, $$$R = [4, 2 ,3]$$$

»
26 hours ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

hello, in the statement of problem 'D', I didn't understand this line:: "Note that after each operation each element of the current array should not exceed 10^18 by absolute value."

Could you please elaborate it??