Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

By pikmike, 14 months ago, translation, ,

Hello Codeforces!

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 5th at 15.00 CET Time.

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

1. Between the ages of 12 to 18,
2. Have not graduated from high school
3. Eligible to take part in IOI/IMO 2020.
Register (before May 3) →

After the test, all participants will get a 20% discount link to attend Tech Scouts, the two-week summer camp we run from the 8th-19th 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 3rd, 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
153 successful hacks and 180 unsuccessful hacks were made in total!

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

• -164

 » 14 months ago, # |   +74 Every educational round ever
•  » » 14 months ago, # ^ |   +7 Don't worry. I am there.
 » 14 months ago, # | ← Rev. 5 →   -15 PikMike says, NEVER GIVE UP
 » 14 months ago, # |   0 Hope the problem set is going to be an interesting one like the last one :) Happy Coding
 » 14 months ago, # |   0 Round Professional 64 activated successfully !
 » 14 months ago, # |   +63 wtf?
 » 14 months ago, # | ← Rev. 2 →   +60
 » 14 months ago, # |   +28 the round should be unrated
 » 14 months ago, # |   +7 what is going on?
•  » » 14 months ago, # ^ |   +2 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
 » 14 months ago, # | ← Rev. 2 →   +57 To be honest, for long enough hasn't a problem A been so... chaotic.
 » 14 months ago, # | ← Rev. 6 →   +13 Is it rated? Rejudging affects >3000 people.UPD: Unrated.
 » 14 months ago, # |   +14 read first problem 10 times before seeing announcement. Feeling Irritated
 » 14 months ago, # |   0 I'm very upset today :(
 » 14 months ago, # |   +25 The round should be unrated, it's not ok that after 30 mins I see my AC code on A get WA
•  » » 14 months ago, # ^ |   +14 Literally everybody did though, I feel like it could still be rated, I don't know
 » 14 months ago, # |   +1 oh no.
 » 14 months ago, # |   0 Eventually, the round became unrated. :(
 » 14 months ago, # |   +16 Solve problems just for fun. ;)
 » 14 months ago, # |   +46 Authors, dont worry. Shit happens. Good luck to you
 » 14 months ago, # |   +10 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
•  » » 14 months ago, # ^ |   +16 Consider a triangle inside a circle inside a square.
•  » » 14 months ago, # ^ |   +13 But because the contest is running, the link can't be accessed.
•  » » 14 months ago, # ^ |   +10 3 1 2 is 6
•  » » » 14 months ago, # ^ |   0 Wow...that's really interesting.
•  » » » 14 months ago, # ^ |   0 thanks
 » 14 months ago, # |   +3 Got really happy after getting notification of round being unrated. Already many WA.
 » 14 months ago, # |   -8 should have been rated but oh well
 » 14 months ago, # |   +38 This round the highest Accepted on the entrance div2-A problem was 8. Out of 100! XD
 » 14 months ago, # |   +16 to be honest, this compitition has got a really chaotic 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.
 » 14 months ago, # |   0 without paying attention to solved problems, It won't change our rating , yeah?
•  » » 14 months ago, # ^ |   0 Right
•  » » 14 months ago, # ^ |   0 no, it won't.
 » 14 months ago, # |   +31 "_Unfortunately_, the round will be unrated."More like, Fortunately am i rite?
•  » » 14 months ago, # ^ | ← Rev. 2 →   +24 Absolutely, the Author even cant solve A. So irritating
•  » » 14 months ago, # ^ |   +11 some people say otherwise. :D
 » 14 months ago, # |   +67 happy coding ❤
•  » » 14 months ago, # ^ |   +19 this but with GCD, divisor and Number theory
•  » » » 14 months ago, # ^ | ← Rev. 2 →   0 Great guess . Here is the original picture ...
•  » » 14 months ago, # ^ |   0 Why not try to learn those stuff and be able to solve problems way over your rating range?
 » 14 months ago, # |   +3 Japanese people welcomed the new era, not error.
•  » » 14 months ago, # ^ |   0 love it
 » 14 months ago, # |   +52
 » 14 months ago, # |   +382 Literally half participants on problem A. ( including me )
•  » » 14 months ago, # ^ |   +24 This photo really swapped out my bad mood today. www
•  » » 14 months ago, # ^ |   0 TFW codeforces comment section is funnier than all of reddit.
 » 14 months ago, # |   +50
 » 14 months ago, # |   +5 Something went wrong...
•  » » 14 months ago, # ^ |   +5 Unfortunately, the contest is unrated(((
 » 14 months ago, # |   +45
 » 14 months ago, # |   +113 This year the highest grade on the entrance math test was 8. Out of 100!I guess now everyone knows why xD
 » 14 months ago, # |   0 What a mess.
 » 14 months ago, # | ← Rev. 6 →   +10 2 1 2is 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 top
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 No. The direction of the red triangle should be like the black one.
•  » » » 14 months ago, # ^ |   0 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.
•  » » » » 14 months ago, # ^ |   0 OK. But there is another announcement now.
•  » » » » 14 months ago, # ^ |   0 Yes, but you have drawn a equilateral triangle for which the height is not equal to the sides, so this configuration is impossible.
•  » » » » » 14 months ago, # ^ |   +2 this is my fault because of drawn misleading.even thought if drawn correctly, the answer may be 5 not 6. :D
•  » » 14 months ago, # ^ |   -23 No. Notice that "each triangle base is parallel to OX".
•  » » » 14 months ago, # ^ | ← Rev. 2 →   +15 Anyway, the base is still parallel :)
•  » » » » 14 months ago, # ^ |   -18 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.
•  » » » » » 14 months ago, # ^ |   +13 How can a vertex be parallel or not to a line?
•  » » » » » » 14 months ago, # ^ |   -10 If it does not intersect the line then it's parallel to the line :)
•  » » » 14 months ago, # ^ |   0 But just now there was an annoucementThe triangle is oriented in such a way that the vertex opposite to its base is at the top.
•  » » » » 14 months ago, # ^ |   +5 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 before the announcement because I had the tab open and didn't refresh.
•  » » » » » 14 months ago, # ^ | ← Rev. 2 →   0 yeah, you are right.maybe I should change my glassesUPD: 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.
•  » » » » » » 14 months ago, # ^ |   0 No, you don't have to do that; that state is revised, and before revising that, there was some vague state.
•  » » 14 months ago, # ^ |   0 Hehe, didn't even think of this one!
 » 14 months ago, # |   +11 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.
•  » » 14 months ago, # ^ |   +14 I did binary search for the number of matches k. Check by trying to pair the k smallest points with the k largest points.
•  » » 14 months ago, # ^ |   +11 just sort the array, and use two variables i and j. initialize i=0,j=n/2 and then just start pairing them.
 » 14 months ago, # | ← Rev. 2 →   +3 I want to experience how it feels like asking a solns of ongoing contest in comments. Here it goes -"How to Solve D??"
•  » » 14 months ago, # ^ | ← Rev. 2 →   +6 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.
•  » » » 14 months ago, # ^ |   +3 Why not to use DFS to find the components connected by 1 edges?
•  » » » » 14 months ago, # ^ |   0 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.
•  » » » 14 months ago, # ^ |   0 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.
•  » » » » 14 months ago, # ^ |   0 $S(m(m-1)) + S(mk)$ actually. Forgot to include it into the main comment, will edit in a few seconds ;)
•  » » 14 months ago, # ^ |   +14 I used Tree DP, with:dp[0][i]: number of 0-1 path whose lca is child of idp[1][i]: number of 1-path which ends at idp[2][i]: number of 0-path which ends at idp[3][i]: number of 0-1 path which ends at i and the edge connecting i is 1-edgedp[4][i]: number of 0-1 path which ends at i and the edge connecting i is 0-edge
•  » » 14 months ago, # ^ | ← Rev. 2 →   +13 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.
•  » » 14 months ago, # ^ |   +4 Lots of tree-DP problems based on paths have a standard procedure consisting of two steps: Solve the DP, but the DP of a vertex will only be restricted to the subtree of the vertex. Start changing the DP values from top to bottom, so that now, the DP of a vertex describes all paths originating at the vertex. There are only two cases — one, we have already included in our DP state, that the second vertex is a child of $v$, and the other is when the second vertex of the path is the parent of a vertex $p[v]$. 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.
 » 14 months ago, # |   +10 problem A (and other problems also) proved that every contestant is also a Labour. Happy Labour Day.
 » 14 months ago, # |   0 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?
•  » » 14 months ago, # ^ |   0 Think that there is "An inner circle of a triangle". It is always possible.
 » 14 months ago, # | ← Rev. 2 →   +12 fortunately, the round be unrated :) problems are interesting,but I have bad performance.
 » 14 months ago, # |   +83 I know author is going to be blamed for this round. But honestly, I found the problems really beautiful and engaging. Kudos to author.
 » 14 months ago, # |   0 Good decision to announce the contest as unrated .
 » 14 months ago, # |   +5 Thanks for very interesting problems! Can anyone tell me how to solve B?
•  » » 14 months ago, # ^ |   +5 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.
•  » » 14 months ago, # ^ |   +10 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.
 » 14 months ago, # |   +30 For everyone who got WA on test 7 (problem C), try this case:10 2 1 2 3 4 5 6 7 8 9 10Correct output: 5I 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.
•  » » 14 months ago, # ^ |   0 what about z?
•  » » » 14 months ago, # ^ |   0 I put everything in one line. It should be:10 21 2 3 4 5 6 7 8 9 10
•  » » 14 months ago, # ^ |   0 Please point out the 5 pairs. TIA.
•  » » » 14 months ago, # ^ | ← Rev. 2 →   +9 1, 62, 73, 84, 95, 10
•  » » 14 months ago, # ^ |   0 Thanks, i couldn't find test.
•  » » 14 months ago, # ^ | ← Rev. 2 →   +10 A simpler test case to prove the greedy approach wrong is:4 41 5 6 9
•  » » 14 months ago, # ^ |   0 Thank you!
 » 14 months ago, # | ← Rev. 2 →   +7 (Direct quote from Problem A) So can you pass the math test and enroll into Berland State University?Um..... (sigh...)
 » 14 months ago, # |   0 after rejudged AIt was at this moment theroot knew, he fucked up xDD
 » 14 months ago, # |   +5
•  » » 14 months ago, # ^ |   0 me too
 » 14 months ago, # | ← Rev. 2 →   0 Why RE on test 16？ Code
•  » » 14 months ago, # ^ |   0 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!
 » 14 months ago, # |   0 So.. Any hint for C?
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 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.
 » 14 months ago, # |   +13 Last contest I wrote a toxic comment and I'm really sorry for that because mistakes happens and we should understand that
 » 14 months ago, # |   +11 Any hints for E ?
•  » » 14 months ago, # ^ |   0 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.
•  » » » 14 months ago, # ^ | ← Rev. 2 →   0 "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$)?
•  » » » 14 months ago, # ^ |   0 "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 1 3 2 8 9 4 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.
•  » » » 14 months ago, # ^ | ← Rev. 3 →   +3 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
•  » » » » 14 months ago, # ^ |   0 "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?
•  » » » 14 months ago, # ^ | ← Rev. 2 →   0 I think Li and Ri can be found using range maximum query inside a binary search..
•  » » » » 14 months ago, # ^ |   +3 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
•  » » 14 months ago, # ^ |   +3 divide and conquer
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 I think that 53648275 is pretty short, easy to understood and O(n log n)
•  » » » 14 months ago, # ^ |   +11 can you please explain your solution a little bit?
•  » » » » 14 months ago, # ^ |   +6 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 pairBut 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 :)
•  » » » » » 14 months ago, # ^ |   0 is selecting all possible $(pl, pr)$ doesn't lead to $O(n^2)$?
•  » » » » » » 14 months ago, # ^ | ← Rev. 2 →   +3 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$
 » 14 months ago, # | ← Rev. 2 →   0 Can someone tell me why this submission got WA https://codeforces.com/contest/1156/submission/53640819got it fails for this input 10 2 1 2 3 4 5 6 7 8 9 10
•  » » 14 months ago, # ^ | ← Rev. 2 →   +1 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
 » 14 months ago, # |   -11 is this unrated? as declared in announcement
 » 14 months ago, # | ← Rev. 2 →   0 If anyone wants to solve problem D using dfs 53633184.
•  » » 14 months ago, # ^ |   0 would you please explain your approach
•  » » » 14 months ago, # ^ |   +1 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.]
•  » » » » 14 months ago, # ^ |   0 Thanks for explaining case by case.
 » 14 months ago, # |   +3 How to solve B? What is the case when we don't get an answer??Please help guys
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 14 months ago, # ^ |   0 But how is this true ??
•  » » » » 14 months ago, # ^ |   0 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
•  » » 14 months ago, # ^ |   0 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..
 » 14 months ago, # | ← Rev. 2 →   0 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?
 » 14 months ago, # | ← Rev. 2 →   0 What's halyavin doing?
 » 14 months ago, # | ← Rev. 2 →   +13 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 Infinite Cases :But during the Contest: Set_IQ(0);
•  » » 14 months ago, # ^ |   +1 You didn't mark one of the six points in the first picture.
•  » » » 14 months ago, # ^ |   0 yes, sorry !thanks
 » 14 months ago, # |   0 halyavin back in business.
 » 14 months ago, # | ← Rev. 3 →   0 Can anyone help me debug my solution for problem Chttps://codeforces.com/contest/1156/submission/53644079I get WA on test 7, is my idea completly incorrect ?
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 try case 10 5 1 2 3 4 5 6 7 8 9 10 ans=5
•  » » » 14 months ago, # ^ |   0 my code gives 5 too
•  » » 14 months ago, # ^ |   +3 Try test case:4 41 5 6 9
•  » » » 14 months ago, # ^ |   0 Thanks!
 » 14 months ago, # |   0 Lmao waited for this contest ever since they messed the last one a couple of days ago just to mess this one again.
 » 14 months ago, # |   0 Maybe this might interest someone...I solved problem B using random_shuffle https://codeforces.com/contest/1156/submission/53634293
•  » » 14 months ago, # ^ |   +17 I thought of this solution but didn't have the balls to write it :D.
 » 14 months ago, # |   0 In tags of problem C I've seen ternary search.Can anybody explain how to use ternary search in this problem?
•  » » 14 months ago, # ^ | ← Rev. 4 →   +3 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
•  » » 14 months ago, # ^ | ← Rev. 2 →   0 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
 » 14 months ago, # |   0 can anybody help me on test 6, problem B plz :( thanks
•  » » 14 months ago, # ^ |   +3 You can Check the following testcase 2 abd acd Output: adb cad
 » 14 months ago, # |   +65 Don't worry PikMike, we still love you!
•  » » 14 months ago, # ^ |   +18 +1
 » 14 months ago, # |   +20 D, E, and F were really intersting. I guess without problem A we could've had a great contest.
•  » » 14 months ago, # ^ |   +15 So are B and C:)
 » 14 months ago, # |   0 Editorial?
 » 14 months ago, # |   0 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!
•  » » 14 months ago, # ^ |   +3 Sorry, it's my fault
 » 14 months ago, # |   +5 Prob.BBOGO SORT Σ(っ °Д °;)っ53651542
 » 14 months ago, # |   0 The problems are really good, by the way, how to solve problem E?
 » 14 months ago, # |   0 My second unrated contest...
 » 14 months ago, # |   0 Can someone explain problem C using binary search?
•  » » 14 months ago, # ^ |   0 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
•  » » » 14 months ago, # ^ |   0 Thanks bro, i got it finally
 » 14 months ago, # | ← Rev. 4 →   +1 You have no right to recognize a non-existent state Its name is Palestine, not Israel -_-
 » 14 months ago, # | ← Rev. 2 →   +8 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 :(
•  » » 14 months ago, # ^ |   +13 I fixed the checker and rejudged your submission, it's ok now.
 » 14 months ago, # |   +36 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.
 » 14 months ago, # |   0 Loved the problems... keep taking such contests more... it was nice contest if we ignore issue on first problem