vovuh's blog

By vovuh, 6 years 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 awoo Piklyaev, Maksim Neon 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 _sys 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 Fe4RLess 6
4 smit.mangukiya 4
5 chandak_vikas 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 Shuba_realniy_krasav4ik 0:05
D vnquynh_hac_am 0:12
E probIem-solving 0:28
F ForeverFire 0:16
G IZONE 0:20

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

| Write comment?
»
6 years 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

»
6 years ago, # |
  Vote: I like it -12 Vote: I do not like it

what is mean by copy pasted round ????

  • »
    »
    6 years 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"

»
6 years 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.

»
6 years 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

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

    Better try virtual. Community love Codeforces' professionalism.

    • »
      »
      »
      6 years 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 :)

      • »
        »
        »
        »
        6 years 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.

        • »
          »
          »
          »
          »
          6 years 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 ❤

          • »
            »
            »
            »
            »
            »
            6 years 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.

            • »
              »
              »
              »
              »
              »
              »
              6 years 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 .

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

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

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

          all times are good for middle-east .. hahahah

»
6 years 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 :)

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will there be any interactive problem?

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

Bug happened! Hope it will be solved soon

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

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

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

      Refreshed but still visible in my screen

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you tell us about the exactly number of problems? Don,2019-03-31't tell me 6 or 7 or 8.

  • »
    »
    6 years 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.

    • »
      »
      »
      6 years 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.

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

    this is a mind game bro

»
6 years 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.

»
6 years 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.

  • »
    »
    6 years 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 .

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve E and F?

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

    F looks like bipartite

  • »
    »
    6 years 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.

    • »
      »
      »
      6 years 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.

    • »
      »
      »
      6 years 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.

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

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

  • »
    »
    6 years 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

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

      You mean s+(t-s)/2

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

      Just (s+t)/2 will also work

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

      How is it possible to represent it as base-26 int when the strings can be as long as 2*10^5 ?

  • »
    »
    6 years 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

»
6 years 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

  • »
    »
    6 years 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.

»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve G?

  • »
    »
    6 years 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.

  • »
    »
    6 years 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

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

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

      • »
        »
        »
        »
        6 years 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.
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            6 years 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

»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

A contest of applying sorting algorithm :3

»
6 years 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.

»
6 years 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?

  • »
    »
    6 years 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
  • »
    »
    6 years 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.

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

Really great contest! Enjoyed the problems a lot.

  • »
    »
    6 years 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.net/contest/1144/submission/52126510

    • »
      »
      »
      6 years 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.

    • »
      »
      »
      6 years 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.

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

        Can u please tell why == is giving problem because its a char array so it must work.

    • »
      »
      »
      6 years 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.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F?

  • »
    »
    6 years 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'.

»
6 years 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.net/contest/1144/submission/52089891.

»
6 years 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

»
6 years 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.

»
6 years 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.

  • »
    »
    6 years 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.

»
6 years 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.

  • »
    »
    6 years 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]$$$

»
6 years 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??

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is is possible to have multiple solution for problem F..

help please ?