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 |

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 |

It hardly matters if you are sick.

Your rounds are always good enough Vovuh

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

what is mean by copy pasted round ????

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"

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

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

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

Better try virtual. Community love Codeforces' professionalism.

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

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.

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 ❤

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

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 .

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

all times are good for middle-east .. hahahah

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

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

Will there be any interactive problem?

This is gonna be my first contest

Bug happened! Hope it will be solved soon

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

Refreshed but still visible in my screen

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

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

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

this is a mind game bro

hello codeforces. gl & hf ♡

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.

My CF account automatically logs out sometimes. Anyone else having this problem? Someone might miss a last minute submission during contest because of 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 .

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

The case when the max or min number is not the most frequent number.

Maybe something of this form:

5

1 2 5 2 3

What's the answer for it, 3?

YES the answer is 3. 1 1 2 2 3 2 2 5 4

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

Yes, the answer is 3

2 3 4

1 1 2

2 5 4

How to solve E and F?

F looks like bipartite

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.

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.

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

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

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

You mean s+(t-s)/2

Just (s+t)/2 will also work

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

store digits in array.

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.

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

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

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

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.

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

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

How to solve G?

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.

could you prove 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.

I am also from Nanjing（秦淮区）

sir, can u provide the code... ur idea is different and easy to understand but I can't implement it...plz!!!! Thanks..

https://codeforces.com/contest/1144/submission/96759936

Thanks.

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

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

UPD:So basically that I meant in the previous revision is that exists oneLONGESTIncreasing 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 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$$$:

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

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

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

A contest of applying sorting algorithm :3

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.

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

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?

Oh, ok. Thanks a lot!

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.

Cool, got it. Thanks for the help!

Really great contest! Enjoyed the problems a lot.

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

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.

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

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

For:

It works.

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

== compares references, not the values

Check this

Got it!. Thanks a ton

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

How to solve F?

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

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

It will pass the sys test.

Underflow is a wonderful thing.

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

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.

If it is correct，can someone tell me how to prove 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.

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.I see, thank you.

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.

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

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.

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.

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]$$$

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

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

help please ?