### vovuh's blog

By vovuh, 16 months ago, translation, ,

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

• +168

 » 16 months ago, # | ← Rev. 2 →   0 It hardly matters if you are sick.Your rounds are always good enough Vovuh
 » 16 months ago, # |   0 Get Well Soon Vovuh. Your rounds are always interesting. Looking forward to this one.
 » 16 months ago, # |   -12 what is mean by copy pasted round ????
•  » » 16 months ago, # ^ |   -11 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"
 » 16 months ago, # | ← Rev. 3 →   -12 Why it copypasted part, if every time Vovuh change something. He downplay his work :)
 » 16 months ago, # |   -19 Div 3's are always a great way to boost up the ratings.
 » 16 months ago, # |   -16 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
•  » » 16 months ago, # ^ |   0 Better try virtual. Community love Codeforces' professionalism.
•  » » » 16 months ago, # ^ |   -17 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 :)
•  » » » » 16 months ago, # ^ |   +15 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.
•  » » » » » 16 months ago, # ^ |   0 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 ❤
•  » » » » » » 16 months ago, # ^ |   +3 Good luck! I hope there will be a contest at a good time for you soon, and wish you a high rating too.
•  » » » » » » » 16 months ago, # ^ |   0 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 .
•  » » » » » » » » 16 months ago, # ^ |   0 I hope you can finish the exam quickly to enjoy the contest
•  » » » » » 16 months ago, # ^ | ← Rev. 2 →   +1 all times are good for middle-east .. hahahah
 » 16 months ago, # |   0 I hope this round will focus on your problem solving skills rather than speed :) Really love your contests Vovuh :)
 » 16 months ago, # |   0 Wanna refresh your algo paradigms? Go for a Vovuh round :)
 » 16 months ago, # |   0 Will there be any interactive problem?
 » 16 months ago, # |   0 This is gonna be my first contest
 » 16 months ago, # | ← Rev. 2 →   0 Bug happened! Hope it will be solved soon
•  » » 16 months ago, # ^ |   0 refresh,because I haven't seen it on my computer
•  » » » 16 months ago, # ^ |   0 Refreshed but still visible in my screen
 » 16 months ago, # |   0 Can you tell us about the exactly number of problems? ~Don't tell me 6 or 7 or 8.~~
•  » » 16 months ago, # ^ |   +9 7 problems this time. Hope this information will help you, but I don't know, how it can help.
•  » » » 16 months ago, # ^ |   -8 I wish you can tell us the number of problems in the round like other rounds.
•  » » 16 months ago, # ^ |   +3 this is a mind game bro
 » 16 months ago, # |   0 hello codeforces. gl & hf ♡
 » 16 months ago, # |   0 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.
 » 16 months ago, # |   0 My CF account automatically logs out sometimes. Anyone else having this problem? Someone might miss a last minute submission during contest because of it.
•  » » 16 months ago, # ^ |   +3 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 .
 » 16 months ago, # |   0 What is the testcase # 8 in D ??????
•  » » 16 months ago, # ^ |   0 The case when the max or min number is not the most frequent number.
•  » » 16 months ago, # ^ | ← Rev. 2 →   0 Maybe something of this form:51 2 5 2 3
•  » » » 16 months ago, # ^ |   0 What's the answer for it, 3?
•  » » » » 16 months ago, # ^ |   0 YES the answer is 3. 1 1 2 2 3 2 2 5 4
•  » » » » » 16 months ago, # ^ |   0 Can u please tell what I'm missing in this: https://codeforces.com/contest/1144/submission/52121632 I am getting wrong answer on test case 8
•  » » » » 16 months ago, # ^ | ← Rev. 2 →   0 Yes, the answer is 32 3 41 1 22 5 4
 » 16 months ago, # |   +1 How to solve E and F?
•  » » 16 months ago, # ^ |   0 F looks like bipartite
•  » » 16 months ago, # ^ | ← Rev. 2 →   +1 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.
•  » » » 16 months ago, # ^ |   0 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.
•  » » » 16 months ago, # ^ |   0 There is no need to change the orientation after it is found that it is not consistent in the first go.
•  » » » » 16 months ago, # ^ |   0 Right. It's unnecessary, didn't strike me during the contest.
•  » » 16 months ago, # ^ | ← Rev. 2 →   +6 E: treat s and t as base-26 integer, then ans = s + (t — s) / 2
•  » » » 16 months ago, # ^ |   0 You mean s+(t-s)/2
•  » » » 16 months ago, # ^ |   +22 Just (s+t)/2 will also work
•  » » » 16 months ago, # ^ |   0 How is it possible to represent it as base-26 int when the strings can be as long as 2*10^5 ?
•  » » » » 16 months ago, # ^ |   +1 store digits in array.
•  » » 16 months ago, # ^ |   0 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.
•  » » 16 months ago, # ^ | ← Rev. 2 →   +2 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
 » 16 months ago, # |   0 Did anyone get stuck in TC 15, problem F?(counterexample would help)
 » 16 months ago, # |   0 What's the logic for D. I thought of max repeating element as the no. and got the wrong answer at TC: 8
•  » » 16 months ago, # ^ |   0 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.
•  » » » 16 months ago, # ^ |   0 I am getting wrong answer on Test case 8 whrn I applied the logic. Can u please tell what I might be missing
 » 16 months ago, # | ← Rev. 4 →   0 Can someone tell me, why every time is vector opU size zero, when i printed, but when i compare it is non zero? See final if. 52121225 52120971Thanks.I find problem.
 » 16 months ago, # |   +5 How to solve G?
•  » » 16 months ago, # ^ | ← Rev. 2 →   +113 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.
•  » » » 16 months ago, # ^ |   -18 could you prove it!?
•  » » » » 16 months ago, # ^ |   +57 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.
•  » » » 16 months ago, # ^ |   -8 I am also from Nanjing（秦淮区）
•  » » » 14 months ago, # ^ |   0 sir, can u provide the code... ur idea is different and easy to understand but I can't implement it...plz!!!! Thanks..
•  » » 16 months ago, # ^ |   +12 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
•  » » » 16 months ago, # ^ |   +11 Why is it possible with only one swap? any intuition?
•  » » » » 16 months ago, # ^ | ← Rev. 4 →   +6 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$: 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. 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.
•  » » » » » 16 months ago, # ^ |   0 How is 1. Invalid??we can add element from lis to ds.
•  » » » » » » 16 months ago, # ^ |   0 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
 » 16 months ago, # |   +3 A contest of applying sorting algorithm :3
 » 16 months ago, # |   +6 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.
 » 16 months ago, # |   0 Please can anyone tell why this code for problem E gets MLE? 52124262
 » 16 months ago, # |   +1 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?
•  » » 16 months ago, # ^ |   0 If you do the following modification the code will work:  //fflush(stdin); getchar();  It is undefined behavior to use fflush(stdin) -> More Info
•  » » » 16 months ago, # ^ |   0 Oh, ok. Thanks a lot!
•  » » 16 months ago, # ^ |   +2 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++. AlsoNever 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." linkBtw 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.
•  » » » 16 months ago, # ^ |   0 Cool, got it. Thanks for the help!
 » 16 months ago, # |   +6 Really great contest! Enjoyed the problems a lot.
•  » » 16 months ago, # ^ |   0 Can u please tell the mistake in logic for my code: https://codeforces.com/contest/1144/submission/52126510
•  » » » 16 months ago, # ^ |   +1 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.
•  » » » » 16 months ago, # ^ |   0 Thank you for ur suggestion. I am implementing this with the way u suggested.
•  » » » 16 months ago, # ^ |   0 There is not a mistake in logic, if you change: b[i]==b[i-1] For: b[i].equals(b[i-1]) It works.
•  » » » » 16 months ago, # ^ |   0 Can u please tell why == is giving problem because its a char array so it must work.
•  » » » » » 16 months ago, # ^ |   +1 == compares references, not the values Check this
•  » » » » » » 16 months ago, # ^ |   0 Got it!. Thanks a ton
•  » » » 16 months ago, # ^ |   0 Can u please teel the mistake in logig for my code: 52106504? Failed on test case 7.
 » 16 months ago, # |   0 How to solve F?
•  » » 16 months ago, # ^ |   +2 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'.
 » 16 months ago, # |   0 I forgot to put abs around (odd.size() — even.size()) in problem B. Go ahead challenge it. https://codeforces.com/contest/1144/submission/52089891.
•  » » 16 months ago, # ^ |   +1 It will pass the sys test.
•  » » 16 months ago, # ^ |   +1 Underflow is a wonderful thing.
 » 16 months ago, # |   0 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
 » 16 months ago, # |   0 I don't know how to hack my second solution of problem G.52114369My 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:61 2 100 3 101 4Because [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.
•  » » 16 months ago, # ^ | ← Rev. 2 →   0 If it is correct，can someone tell me how to prove it?
 » 16 months ago, # |   0 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.
•  » » 16 months ago, # ^ |   +11 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.
•  » » » 16 months ago, # ^ |   0 I see, thank you.
 » 16 months ago, # |   -26 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.
 » 16 months ago, # |   0 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
•  » » 16 months ago, # ^ | ← Rev. 3 →   0 The integer variable "temp" is default initialized to 0, but this can be troublesome as elements of the array can be equal to 0 in some cases. Just initialize the value of the temp variable to some negative value, it should be good to go.
 » 16 months ago, # |   0 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.
•  » » 16 months ago, # ^ |   +3 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]$
 » 16 months ago, # | ← Rev. 3 →   0 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??
 » 10 months ago, # |   0 Is is possible to have multiple solution for problem F..help please ?