| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 165 |
| 2 | maomao90 | 163 |
| 2 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 160 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | nor | 153 |
| 9 | Dominater069 | 153 |
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.
Разбор задач Codeforces Round 794 (Div. 1)
Разбор задач Codeforces Round 794 (Div. 2)
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).
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
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.
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.
precision error) i've change your code a little and it passed tests 158518313
It says "Python supported has been temporarily disabled..." for Div2 A
I cannot find the test case responsible for my WA.https://codeforces.net/contest/1685/submission/158616772 is the link to my submission.
Here's a simple failing testcase: Ticket 8222
Thank you. This was helpful!
Very good problems! I like this types problems!
But my friends who wrote contest dont think so
Oh yeah, Mr.Bebra, I totally agree with you! Problems were very good!
I don't like this type of problem. They are too ad-hoc. Algorithmic problems are better.
what does it means, ad-hoc? I wonder!
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?)
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.
Silly in retrospect, but I also made the same mistake.
the same as me
.
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.
who tf asked?
If every comment was something somebody asked for, codeforces would be a silent place, my silly friend.
Exactly!
If you can't say something good, don't speak at all. -Eminem
i asked
I didn't like the problem names. They were boring.
you are boring
How many constructives?
"Yes"
How did you write the checker in 1685E - The Ultimate LIS Problem?
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.
For 1686A - Everything Everywhere All But One, suppose the number to be excluded is at index $$$r$$$, we require:
Therefore, the required condition becomes:
Which is the same as asking the question
Nothing new here i suppose, but I found this easier to code than what's in the editorial.
Complete code: 158477863
This is how I solved it and I think this approach is much more elegant!
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.
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.
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.
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.
Why I couldn't see editorial in div2's Contest materials? plz fix it :)
upd：now I can see it, thanks for fixing it!
Best contest I've ever wrote. Really nice problems!
I hate linguistics now.
same
same
same
For some reason, understanding the explanations in this editorial itself seems difficult, for me :(
Hoping this helps, Video Solution for D.
Really wondering how the top 100 come up with
Key observation: It's always possible to get a balanced sequence in at most 2 operations.in contests in a couple of minutes...
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...
What well-known problem?
Perhaps I find it. Is it the cyclic shift in editorial of E?
Yes, the same idea was used in one of the last ARC link
"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
I got the following test case using CF Stress.
Thanks!
how to check this?? because i want to check test case 21950
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.
Implementation ?
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?
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.
The easiest (but boring) way is to write a brute force.
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.
Two points I would like to highlight:
You could use data type
intinstead ofdouble. First check if the remainder of the division is NOT 0. In that case, the answer isNO. 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.
Can anyone please help me on how to solve problem D, in Div2?
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.
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 imaginea=1,b=0,c=1,d=1, and a stringAABBABBBB.a + c + d = 3, it passes the initial check. But we see we don't have enoughB's.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.
My solution for problem D(Linguistics) and an attempt to explain it.
There 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.
158512740
This is my first time explaining a solution in writing on Codeforces. Suggestions are welcome and please point out the mistakes.
The number of values from type I will always be zero right as there are no A's
No, there will be such chains, these are the indexes which are already disjoint that is they have no neighbouring A.
**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 **
One of the simple failing test case is Ticket 8284
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$$$.
Can anyone tell me that in the proof part of div2D,what's the meaning of "+" and "$$$\sum$$$" in
,are they equivalent to $$$\cup$$$ here?
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)).
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.
Div2, Problem A
https://codeforces.net/contest/1686/submission/158501965
I 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.
You mixed up mean and median. In this problem mean is the average of some values, not the middle element.
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!
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]
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 thata1=[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].got it thank you guys
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
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$$$?
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."
@dario2994 I guess
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).
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...
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.
Thanks! I don't seem to see your changes though, and it's been a week...
We are trying to propagate the changes without much success.