### antontrygubO_o's blog

By antontrygubO_o, 6 weeks ago,

I hope you enjoyed the round.

While problem D1B was good for balance in Div1, it was too hard for balance in Div2. I apologize for this.

Problem D1B = D2D is by dario2994. Other problems are mine.

D2A
D2B
D2C/D1A
D2D/D1B
D2E/D1C
D2F/D1D1
D1D2
D1E

• +250

 » 6 weeks ago, # |   -7 If you are/were getting a WA/RE verdict on problems from this contest, you can get the smallest possible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table (or edit compressed parameters) to increase/decrease the constraints.Divison 2 Divison 1 If you are not able to find a counter example even after changing the parameters, reply to this thread (only till the next 7 days), with links to your submission and ticket(s).
•  » » 6 weeks ago, # ^ | ← Rev. 4 →   0 I can't find the test case.I got wa on 177th token of 2nd test.Please tell me the test case,this is my submission id:158470917
•  » » » 6 weeks ago, # ^ |   +14 Consider this testcase in Ticket 7727.What's special about this testcase? All numbers are in $[0, 3]$, and $sum(array) = Length(arr)$. Hence, if you partition the array at $1$, the AM would be $49/49$, which would convert all numbers to 1. Hence, the answer is YES, but your code prints NO.
•  » » » » 6 weeks ago, # ^ |   0 Thankyou so much,can you please tell me what's wrong with my code,as far as i see the logic seems to correct as well.But somehow the value stored in my 'ms' variable doesn't end up in it,and it doesn't get checked at all ,not until i try to print it externally.
•  » » » » » 6 weeks ago, # ^ |   0 precision error) i've change your code a little and it passed tests 158518313
•  » » » » » » 6 weeks ago, # ^ |   0 Thankyou so much sir,you are a godsend!
•  » » 6 weeks ago, # ^ |   +5 It says "Python supported has been temporarily disabled..." for Div2 A
•  » » » 6 weeks ago, # ^ |   -7 It's because I haven't added Python support yet. It's enabled in the development environment, but not in production.
•  » » 6 weeks ago, # ^ |   0 I cannot find the test case responsible for my WA.https://codeforces.com/contest/1685/submission/158616772 is the link to my submission.
•  » » » 6 weeks ago, # ^ |   +1 Here's a simple failing testcase: Ticket 8222
•  » » » » 6 weeks ago, # ^ |   0 Thank you. This was helpful!
 » 6 weeks ago, # |   +1 Very good problems! I like this types problems!
•  » » 6 weeks ago, # ^ |   +47 But my friends who wrote contest dont think so
•  » » » 6 weeks ago, # ^ |   +15 Oh yeah, Mr.Bebra, I totally agree with you! Problems were very good!
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   -16 I don't like this type of problem. They are too ad-hoc. Algorithmic problems are better.
•  » » » 6 weeks ago, # ^ |   0 what does it means, ad-hoc? I wonder!
•  » » » » 5 weeks ago, # ^ | ← Rev. 3 →   0 https://www.geeksforgeeks.org/what-are-ad-hoc-problems-in-competitive-programming/ Div 2 problems are mostly this type of problem. But I don't like them, I know I will get downvoted if I say that, so I create an alt to comment.
 » 6 weeks ago, # |   +97 I just realized on reading this that reversing a substring in D1C means actually reversing order of the substring, not flipping every bracket in the substring :(Would have been nice to have a sample/statement exactly capturing that, though (I think none of the samples differentiate between these two interpretations?)
•  » » 6 weeks ago, # ^ |   +8 I made the same mistake as well. I wrote and submitted a solution using stack that solves the flip problem (158461024). Not sure about correctness though.
•  » » 6 weeks ago, # ^ |   0 Silly in retrospect, but I also made the same mistake.
•  » » 6 weeks ago, # ^ |   0 the same as me
•  » » 5 weeks ago, # ^ |   0 I'm curious to know the soln to the flipping-version.
 » 6 weeks ago, # | ← Rev. 2 →   -51 .
 » 6 weeks ago, # |   +24 I personally like adhoc problems, and do best when the problems require less topic-specific knowledge, less coding, and more thinking. Not everyone agrees, but I loved Div 2D.
•  » » 6 weeks ago, # ^ |   -119 who tf asked?
•  » » » 6 weeks ago, # ^ |   +71 If every comment was something somebody asked for, codeforces would be a silent place, my silly friend.
•  » » » » 6 weeks ago, # ^ |   +13 Exactly!
•  » » » 6 weeks ago, # ^ |   +8 If you can't say something good, don't speak at all. -Eminem
 » 6 weeks ago, # |   +27 I didn't like the problem names. They were boring.
•  » » 6 weeks ago, # ^ |   -35 you are boring
 » 6 weeks ago, # |   +16 How many constructives?"Yes"
 » 6 weeks ago, # |   +28 How did you write the checker in 1685E - The Ultimate LIS Problem?
•  » » 6 weeks ago, # ^ |   +70 If exactly one of jury and participant found such k after some update, check if that k works, and return with WA or fail.Otherwise, look at the instances where ks found by jury and participant were different. Briefly, check random ~1000 of them.This approach doesn't guarantee that submission will give WA even if its output is incorrect, so we disabled hacks.
 » 6 weeks ago, # |   +37 For 1686A - Everything Everywhere All But One, suppose the number to be excluded is at index $r$, we require: $\dfrac{\sum_{i \neq r} a[i]}{n-1} = a[r]$ $\implies \sum_{i \neq r} a[i] = a[r] \cdot (n-1)$ $\implies \sum_{i} a[i] = a[r] \cdot n$Therefore, the required condition becomes: $\dfrac{\sum_{i} a[i]}{n} = a[r]$Which is the same as asking the question $\text{Is the average of the list present in it?}$Nothing new here i suppose, but I found this easier to code than what's in the editorial. Codeint sum = std::accumulate (arr.begin( ) , arr.end( ) , 0 ); if(sum % n == 0 && find(arr.begin(), arr.end(), sum/n) != arr.end()) { cout << "YES" << endl; } else{ cout << "NO" << endl; } Complete code: 158477863
•  » » 6 weeks ago, # ^ |   +1 This is how I solved it and I think this approach is much more elegant!
 » 6 weeks ago, # |   +102 Problem D can be generalized further: given $n$ pairs of (arbitrary) integers $(a_i, b_i)$, find the (lexicographically minimal) permutation $q_i$ which minimizes $\sum_{cyc} \lvert a_{q_i} - b_{q_{i+1}}\rvert$. In this phrasing, this problem is quite similar to IOI 2016 railroad.Consider the graph with 1 vertex per integer. Let's view the pair $(a_i, b_i)$ as a directed edge from $a_i$ to $b_i$. Now, we want to add the minimum number of directed edges $i \to i+1$ or $i+1 \to i$ so that we can form a valid Eulerian tour through all edges. To do this, we should first make sure that the number of edges crossing between each integer in each direction is balanced (in problem D, this is always the case, since all given vertices have indegree and outdegree equal to $1$). Then, we need to add the minimum number of pairs of edges $i \to i+1$ and $i+1 \to i$ to make the graph connected, which reduces to minimum spanning tree.We can still find the lexicographically minimal permutation in $O(n^3)$ time by trying to add each possible next edge, and checking if it's still possible to finish the Euler tour, which turns out to only require checking some connectivity conditions.
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 Good job!I also remembered this problem, but decided not to open the editorial (which was a mistake). I think this reasoning is much easier to understand than the one from this blog.To clarify, we have directed edges $(b_i, a_i)$ and want to construct edges $(a_i, b_{i+1})$ for some permutation to minimize length of euler tour. Turns out, for me it was hard to understand how to fulfill the condition that each node must have one ingoing and one outgoing edge (which is kind of necessary to construct a solution). The proof is: construct an euler tour (it is necessary to have balances zero and graph connected, and it is also sufficient — even with big edges $(b_i, a_i)$ that are actually not many small ones, because indegree is still equals to outdegree for nodes in between segment $(b_i, a_i)$), write down all edges $(b_i, a_i)$ in order of euler tour, now part of euler tour between $a_i$ and $b_{i+1}$ is some path in line graph, but since we minimize the length (which is key) this path must be straight segment, so its actually $|a_i - b_{i+1}|$ which is exactly what we need.Its a bit different from the IOI problem because we were allowed to travel back and forth, so the length might not be $|a_i - b_{i+1}|$, but again, because of minimization its always the case.
•  » » 6 weeks ago, # ^ |   0 Could you please explain a reduction from original problem to "we want to add the minimum number of directed edges so that we can form a valid Eulerian tour through all edges." in more details? The most unclear part is how to calculate the weight of the $q$ from the original problem using our Eulerian tour.
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   +10 We can think of $\lvert b_{q_i} - a_{q_{i+1}} \rvert$ as the number of new $x \leftrightarrow x+1$ edges we need to move from the tail of edge $q_i$ to the head of edge $q_{i+1}$. Thus, a particular set of extra edges and an Euler tour corresponds to the permutation $q$ of the original edges in the order visited, and the weight is the number of extra edges.
 » 6 weeks ago, # | ← Rev. 2 →   -26 Why I couldn't see editorial in div2's Contest materials? plz fix it :)upd：now I can see it, thanks for fixing it!
 » 6 weeks ago, # |   +6 Best contest I've ever wrote. Really nice problems!
 » 6 weeks ago, # |   +13 I hate linguistics now.
•  » » 6 weeks ago, # ^ |   0 same
•  » » 6 weeks ago, # ^ |   0 same
•  » » 5 weeks ago, # ^ |   -10 same
 » 6 weeks ago, # |   +6 For some reason, understanding the explanations in this editorial itself seems difficult, for me :(
•  » » 6 weeks ago, # ^ |   0 Hoping this helps, Video Solution for D.
 » 6 weeks ago, # |   +21 Really wondering how the top 100 come up withKey observation: It's always possible to get a balanced sequence in at most 2 operations.in contests in a couple of minutes...
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   0 It is pretty well-known problem, so we can easily get how to make it under 3 reverses. Then we just have to think if we are able to make it in less reverses. D1C is actually a good problem, unfortunately I didn't manage to solve it during contest because of D1B...
•  » » » 6 weeks ago, # ^ |   +1 What well-known problem?
•  » » » 6 weeks ago, # ^ |   0 Perhaps I find it. Is it the cyclic shift in editorial of E?
•  » » » » 5 weeks ago, # ^ |   0 Yes, the same idea was used in one of the last ARC link
 » 6 weeks ago, # |   0 "wrong answer Jury found the answer but participant didn't (test case 1435)" this verdict on 3rd problem test case 2. Where did I go wrong? Submission--> 158448669
•  » » 6 weeks ago, # ^ |   +10 I got the following test case using CF Stress.
•  » » » 6 weeks ago, # ^ |   +8 Thanks!
•  » » » 6 weeks ago, # ^ |   0 how to check this?? because i want to check test case 21950
•  » » » » 6 weeks ago, # ^ |   +10 You probably cannot check this large numbered test case on Codeforces. If you want to find out some other test case where your solution is failing, you can visit CF Stress and stress test your solution there.
 » 6 weeks ago, # |   0 Implementation ?
 » 6 weeks ago, # |   -9 Awesome contest.Thanks antontrygubO_o
 » 6 weeks ago, # |   +47 How can one notice that the answer is at most 2 in D2E/D1C? I wouldn't have ever guessed that if I didn't look at the solution. How to come up with this myself?
•  » » 6 weeks ago, # ^ |   +14 Personally I didn't come up with this during the contest (I solved this problem in a different way). But I think this is how you could come up with it: You see the opening brackets as +1 en closing as -1 and look at the prefix sum. This is the first thing you should always think about with these kind of bracket problems. Draw a few graphs of these prefix sums and see what happens if you reverse a sub string. The first thing you can notice is that it rotates a part of the prefix sum graph by 180 degrees. The second thing you can notice is that if the part of the sub string you reverse starts with a prefix of 0 and ends with a prefix of X, then if there is no prefix greater then X this part of the sub string will have a prefix where every value is greater then 0. (Because of the rotating by 180 degrees) Because of this you can always find an answer of 2, by reversing everything before the greatest prefix sum, and everything after that.For my solution I made all of these insights, except the last one that the answer is at most 2.
•  » » 6 weeks ago, # ^ |   +30 The easiest (but boring) way is to write a brute force.
•  » » » 5 weeks ago, # ^ |   -15 What is the brute method?
 » 6 weeks ago, # |   0 Hey can anyone tell me what is wrong with my code, it is giving wrong ans on pretest 2 sort(all(arr)); vi a; fori(i, 0, n / 2) { a.pb(arr[i]); } vi b; fori(i, n / 2, n) { b.pb(arr[i]); } if ((n % 2) == 0) { fori(i, 0, n / 2) { if (!i) { if (a[i] >= b[i]) { noo; return; } } if ((a[i] >= b[i]) || (a[i] >= b[i — 1])) { noo; return; } } yess; fori(i, 0, n / 2) { cout << a[i] << " " << b[i] << " "; } nl; return; } noo;
 » 6 weeks ago, # |   +5 Problem (1686A — Everything Everywhere All But One) can be solved simply by computing the average of that array as avg (type: double), then searching for avg in the array (normal search: O(n/2), binary search: (O(log2(n)), although the normal search is enough to accept. Isn't it simpler than the tutorial?P/S: sorry for my bad English, I translated it myself.
•  » » 6 weeks ago, # ^ |   +3 Two points I would like to highlight: You could use data type int instead of double. First check if the remainder of the division is NOT 0. In that case, the answer is NO. If the remainder is 0, compute the integral quotient and search for it in the array. The binary search approach would be more expensive than a linear scan as it would require an O(nLogn) sort prior to the search.
•  » » » 6 weeks ago, # ^ |   0 Thank you for your reply, I personally found it really useful for me. I totally agree with you the second point. About the first one, I tried use int datatype but failed (because it rounded avg), then I used double I got accepted.
•  » » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 Yes, if you directly store avg in an int variable, you would have a problem with rounding off. That is why I suggested to first check if the sum is divisible by n. If it is not divisible, the answer to that test case would be NO directly. If it is divisible, then the quotient is an integer anyway, so you wouldn't face any rounding errors. Here is my implementation for more clarity: 158422758UPD: Added a link to my implementationHope that helps :)
•  » » » » » 6 weeks ago, # ^ |   0 Wow thanks a lot for your comment! It actually better than mine. I will remember it! Thank you again :]
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 Can you explain why this approach works? I'm unable to figure out the maths behind it. I mean, why it works for second or third iteration of the operation?
•  » » » 5 weeks ago, # ^ |   0 When the array equal, there will be at least one element left unchanged, and the average of the array never change so we have 2 things that never change, then we can use it to solve the problem. P/S: sorry if you can't understand the above, but I can't make it more clear for you as English is not my native language.
 » 6 weeks ago, # |   0 Can anyone please help me on how to solve problem D, in Div2?
•  » » 6 weeks ago, # ^ |   0 Actually D is easier than it looks. If you are confused on proof part, here is an intuition. If you want to take BA from Type 2, it'll be better to take it from larger sizes as 1 will be wasted everytime you take from any. So while taking AB from type 2, take from smallest everytime. That's exactly what he is proving.
 » 6 weeks ago, # |   0 I am going through question Div 2 question D and I am literally so confused. I used the stress test and it said: 2 2 5 4 BABABABABAAABBABAABBAB is YES while my code gives false I tried grouping it by hand but I literally can't find how this is true.
•  » » 6 weeks ago, # ^ |   0 okay sike I literally figured it out lmao it is (BA)(BA)B(AB)(AB)AA(AB)(BA)(BA)(AB)B(AB)
 » 6 weeks ago, # |   0 Can someone help me with Div2 C
 » 6 weeks ago, # |   0 Thanks for the contest, I enjoyed it a lot! Why in the "Linguistics" task we don't check the same initial condition for the letter "B"? Moreover, in the editorial it is said we are sure that the number of characters A and B is correct because of the initial check. I imagine a=1, b=0, c=1, d=1, and a string AABBABBBB. a + c + d = 3, it passes the initial check. But we see we don't have enough B's.
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   +3 If the count of A is correct then count of B will always be correct because $a+b+2*c+2*d = len(s).$ In the example you mentioned, the above condition is not satisfied, so it's not a valid test case.
•  » » » 6 weeks ago, # ^ |   0 ooook, that's, actually, given to us as a condition. Thanks a lot!
 » 6 weeks ago, # |   0 would you please tell me about the test case 1435 in test case 2 of problem C from div2? :(
•  » » 6 weeks ago, # ^ |   0 Wait, mine 1432 is wrong. And I compared my solution to the solutions accepted. It kinda looks similar.
•  » » 6 weeks ago, # ^ | ← Rev. 3 →   0 62 2 1 1 0 0 63 2 1 1 0 0 Here mate.1435 and next one
•  » » 6 weeks ago, # ^ |   0 Bro same issue I'm facing.....my 1435th token in test case 2 is giving WA. If u get it please tell me too
•  » » » 6 weeks ago, # ^ |   0 I replied the test cases in my message above
•  » » » » 6 weeks ago, # ^ |   0 Thanks, Got it!!
 » 6 weeks ago, # |   +11 My solution for problem D(Linguistics) and an attempt to explain it. ApproachThere are some checks that we need to make for determining whether the given string is valid. Check 1: Number of A(s) must be a+c+d.Note that it if this is true then we don't need to check the number of B(s). Check2: We need to have at least c positions, say i, where s[i]=='A' and s[i+1]=='B'. We also need to have at least d positions where s[i]=='B' and s[i+1]=='A'. We also need to be sure that these positions are not overlapping and are disjoint. For example: If the string was ABA, we have one position where AB starts and one position where BA starts according to our check but notice that we can't count both AB and BA. So the positions should be disjoint. Let's suppose that the first check is true. Now the problem is selecting at least c+d disjoint positions out of which at least c are AB and at least d are BA. Observation: - The overlapping will result in consecutive chains of ABA.. or BAB.. of different sizes in which their count will always differ by at most one. We can greedily select d positions for BA which will eliminate minimum AB positions. Finally if still valid AB positions is less than c then the answer is NO. These are the types of chains in which we are interested in: 1. Number of B=1 and number of A=0. (B) 2. Number of B=p and number of A=p and p!=0. (A-B-A-B-A-B) 3. Number of B= 1+ number of A = p and p!=1. (B-A-B-A-B) 4. Number of B= number of A -1 = p and p!=1. (A-B-A-B-A) Selecting from type 1 eliminates no A. Selecting from type 2 eliminates 1 A for each B. Selecting from type 3 eliminates 1 A for the first p-1 B and none for the last one Selecting from type 2 eliminates 2 A for the first B and 1 for the rest Greedy Strategy: While number of BA positions is less than d. - Select as many as possible(one by one till less than d) from type 1. - Select as many as possible(one by one till less than d) from type 3 sorted in increasing order by number of B. - Select as many as possible(one by one till less than d) from type 2. - Select as many as possible(one by one till less than d) from type 4 sorted in decreasing order by number of B. Finally check whether the number of valid AB positions is less than c. My Submission158512740This is my first time explaining a solution in writing on Codeforces. Suggestions are welcome and please point out the mistakes.
•  » » 5 weeks ago, # ^ |   0 The number of values from type I will always be zero right as there are no A's
•  » » » 5 weeks ago, # ^ |   0 No, there will be such chains, these are the indexes which are already disjoint that is they have no neighbouring A.
 » 6 weeks ago, # |   0 **I can't find the test case. I got WA on the 1435th token of the 2nd test. Please tell me the test case,this is my submission id:158613119 **
•  » » 6 weeks ago, # ^ |   0 One of the simple failing test case is Ticket 8284
•  » » » 6 weeks ago, # ^ |   0 Thanks, Got it!!
 » 6 weeks ago, # |   0 The round shows that it has become unrated. Is it true?
 » 6 weeks ago, # |   +10 For anyone trying to upsolve D1D2: In the editorial for problem D1D2 it gives a list of criteria that is sufficient, but when I tried implementing it I got wrong answer. I think they forgot one constraint: "There is no $x$ such that there is a left segment $i$ with $l_i < x < r_i$ and a right segment $i$ with $l_i < x < r_i$.
 » 5 weeks ago, # |   0 Can anyone tell me that in the proof part of div2D,what's the meaning of "+" and "$\sum$" in $\sum_{u\in U}f(u) + \sum_{v\in V}f_{AB}(v) + \sum_{w\in W}f_{BA}(w)$,are they equivalent to $\cup$ here?
•  » » 4 weeks ago, # ^ |   +1 I think, it means following:Suppose we have two multisets of pairs of numbers A and B. For exapmle, A = {(0, 1), (0, 1)} and B = {(5, 2), (0, 7), (3, 11)}. A ∪ B = {(0, 1), (0, 1), (5, 2), (0, 7), (3, 11)} (size of this multiset is size(A) + size(B)). But A + B is a multiset consisting of all such pairs (x, y) that there exist a pair (x_a, y_a) ∈ A, pair (x_b, y_b) ∈ B and x_a + x_b = x, y_a + y_b = y (i.e. (x_a, y_a) + (x_b, y_b) = (x, y)). In my example A + B = {(5, 3), (0, 8), (3, 12), (5, 3), (0, 8), (3, 12)} (size of this multiset is size(A) * size(B)).
•  » » » 4 weeks ago, # ^ |   +5 Thanks for reply.You are right,it means that (c,d) must be in the multiset of all possible combinations of valid pairs from three types of strings.
 » 5 weeks ago, # |   0 Div2, Problem Ahttps://codeforces.com/contest/1686/submission/158501965I got WA in the 2nd test. Can someone kindly tell/give an array where my code won't work? My logic was, for a sorted array the mean value will be at the center. So I considered the middle value and checked if the (sum-mid value)/(n-1) = mid value. If not, then answer is No, else Yes.
•  » » 5 weeks ago, # ^ |   0 n=5, a=[1,1,1,2,5]It should answer yes, because 2 is the array mean and it is present in the array, but your code will answer no because 2 is not in the middle.
•  » » » 5 weeks ago, # ^ |   0 Ah yes, you are right. Thank you.
•  » » 5 weeks ago, # ^ |   0 You mixed up mean and median. In this problem mean is the average of some values, not the middle element.
•  » » » 5 weeks ago, # ^ |   -10 Yes my logic was not correct. I had to check all the elements. Thanks.
 » 5 weeks ago, # |   0 For Problem C(DIV-2) , check for this test case , 1 2 3 3 5 6 .you will get the answer. Thank you!
 » 5 weeks ago, # |   -10 Sounds crazy, problem F in div.2 we can solve it in $\mathcal{O}(n\log n)$ just like the editorial. But the limit of $n$ is $\sum n\leq400$. It's really crazy!
 » 5 weeks ago, # |   -10 I'm getting Time limit exceeded error on test 2 of Circular local minimax(D2C) problem. Can anyone help me how should i reduce that. I'm typing in java. import java.util.*; import java.io.*; public class Minimax { int[] circ(int x,List ary) { int i,j; int p,c=0; int a[]=new int[x]; int b[]=new int[x]; int z[]={0,0}; for(i=0;i=x/2) return z; else return b; } else return b; } } public static void main(String args[])throws IOException{ Scanner sc=new Scanner(System.in); BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); long n=Long.parseLong(br.readLine()); int i,j,x,y,z; List list; List ary; list=new ArrayList(); ary=new ArrayList(); StringTokenizer st; Minimax a=new Minimax(); for(i=0;i
 » 5 weeks ago, # |   0 159346667 I am getting an error in the 1435 test case. I'm not able to figure out whats wrongs. would appreciate if someone could help. [problem:D1A]
•  » » 5 weeks ago, # ^ |   0 Sure, take a look at Ticket 10244 for a counter example.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 your approach is wrong ,the correct array construction is like that:if sorted a=[1,2,3,4,5,6] then split a into two halves like that a1=[1,2,3] and a2=[4,5,6] .then fill the circle alternatively between a1 and a2 starting from a1 ,so answer = [1,4,2,5,3,6].`
•  » » » 4 weeks ago, # ^ |   +3 got it thank you guys
 » 4 weeks ago, # |   +10 In d1D2 I think a condition is left out by the editorial: for $1\le i\le n$, if $i$ is covered by two segments (we know they are a left segment and a right segment), it's an endpoint of one of the two segments. This guarantees $i$ is in the correct cycle in graph $G$.For example let's consider $p=[1,4,3,6,5,2]$, and $[1,3,5]$ as a prefix of $q$. We have a left segment $[1,3]$ and a right segment $[1,3]$. $[1,3,5]$ is a possible prefix for an optimal $q$ according to the five conditions in the editorial, but in fact we see $1$ and $3$ make up a cycle without $2$. By the way, the answer of $p=[1,4,3,6,5,2]$ is $q=[1,3,6,4,5,2]$.The proof that the six conditions are enough is left to the reader as an exercise. x
 » 3 weeks ago, # |   0 This is my submission id 160783559 for problem number 3 : Circular Local MiniMax.please show me the wrong test case(test case 2 : 1435th).
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   0 int32_t main(){ fastint t=1; cin>>t; while(t--){ll i,j,k=0,s,a,b,c,n,x,y,z; vectorv; cin>>n; ll arr[n+1]; fl(i,n)cin>>arr[i]; sort(arr,arr+n); if(n%2!=0||arr[(n)/2-1]>=arr[(n)/2])cout<<"NO"<
 » 9 days ago, # |   +10 For the D1B proof, shouldn't the $k$ in $(c, d) \in f\Bigg(\sum_{u\in U} k + \sum_{v' '\in V\setminus V'} (v' ' - 1) + \sum_{w' '\in W\setminus W'} (w' ' -1)\Bigg) + \bigg(\sum_{v'\in V'} v', 0\bigg) + \bigg(0, \sum_{w'\in W'} w'\bigg)$ be $u$?
•  » » 8 days ago, # ^ |   +10 I'm also a bit confused on the function $f$ used in that proof. In the three subcases, you define the input to $f(k)$ as $\lfloor \frac{|t|}{2} \rfloor$. (ex. $|t|=2k+1$ for case 1) However, in the equation $(c, d) \in \sum_{u\in U} f(u) + \sum_{v\in V} f_{AB}(v) + \sum_{w\in W} f_{BA}(w)$ and subsequent lines, the entire length of each string is plugged into $f$. As defined, $U$, $V$, and $W$ are "the multisets of lengths of strings of the first, second and third type respectively."
•  » » » 8 days ago, # ^ |   0 @dario2994 I guess
•  » » » » 8 days ago, # ^ | ← Rev. 2 →   0 Fixed the typo "$k$ instead of $u$" in two places. Thank you for pointing it out.You have misunderstood the definition of the function $f$. $f(k)$ is not a number, it is a set of pairs (as defined in the editorial).
•  » » » » » 7 days ago, # ^ |   +10 Thanks for replying! Just to clarify, I wasn't asking about $f(k)$, but rather about $k$ itself. Based on your initial definitions of $f$, shouldn't $(c, d) \in \sum_{u\in U} f(u) + \sum_{v\in V} f_{AB}(v) + \sum_{w\in W} f_{BA}(w)$ be turned into $(c, d) \in \sum_{u\in U} f(\frac{u-1}{2}) + \sum_{v\in V} f_{AB}(\frac{v}{2}) + \sum_{w\in W} f_{BA}(\frac{w}{2})$?Sorry if I wasn't clear the first time.Also, your fixes aren't showing up in the above editorial for some reason...
•  » » » » » » 7 days ago, # ^ |   0 You are totally right, my mistake. Now it should be fixed (changed the definition of the sets $U, V, W$).Sooner or later my fixes should be propagated to this post. If it does not happen in a couple of days, I will try to fix it.
•  » » » » » » » 92 minutes ago, # ^ |   0 Thanks! I don't seem to see your changes though, and it's been a week...