Hello Codeforces!

On May/01/2019 17:35 (Moscow time) Educational Codeforces Round 64 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be **rated for the participants with rating lower than 2100**. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given **7 problems** and **2 hours** to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir Vovuh Petrov, Ivan BledDest Androsov, Maksim Ne0n25 Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all participants!

Our friends at Harbour.Space also have a message for you:

Hi Codeforces!

Harbour.Space University, the International Tournament of Young Mathematicians (ITYM) and St. Paul International School Barcelona have designed a special online test for high school students, to take place on **May 5 ^{th}** at

**15.00 CET Time**.

You can take part in the online test if all the following conditions are met:

- Between the ages of 12 to 18,
- Have not graduated from high school
- Eligible to take part in IOI/IMO 2020.

After the test, all participants will get a 20% discount link to attend Tech Scouts, the two-week summer camp we run from the 8^{th}-19^{th} of July in one of Barcelona's leading international schools, St.Paul’s, **and the most successful performers will be interviewed and awarded a full tuition waiver to attend the advanced level of the Advanced Technical Track of Tech Scouts**.

In order to register for the contest, please fill out **this form** before **May 3 ^{rd}, 2019**.

We would love to see you guys at our camp this year — if you’re interested in joining, or if you just want to know more, just head over to the Tech Scouts website.

**UPD:** There are some minor issues with one of the problems, we'll use one of lesser-known problems by Maxim Babenko.

Congratulations to the winners:

Rank | Competitor | Problems Solved | Penalty |
---|---|---|---|

1 | step_by_step | 7 | 491 |

2 | RimuruTempest | 6 | 270 |

3 | receed | 6 | 280 |

4 | I_love_Tanya_Romanova | 6 | 286 |

5 | dreamoon_love_AA | 6 | 299 |

Congratulations to the best hackers:

Rank | Competitor | Hack Count |
---|---|---|

1 | halyavin | 64:-3 |

2 | WileE.Coyote | 39:-23 |

3 | wzw19991105 | 18:-1 |

4 | FST-OIer | 14:-1 |

5 | omaewamoushindeiruuuuuuu | 2 |

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

Problem | Competitor | Penalty |
---|---|---|

A | halyavin | 0:06 |

B | nuip | 0:07 |

C | quailty | 0:04 |

D | waynetuinfor | 0:11 |

E | step_by_step | 0:05 |

F | step_by_step | 0:15 |

G | step_by_step | 1:22 |

**UPD2:** The editorial is out.

Every educational round everDon't worry. I am there.

PikMike says, NEVER GIVE UP

Hope the problem set is going to be an interesting one like the last one :)

Happy Coding

Round Professional 64 activated successfully !

wtf?

the round should be unrated

what is going on?

Problem A was not well described. The side note under the test case was explaining an unwritten test case which means it was misleading. The solution had been rejudged. I see something strange that most of the solutions get WA answer on test 3. check the announcement of the round. Whatever, it is unrated now

To be honest, for long enough hasn't a problem A been so... chaotic.

Is it rated? Rejudging affects >3000 people.

UPD: Unrated.read first problem 10 times before seeing announcement.

Feeling IrritatedI'm very upset today :(

The round should be unrated, it's not ok that after 30 mins I see my AC code on A get WA

Literally everybody did though, I feel like it could still be rated, I don't know

oh no.

Eventually, the round became unrated. :(

Solve problems just for fun. ;)

Authors, dont worry. Shit happens. Good luck to you

So what's going on in Problem A? My code got WA after rejudge. But I don't know what's wrong in it. http://codeforces.com/contest/1156/submission/53616304

Consider a triangle inside a circle inside a square.

But because the contest is running, the link can't be accessed.

3 1 2 is 6

Wow...that's really interesting.

thanks

Got really happy after getting notification of round being unrated. Already many WA.

should have been rated but oh well

This round the highest Accepted on the entrance div2-A problem was 8. Out of 100! XD

to be honest, this compitition has got a

reallychaotic problem set.(who had seen problem A give so many leaks? And problem B also got an error in the standard output.)

yet this round is unrated.

Irritating. Very irritating.

without paying attention to solved problems, It won't change our rating , yeah?

Right

no, it won't.

"_Unfortunately_, the round will be unrated."

More like,

Fortunatelyam i rite?Absolutely, the Author even can`t solve A. So irritating

some people say otherwise. :D

happy coding❤this but with GCD, divisor and Number theory

Great guess.Here is the original pictureWhy not try to learn those stuff and be able to solve problems way over your rating range?

Japanese people welcomed the new era, not error.

love it

Literally half participants on problem A. ( including me )

This photo really swapped out my bad mood today. www

TFW codeforces comment section is funnier than all of reddit.

Something went wrong...

Unfortunately, the contest is unrated(((

`This year the highest grade on the entrance math test was 8. Out of 100!`

I guess now everyone knows why xD

What a mess.

2 1 2

is this valid for Problem A?

UPD: Finally this is surely invalid because an anoucement.

The triangle is oriented in such a way that the vertex opposite to its base is at the top.UPD2: really sorry, maybe I should change new glasses, the problem statement says,

the triangle is oriented in such a way that the vertex opposite to its base is at the topNo. The direction of the red triangle should be like the black one.

isosceles triangle with the length of height equal to the length of base.each triangle base is parallel to OXfor each i from 2 to n figure i has the maximum possible length of side for triangle and square and maximum radius for circleThe red triangle fit these condition well.

OK. But there is another announcement now.

Yes, but you have drawn a equilateral triangle for which the height is not equal to the sides, so this configuration is impossible.

this is my fault because of drawn misleading.

even thought if drawn correctly, the answer may be 5 not 6. :D

No. Notice that "each triangle base is parallel to OX".

Anyway, the base is still parallel :)

Yea, I think you are right. In this case, I considered the vertex as the "base" actually, so I thought it's not parallel to axis.

How can a vertex be parallel or not to a line?

If it does not intersect the line then it's parallel to the line :)

But just now there was an annoucement

The triangle is oriented in such a way that the vertex opposite to its base is at the top.It's also in the statement of the problem:

`the vertex opposite to the base of the triangle is poiting up;`

And I think it was there

beforethe announcement because I had the tab open and didn't refresh.yeah, you are right.

maybe I should change my glasses

UPD: there are only four condition in very first,

the vertex opposite to the base of the triangle is poiting up;this was just added later.

No, you don't have to do that; that state is revised, and before revising that, there was some vague state.

Hehe, didn't even think of this one!

Since the contest is unrated and everyone is discussing the problems anyway... how to solve C? It feels like there should be some sort of greedy way of matching up points but I can't figure it out.

I did binary search for the number of matches k. Check by trying to pair the k smallest points with the k largest points.

just sort the array, and use two variables i and j. initialize i=0,j=n/2 and then just start pairing them.

I want to experience how it feels like asking a solns of ongoing contest in comments.

Here it goes -

"How to Solve D??"

You can solve it with a little bit of DSU.

First of all, use all edges marked as $$$1$$$ to merge nodes into disjoint sets.

Then, the remaining edges — those marked as $$$0$$$ — are considered as the actual edge of the graph (in other words, after using all $$$1$$$ edges to create disjoint sets, we remove them).

From here, we'll perform DFS for the entire graph to find the components of nodes connected solely by $$$0$$$ edges.

For each component, let's denote $$$m$$$ as the component's size. Also, let's denote $$$k$$$ as the number of nodes not within the component, but can be reached from some nodes of the component due to being in the same disjoint set (mentioned at the first step). We'll add $$$m(m-1) + mk$$$ to the final answer.

The calculation of $$$k$$$ is simple — before the DFS traverse initiate $$$k = 0$$$. For each node $$$z$$$ visited, increase $$$k$$$ by $$$sizeof(dsc(z)) - 1$$$, with $$$dsc(z)$$$ is the disjoint set containing node $$$z$$$.

Total complexity: $$$\mathcal{O}(n \cdot \log(n))$$$ or $$$\mathcal{O}(n \cdot \alpha(n))$$$, based on how you construct the disjoint set union.

Why not to use DFS to find the components connected by 1 edges?

Well, we still need $$$sizeof(dsc(z))$$$ after joining nodes by $$$1$$$ edges, and (not sure if there was any neat implementation), if I performed DFS on that step, I'd either do it twice to assign $$$sizeof(dsc(z))$$$ to all $$$z$$$ in that component, or use a vector/stack to maintain the newly visited nodes, which could actually makes the implementation be a bit unnatural.

The answer is S(m*(m-1)) + S(dsc(z)*(dsc(z)-1)) + S(m*k) right? S() denotes sum over all components, disjoint sets and components respectively.

$$$S(m(m-1)) + S(mk)$$$ actually. Forgot to include it into the main comment, will edit in a few seconds ;)

I used Tree DP, with:

dp[0][i]: number of 0-1 path whose lca is child of i

dp[1][i]: number of 1-path which ends at i

dp[2][i]: number of 0-path which ends at i

dp[3][i]: number of 0-1 path which ends at i and the edge connecting i is 1-edge

dp[4][i]: number of 0-1 path which ends at i and the edge connecting i is 0-edge

It's also possible to do it in O(n) using dp on trees. Let dp[x][0] be equal to number of vertices to which we can access from vertice x using paths which have only zeroes as their weights and dp[x][1] same thing but which have only ones as their weights.

We can note, that each path we are looking for has a point where ones change to zeroes. Let's assume that our vertice is the vertice of change for some paths. We can easily observe that we need to add to an aswer dp[v][0]*dp[v][1]+dp[v][0]+dp[v][1].

So now the only problem is to find a way to calculate dp array. Firstly let's calculate number of paths which i mention before but only for vertices in the subtree of vertice x. That can be done as follows: if we have dp calculated for our son, and we use a path of weight y to go to him, then dp[x][y]+=dp[son][y]+1.

Now we have the answer but only for a vertice from which we started our DFS (because his subtree is full tree). Now let's start second DFS. An observation is: if we go from vertice x to its son using a path with weight y then dp[son][y]=dp[x][y]. Why? Having in memory that dp[x][y] is number of vertices we can access from vertice x using paths which have only weights y, then we see that this number can't change if we are using a path of weight y.

Lots of tree-DP problems based on paths have a standard procedure consisting of two steps:

Initially, if I define $$$dp[v]$$$ to be the number of vertices in the subtree of $$$v$$$ to which I have a valid path, and $$$dp1[v]$$$ to be the number of vertices in the subtree of $$$v$$$ to which I have a path by navigating only 1-edges, then in one dfs we can compute these values. Then, in the next dfs, we include in both $$$dp[v]$$$ and $$$dp1[v]$$$ the case where the second vertex of the path is the parent, which gives us the final answer for vertex $$$v$$$. So after this dfs, $$$dp[v]$$$ will be the number of valid paths originating at vertex $$$v$$$ and $$$dp1[v]$$$ will be the number of valid paths originating at $$$v$$$ by navigating only 1-edges. Note that we must change the value of the parent before that of a vertex, because we want to use the second definition of $$$v$$$ for the parent in the second DFS.

problem A (and other problems also) proved that every contestant is also a Labour. Happy Labour Day.

Is it possible that a cycle inscribed into the non-equilateral triangle (isosceles with the length of height equal to the length of base) with three distinct points touched?

Think that there is "An inner circle of a triangle". It is always possible.

fortunately, the round be unrated :) problems are interesting,but I have bad performance.

I know author is going to be blamed for this round. But honestly, I found the problems really beautiful and engaging. Kudos to author.

Good decision to announce the contest as unrated .

Thanks for very interesting problems! Can anyone tell me how to solve B?

Lets represent a, b, c...z as 1, 2, 3, ... 26. Now the best strategy is to club all a's together, all b's together etc. If you keep first all evens and then all odd terms, then we'll just have to worry about junction. For this you can find a pair of (even, odd) which differ by atleast 1.

Let's switch to numbers instead of characters, so the alphabet will be $$$0,1,2,\ldots 25$$$. Notice that a pair can only be ugly if one of them is odd and the other is even. First we have two cases if there're only odd or only even numbers, in that case we're done. Else we have at least one odd and one even number, intuitively we may want to minimize the touching of odds with evens so we may think about an order where first the even numbers then the odds come. This will only be possible if there's at least a pair of odd and even numbers that have a difference larger $$$1$$$ (since then we can put them in the middle and the rest can be placed arbitrarily) and obviously in the case when we have $$$0$$$ such pairs it would be impossible to order them (since in every ordering there is at least one odd-even pair), so we can see that the above statement is equivalent to that there's a valid reordering.

For everyone who got WA on test 7 (problem C), try this case:

10 2 1 2 3 4 5 6 7 8 9 10

Correct output: 5

I made a greedy solution (sort all the numbers using multiset, then for every number find the smallest number it can be connected to and erase both numbers from the multiset) and this case showed me that my approach was wrong. I hope it'll be helpful to someone.

what about z?

I put everything in one line. It should be:

10 2

1 2 3 4 5 6 7 8 9 10

Please point out the 5 pairs. TIA.

1, 6

2, 7

3, 8

4, 9

5, 10

Thanks, i couldn't find test.

A simpler test case to prove the greedy approach wrong is:

4 4

1 5 6 9

Thank you!

(Direct quote from Problem A) So can you pass the math test and enroll into Berland State University?

Um..... (sigh...)

after rejudged A

It was at this moment theroot knew, he fucked up xDD

I wanna be a yellow coder

me too

Why RE on test 16？ Code

I guess it is due to size of the array. As segment trees have around 4*N nodes.

Btw if possible then please explain your approach here!

So.. Any hint for C?

If you order the array and one of the best possible solution has some pairs with both indexes in the first half of the array, you can change one index of each this pairs be indexes of the second half of the array. And this new set of pairs still is one of the best solutions.

Same way if you have some pairs with both indexes in the second half.

Last contest I wrote a toxic comment and I'm really sorry for that because mistakes happens and we should understand that

Any hints for E ?

You can doing it using a Mergesort tree.

For each element Ai calculate the range in which it will be maximum. That is Li and Ri where Li is the highest index j < i such that Aj > Ai and similary Ri is lowest j > i such that Aj > Ai.

For each Ai, check each j in Li...i-1 to see if Ai — Aj exists between i+1...Ri using the mergesort tree. (You just have to maintain a set on each node in the Mergesort tree and check for each node in the range if the required value exists in its set).

Since for any j between Ai and Ri Lj >= i (as all elements from i...Ri <= Ai) so you'll be querying mergesort tree for each element only once. Each query takes logN*logN time.

Thus the complexity is N*logN*logN.

Not sure if easier approach exists.

"For each Ai, check each j in Li...i-1 " Can you please help me understand why this will not lead to O($$$n^2$$$)?

"Since for any j between Ai and Ri Lj >= i (as all elements from i...Ri <= Ai) so you'll be querying mergesort tree for each element only once."

Could you explain this part a little bit more? What if we have a situation like:

`[ ( y ) x ]`

Here x and y are two elements,

`[]`

indicate Lx and Rx and`()`

indicate Ly and Ry. Obviously, y < x. Evidently, we can construct such a case (for example, 10 5 6 7 132 894 11).In such a case, every element between Ly and y is queried twice (once because of y and once because of x). I thought of the same approach during the contest, but I didn't think it would work because of such cases.

I had a similar approach, but i think it is easier. For each element you calculate l[i] and r[i]. These numbers represent the range in which a[i] is the maximum element. To find this easily we can use a stack.

Then, for every i from 2 to N-1, we will do the following: Choose the smallest side in our range [l[i],r[i]]. ( Smaller between i — l[i] and r[i] — i ). Then we can try every number in this range with a "bruteforce" approach. To know if that number will make a valid solution, we need to check if its complement ( a[i] — a[j] ) its in the opposite side and inside the range in which a[i] is maximum.

This approach seems like bruteforce, but with a little bit of math you can confirm it is actually linear.

Code to understand the idea better : 53634108

"This approach seems like bruteforce, but with a little bit of math you can confirm it is actually linear. " can you please give a rough sketch of proof?

I think Li and Ri can be found using range maximum query inside a binary search..

It is faster and not hard to find them with a stack. ( Linear time ) You can read about it here: https://en.wikipedia.org/wiki/All_nearest_smaller_values

divide and conquer

I think that 53648275 is pretty short, easy to understood and

O(n log n)can you please explain your solution a little bit?

I used divide and conquer... $$$f[l, r)$$$ counts how many pairs $$$(i, j)$$$ exists such that $$$p_i+p_j=max(p_i...p_j)$$$ and $$$i < m <= j$$$ for $$$m = (l+r) / 2$$$, and again solve the problem for $$$f[l, m)$$$ and $$$f[m, r)$$$ recursively (cases when the condition $$$i < m <= j$$$ not is true).

So for a fixed $$$f[l, r)$$$ and $$$m = (l+r) / 2$$$ for every $$$l <= pl < m$$$ and $$$m <= pr < r$$$ the maximum of the interval $$$[pl, pr]$$$ is $$$max(max(pl...m-1), max(m...pr))$$$, i assume that the maximum is equal to $$$max(pl...m-1)$$$ this determine $$$pr$$$ of a unique way $$$(pr=max(pl...m-1)-pl)$$$ so you only need check if $$$[pl, pr]$$$ is a valid pair

But what about if $$$max(max(pl...m-1), max(m...pr)) == max(m...pr)$$$ not $$$max(pl...m-1)$$$ ?, then solve the same problem again but with the reverse of the array, because if the maximum is in the right part in the reverse will be in the left part :)

is selecting all possible $$$(pl, pr)$$$ doesn't lead to $$$O(n^2)$$$?

For a fixed $$$pl$$$ you can determine of a unique way the maximum (assuming that is in the left part) and then $$$pr=max(pl...m-1)-pl$$$. So you only need iterate all $$$l <= pl < m$$$

Can someone tell me why this submission got WA https://codeforces.com/contest/1156/submission/53640819

got it fails for this input 10 2 1 2 3 4 5 6 7 8 9 10

4 3` 1 6 9 10 test like this one will explain the WA for you, if it doesn't i made it clear here https://codeforces.com/blog/entry/66796?#comment-509109

is this unrated? as declared in announcement

If anyone wants to solve problem D using dfs 53633184.

would you please explain your approach

Divide the tree into connected components of edges of 0s and 1s.

Now, there will be three cases to sum:

case #1: the path contains edges of all 1s.

case #2: the path contains edges of all 0s.

case #3: the path contains some edges of 0s in starting then all 1s at end.

For case #1 and case #2 answer will be simply

`cnt1 * (cnt1 - 1)`

and`cnt0 * (cnt0 - 1)`

respectively.For case #3: select a center vertex containing both edges of 0s and 1s. Now, to form a valid path, you have to select first vertex from connected component of 0s and second vertex from connected component of 1s. Answer in this case will be

`(cnt0 - 1) * (cnt1 - 1)`

.`[ how ? center vertex will be counted in both components.]`

Thanks for explaining case by case.

How to solve B? What is the case when we don't get an answer??Please help guys

You need to take unique elements in string sort it and keep even indexes in first and odd indexes in second array. For example if string is "dcbab" then it would be like "ac" and "bd" and check if we can return it as "acbd" or "bdac" if two if this replacements are not possible then we return wrong answer, else we would return possible answer.

But how is this true ??

Because there if we take even and odd indexes of the unique string then there would be minimum 2 letters between them and if there is the size of the string is odd number it means last element of two arrays differ by 1. It means you check if which replacement is right array two-> array one or array one -> array two. And don't forget to print out the number of elements in the string

Cases when we don't get answer..

2

ab

abc

Critaical Test Cases you can check...

2

abd

acd

Output:

adb

cad

How to solve:

You can count the frequency of every letter from 'a' to 'z' in the input string... Then iterate through 'a' to 'z' and if count of it is not zero then insert it in a vector or string as you want... then take the even positions characters in vector1 and odd positions characters in vector2... then check if vector1+vector2 give you a valid solution or vector2+vector1 give you a valid solution if no one give a valid solution then, there exist no solution.. Hope you understand..

I'm a little bit confused. Isn't solution for problem F is to calculate number of winning and all combinations and just divide them?

What's halyavin doing?

in fact, Problem A is nice and trick. if you got WA... did you thought about this foken test case

:D?6 intersection Points, NOT 7also, the

InfiniteCases :But during the Contest:

Set_IQ(0);You didn't mark one of the six points in the first picture.

yes, sorry !

thanks

halyavin back in business.

Can anyone help me debug my solution for problem C

https://codeforces.com/contest/1156/submission/53644079

I get WA on test 7, is my idea completly incorrect ?

try case 10 5 1 2 3 4 5 6 7 8 9 10 ans=5

my code gives 5 too

Try test case:

4 4

1 5 6 9

Thanks!

Lmao waited for this contest ever since they messed the last one a couple of days ago just to mess this one again.

Maybe this might interest someone...

I solved problem B using random_shuffle

https://codeforces.com/contest/1156/submission/53634293

I thought of this solution but didn't have the balls to write it :D.

In tags of problem C I've seen ternary search.Can anybody explain how to use ternary search in this problem?

https://codeforces.com/contest/1156/submission/53646659 here is a solution using ternary search. it's very similar to the binary search one so i think it isn't necessary to do it using ternary search. i think the easiest solution is using two pointers technique, it's clear that it isn't optimal if we matched any number with another one has index below than n/2 because it may decrease our answer and we could match the two numbers with another two have indices above n/2, so we only have to start the first pointer from 0 and the other from n/2 and increase our answer whenever the condition happen and increase the two pointers too if the first pointer is below n/2, else we increase the second pointer until the condition happen or the second pointer reach n and here is a solution using two pointers https://codeforces.com/contest/1156/submission/53615906

if the solution has one peak or low on the middle of searching range, we can find that by ternary serach . when doing two pointer greedy rolling match p1 = 0 is optimal obviously, and choice of p2 have the property to do ternary search if choose 1 it is not good since best can only be 1 it will be optimal at some middle point and then be bad again at last part since some possible match will be in front of p2

can anybody help me on test 6, problem B plz :( thanks

You can Check the following testcase

2

abd

acd

Output:

adb

cad

Don't worry PikMike, we still love you!

+1D, E,andFwere really intersting. I guess without problemAwe could've had a great contest.So are B and C:)

Editorial?

Can someone tell we why I get a WA on test1 problemB My submission, it says that "wrong answer Resulting string should be a rearrangement of the given string" but I think my answer is correct!

Sorry, it's my fault

Prob.B

BOGO SORTΣ(っ °Д °;)っ53651542

The problems are really good, by the way, how to solve problem E?

My second unrated contest...

Can someone explain problem C using binary search?

After sorting the set of point x, you only need to look at begin and last N points while checking whether N can be an answer.

My submission

Thanks bro, i got it finally

You have no right to recognize a non-existent state Its name is Palestine, not Israel -_-

PikMike There is a bug in the checker of problem G!

It says "each character is a lowercase or an uppercase Latin letter, or a digit" in the statement, but if you use uppercase, you get WA!

Accepted 53671039 and Wrong answer on test 1 53671084 only differ by 1 byte.

I think you have no choice but to rejudge G and make this round unrated :(

I fixed the checker and rejudged your submission, it's ok now.

The problem G is 20 years old! It was offered by Maxim Babenko for Saratov internal contest. Now he heads development of the YT platform for distributed computing at Yandex. We studied in the same school, in parallel classes. I am very grateful to Maxim that he inspired me to learn programming in those years.

Loved the problems... keep taking such contests more... it was nice contest if we ignore issue on first problem