antontrygubO_o's blog

By antontrygubO_o, 18 months 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

| Write comment?
 » 18 months 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).
•  » » 18 months 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
•  » » » 18 months 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.
•  » » » » 18 months 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.
•  » » » » » 18 months ago, # ^ |   0 precision error) i've change your code a little and it passed tests 158518313
•  » » 18 months ago, # ^ |   +5 It says "Python supported has been temporarily disabled..." for Div2 A
•  » » 18 months 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.
•  » » » 18 months ago, # ^ |   +1 Here's a simple failing testcase: Ticket 8222
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 variety-jones activate my subscription or please tell why this giving wrong submission
•  » » » 12 months ago, # ^ |   0 Your subscription has been activated.Take a look at Ticket 16548 from CF Stress for a counter example.
 » 18 months ago, # |   +1 Very good problems! I like this types problems!
•  » » 18 months ago, # ^ |   +47 But my friends who wrote contest dont think so
•  » » » 18 months ago, # ^ |   +15 Oh yeah, Mr.Bebra, I totally agree with you! Problems were very good!
•  » » 18 months ago, # ^ | ← Rev. 2 →   -16 I don't like this type of problem. They are too ad-hoc. Algorithmic problems are better.
•  » » » 18 months ago, # ^ |   0 what does it means, ad-hoc? I wonder!
 » 18 months 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?)
•  » » 18 months 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.
•  » » 18 months ago, # ^ |   0 Silly in retrospect, but I also made the same mistake.
•  » » 18 months ago, # ^ |   0 the same as me
 » 18 months ago, # | ← Rev. 2 →   -51 .
 » 18 months 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.
•  » » 18 months ago, # ^ |   -119 who tf asked?
•  » » » 18 months ago, # ^ |   +71 If every comment was something somebody asked for, codeforces would be a silent place, my silly friend.
•  » » » » 18 months ago, # ^ |   +13 Exactly!
•  » » » 18 months ago, # ^ |   +8 If you can't say something good, don't speak at all. -Eminem
•  » » » 17 months ago, # ^ |   0 i asked
 » 18 months ago, # |   +27 I didn't like the problem names. They were boring.
•  » » 18 months ago, # ^ |   -35 you are boring
 » 18 months ago, # |   +16 How many constructives?"Yes"
 » 18 months ago, # |   +28 How did you write the checker in 1685E - Лучшая задача о LIS?
•  » » 18 months 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.
 » 18 months ago, # |   +37 For 1686A - Всё везде кроме одного, 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
•  » » 18 months ago, # ^ |   +1 This is how I solved it and I think this approach is much more elegant!
 » 18 months 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.
•  » » 18 months 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.
•  » » 18 months 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.
•  » » » 18 months 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.
 » 18 months 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!
 » 18 months ago, # |   +6 Best contest I've ever wrote. Really nice problems!
 » 18 months ago, # |   +13 I hate linguistics now.
•  » » 18 months ago, # ^ |   0 same
•  » » 18 months ago, # ^ |   0 same
•  » » 18 months ago, # ^ |   -10 same
 » 18 months ago, # |   +6 For some reason, understanding the explanations in this editorial itself seems difficult, for me :(
•  » » 18 months ago, # ^ |   0 Hoping this helps, Video Solution for D.
 » 18 months 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...
•  » » 18 months 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...
•  » » » 18 months ago, # ^ |   +1 What well-known problem?
•  » » » 18 months ago, # ^ |   0 Perhaps I find it. Is it the cyclic shift in editorial of E?
•  » » » » 18 months ago, # ^ |   0 Yes, the same idea was used in one of the last ARC link
 » 18 months 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
•  » » 18 months ago, # ^ |   +10 I got the following test case using CF Stress.
•  » » » 18 months ago, # ^ |   +8 Thanks!
•  » » » 18 months ago, # ^ |   0 how to check this?? because i want to check test case 21950
•  » » » » 18 months 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.
 » 18 months ago, # |   0 Implementation ?
 » 18 months 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?
•  » » 18 months 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.
•  » » 18 months ago, # ^ |   +30 The easiest (but boring) way is to write a brute force.
 » 18 months 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.
•  » » 18 months 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.
 » 18 months ago, # |   0 Can anyone please help me on how to solve problem D, in Div2?
•  » » 18 months 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.
 » 18 months 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.
•  » » 18 months 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.
 » 18 months 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.
•  » » 18 months ago, # ^ |   0 The number of values from type I will always be zero right as there are no A's
•  » » » 18 months ago, # ^ |   0 No, there will be such chains, these are the indexes which are already disjoint that is they have no neighbouring A.
 » 18 months 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 **
•  » » 18 months ago, # ^ |   0 One of the simple failing test case is Ticket 8284
 » 18 months 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$.
 » 18 months 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?
•  » » 18 months 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)).
•  » » » 18 months 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.
 » 18 months 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.
•  » » 18 months ago, # ^ |   0 You mixed up mean and median. In this problem mean is the average of some values, not the middle element.
 » 18 months 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!
 » 18 months 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]
•  » » 18 months 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].
•  » » » 18 months ago, # ^ |   +3 got it thank you guys
 » 18 months 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
 » 17 months 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$?
•  » » 17 months 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."
•  » » » 17 months ago, # ^ |   0 @dario2994 I guess
•  » » » » 17 months 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).
•  » » » » » 17 months 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...
•  » » » » » » 17 months 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.
•  » » » » » » » 17 months ago, # ^ |   0 Thanks! I don't seem to see your changes though, and it's been a week...
•  » » » » » » » » 17 months ago, # ^ |   0 We are trying to propagate the changes without much success.