Привет Codeforces!
Мы, Supermagzzz, Stepavly, AdvancerMan, unreal.eugene, студенты ИТМО, желая внести свой вклад в развитие сообщества Codeforces, обратились к MikeMirzayanov с предложением помочь с тестированием новых раундов. Но MikeMirzayanov предложил нам свою помощь в разработке собственного раунда. Поэтому...
Мы рады пригласить вас на Codeforces Round #603 (Div. 2), который пройдет в Nov/29/2019 17:35 (Moscow time). Он будет рейтинговым для всех участников, чей рейтинг ниже 2100. Вам будет предложено шесть задач и два часа на их решение.
Задачи были придуманы и подготовлены Supermagzzz, Stepavly, AdvancerMan, unreal.eugene, MikeMirzayanov.
Особую благодарность выражаем:
- VArtem, budalnik, arsijo, Alexxx, MeowMr, Vinatorul, SpeedOfMagic, RDmitriyS, Rox, Mr.Hakimov за тестирование раунда и за полезные советы по задачам.
- MikeMirzayanov за замечательные системы Codeforces и Polygon, а также за координирование нашего раунда.
UPD: Разбалловка: 500 — 1250 — 1250 — 1750 — 2500 — 3000
Надеемся, вам понравятся задачи. Удачи и высокого рейтинга!
UPD1.5: Спасибо за участие! Поздравляем победителей!
Top 5 Div. 2:
Top 5 Div. 2 + unoffical:
UPD2: Разбор выложен!
Are there any subtasks?
No.
Please share the score distribution.
Why do you have negative contribution?
I am trying to get the feel and nature coders. Right now, I am not aware of it so this may be a reason. Hope for positive contribution soon :)
It will be shared about an hour before the contest . Does it make any difference though?
I hope tomorrow I will be able to reach 2100 :)
Maybe the dislikes for your comments are because your avatar...
Or because it's spam
Or maybe he just posts comments wich are not usefull at all and reading them is not a good way of spending time
Me too!
I am not able to reach 2100 because I have missed a +1 in my code..:(
This time no copy-pasted part ! ;)
hope to become specialist in this contest.
good luck for all
Score distribution?
here it is!
There is a bug. I see some yellow coders in the official standings!
Yes, my bad. I'll fix it after the contest.
How to solve A?Am not sure of my solution :(
Sort by magnitude. It is optimal to pair the smallest with the largest until the largest and the middle are equal (or as close as you can), then pair the smallest with largest once and smallest once until you run out of smallest.
Nice solution!Thought so too, but tried different approach....:( Thanks BTW!
got timeout using this :? Python3.6
You can't simulate the optimal solution directly, it's too slow (you could take up to hundreds of billions of steps across all $$$1000$$$ test cases). You need to find a way to calculate the steps mathematically.
I did not actually do the simulation directly — it's just a description of how to go about this optimally. To simulate the simulation, I found difference between highest and middle, and checked whether it is higher than lowest or not. If so, then answer = lowest + middle.
Otherwise, set lowest = lowest — diff and set highest to middle. Now remove lowest/2 from highest and mid, add answer = (lowest%2==0? lowest : lowest — 1) + min(mid, high)
Not a very good solution (some repeated code) but you can see 65992022 to get the idea
I found A very similar to this problem: https://mirror.codeforces.com/contest/1260/problem/B
Non-dp solution for F:
Firstly, we can achieve our goal by deleting all edges in the first or second tree, so suppose now that we leave at least one edge from both trees.
We can consider our goal as choosing vertices from both trees so that the vertices from a tree are connected and for each pair of corresponding leaves, at least one of them is chosen.
This sounds like a min cut problem.
Suppose we label each vertex with S or T. A vertex in the first (second) tree is labelled S (T) if and only if it is chosen.
How can we encode our conditions?
Firstly, the root of the first (second) tree must be labelled with S (T).
Next, if a node in the first (second) tree is labelled with S (T), then so is its parent.
Finally, for each pair of matching leaves, we cannot have the first one labelled with T and the second one labelled with S.
We want the minimum cut to denote the minimum number of vertices we can choose.
How the final flow graph looks like:
Vertices: Source, sink and the vertices of the 2 trees.
For each non-root vertex of the first tree, there is an edge from it to its parent with capacity INF.
For each vertex of the first tree, there is an edge from it to sink with capacity 1.
For each non-root vertex of the second tree, there is an edge from its parent to it with capacity INF.
For each vertex of the second tree, there is an edge from source to it with capacity 1.
For each of the $$$n$$$ pairs of leaves, there is an edge from the leaf of the second tree to the corresponding leaf of the first tree with capacity INF.
There is an edge from source to root of first tree with capacity INF.
There is an edge from root of second tree to sink with capacity INF.
Your solution is so overcomplicated, but still very cool.
Observation 1: if some vertex is not going to be used, it's whole subtree is not going to be used. So let's have each vertex as some segment on the leaf vertices and by deleting this segment we can delete every edge in this subtree and the edge to it's parent (if there is one). Observation 2: those segments must cover each leaf exactly once (otherwise it would not be correct nor optimal). So it dropped down to a task: given a + b segments with some cost c find a coverage of n leaves with maximum cost, which is a stupid dp.
Hi! That's a nice solution. I just tried your approach. But, I believe that the case of deleting all edges from one of the trees is also covered as a special case in the minimum cut algorithm. Instead of outputting $$$max(a-1, b-1, a+b-maxflow)$$$, I just outputted $$$(a+b-maxflow)$$$, and it got AC.
A-E all classical problems
You have solved similar problems like A-E ? If so , would you please give the links of some of those problems ?
They indeed looked familiar.
E.G. as far as I remember the solution of A was also needed to solve DeleteArrays from SRM770
The problems were great! Who can tell me how to solve C?
I found that if I just iterate for divisors till sqrt(A), then all quotients I get for higher values lie in a single continuous range.
success or timeout?
Success!
Thank you!
You could refer to this post.
i think i am right,but the answer is TLE.how to solve C?
Lol, your solution uses t both as the count for tests and n / i so it runs forever.
Imagine we iterate through k
n/k — n/(k+1) = n/(k(k+1))
this means that if k > sqrt(n) then at each step you will be decreasing less than 1
so, after that you will pass for all non negative integers
start diving from i=1 and keep increasing unless u don't get same value when doing floor(x/i) after that it's a continuous decrease like for x=1000 at i=37 u will get floor(1000/37)==27 which is repeat for i=36. This means after 27 all are included like 2, 25...2,1,0. but i still got timeout. ;? but i see rohit_goyal has more optimal solution
You can also start from 1 and do binary search every time that until what number n /j == i. and then move the pointer to that number .
Well, for fixed n f(k) = n/k is a monotonous function. Binary search is a solution in O(Ans*log(n)).
I'm sad I didn't see D solution is it graphs or something
I think it was related to Union — Find algorithm...
Yes ; one can connect strings who have a common character ( As these two strings are equivalent ) ; and finally answer is number of connected components !
It can be solved greedily as well.
Start with the string having the most number of distinct characters and simultaneously mark the characters you have gone through. If we come across a string in which all it's characters are already marked, we need not count that string in our final answer.
PS: The DSU Approach is great.
The greedy approach fails at test case 68. i tried it! when the strings of have same length have same number of unique elements and all are different it fails.
for example
abcd efgh fa
expected — 1 output — 2
Is pD really that easy ?? I tried to do it with a bitmask-things but I couldn't. Can somebody help?
For each letter find a word that contains it and build a graph by connecting every other word that contains it with that word. The answer is the number of connected components of that graph.
it's dsu. But only there are only 26 arrays, so I think bruteforce may be accepted too.
A node is a char
for each pair of letters x,y in a string add an edge x->y
The answer is the number of connected components
It is fairly simple dsu, just build groups by contained characters.
For every password you could build a set of letter. then if 2 letters are in 2 passwords — just join the sets. after count how many sets left
Wow I just realized that I totally misunderstood the Task. Rating goes down again!
You can use simple approach such as brute force :))) 65990114
Your solution gives wrong answer on test case 67, though its accepted. Quite strange
it didn't have test case 67, bro!!
It does have test case 67. Check my 2nd last submission, I just pasted your code and it gives WA kn test 67
Wow, this is my first time seeing something like that.
Is that a hack test case?
New test case after contest ??
Yes ; for each string ; you may store a bitmask corresponding to it ; and then the strings with common character could be joined ; and at last answer will be number of connected components !
A code which does bitmask + DSU : https://mirror.codeforces.com/contest/1263/submission/65980587
In F,
wires between nodes do not intersect.shouldn't it be bolded?Hmmm, my bad. I didn't see the condition
It is guaranteed that each grid is a tree, which has exactly n leaves and each leaf is connected with one device. Also, it is guaranteed, that for each tree exists a depth-first search from the node 1, that visits leaves in order of connection to devices.I don't understand why such a tight time limit was put in E. It cost me multiple TLEs when writing output using cout, however with printf it passed.
I had the same issue — little bit annoying lol
VERY annoying actually.
I used Java, and with Java lazy SegTree doesn't pass at all :(
you can solve it without lazy just normal segTree my submission (that was after contest because I forgot ind = max(ind,0) xD )
I too was getting TLE, but it was a coding error in my case though, I was calculating values again and again, instead of just referencing already stored values... :(
Jury has a simple linear solution with stacks in this problem.
Ah, that's cool, but imho segment tree with lazy propagation isn't really a bad solution to this problem.
How to use segment tree WITH lazy propagation in this problem? I came up with a solution only needed to modify a single position.
I think they update the prefix sum.
Its a little sad though when you correctly implement everything, but still get TLE because of using Java :(
I think the time limit should be 3 seconds, or N should have been less than 200,000.
After the contest I optimized a tiny bit and got it to pass. I changed all the longs to ints first (I'm not sure if this actually did anything meaningful). Most importantly, you're querying three times over the segment tree per change, which can be reduced to one (Query max and min at the same time because they're over the same range and manually store the prefix sum over the entire array). However I see that you fail on TC 4, which means that you might have to optimize your seg tree implementation.
Edit: Some other simple optimizations, I found .toCharArray() to be faster than charAt(i). Also when you build your segment tree you can initialize your tree as zeros to save some time
I think cout endl cause TLE. Pls read this https://mirror.codeforces.com/blog/entry/43780 for more information.
How to do first if there are n piles.
Its very similar:
min(sum of n-1 smallest piles, sum of all piles / 2 floor)
I think that if you want you could derive the condition considering finally piles are of the form : { 0 0 0 0 0 0 A 0 0 0 ...... 0} So you could apply constraint between A, sum of all piles and largest pile's value and find minimum A, and hence maximize the value of answer!
Is intended solution for E Segment Trees w/ Range Propagation and then leveraging min/max/sum?
My solution on that passed in 202ms so I guess yes.
Damn Java
Lol system tests even reduced that to 187ms
No, it wasn't intended to be seg-tree in any way, although many solutions passed... It can be solved with 2 stacks storing brackets, one from left and other right, with 2 arrays(although i used sets 66013420) to check the max and min on both sides
I used the same but got runtime eror, can you check my solution?
It's seems like STL stack overflow error, your stack couldn't allocate 5*10^5 size... although my STL vector could.
In Problem E.
How to update number of different color need to use if text is correct
I found that we can use the maximum prefix value(by assigning openings as 1 and closings at -1) that one can get as answer, because answer is longest opening sequence(it may have some complete brackets within) and any closing would just decrease the answer
I'm so confused where do I wrong on E. I was so close to an AK.
Anyone got the wrong answer on pretest 2 of A and then got correct?
Or any possible testcase where this could get wrong?
Thanks in advance :)
My solution — https://mirror.codeforces.com/contest/1263/submission/65990422 (I stresstyped every possible case because I was getting the wrong answer :( )
I believe yours fails on the input 3 4 5 since then it returns 5 whereas 6 is the answer.
strange round. D is just — "oh my, write DSU". E is just "oh my, write segtree with mass updates".
No DSU was needed in D. Create N+26 nodes (N nodes for each string, 26 nodes for each character). Connect node of string and character, if the string contains this character. Answer = number of connected components among nodes corresponding to strings.
I think ideas of CD are quite standard. E is just a boring version of this.
Вопрос к авторам: зачем в раунд добавили Е? Кажется, что это просто задача на реализацию, которая не может оставить положительных впечатлений.
Very easy div2 contest.
For probB ,My solution passed pretest 2 . But failed on test 2 , is'nt it amazing .
So, I tried to solve E using a Segment Tree with lazy propagation. I wrote the bracket series as a prefix sum, for example like [1,2,3,2,1,0,-1,0,1]. Then, to process 'L' and 'R' moves I just shifted an index variable. To process '(' and ')' updates I simply lazily updated all the numbers in the prefix after the index i. Then, to find if it was valid or not, I simply used Segment Tree range min and range max query.
In total, my algorithm was Nlog(N). And yet it TLED. Any reason why? (I used Java)
First, nlogn in segment tree. Second, Java.
Can you be more specific thx.
Segment tree has a rathar large factor constant. And so Java.
Here is a link to my code 65980577
TL 1 second, n = 10^6, you use java. there is no chance
Apparently the intended solution was linear, i was thinking about segmet tree too, but i guess we will have to wait for the editorial. https://mirror.codeforces.com/blog/entry/71803?#comment-561282 Some people were able to get nlogn with fast inputs too, it seems.
A is quite beautiful if you prove things by construction and the triangle inequaltiy.
How to solve B..?
For repeating pins, replace their first digit with the digit that is not present in other pins first digit. Since maximum value of n is 10, we can be sure that all digits will be distinct after the process.
I thought it like this : Say I iterate over the input values(as strings) and if I have more than 2 strings of current type, I can change it to a whole other string just by changing 1 character because if I just change a single character, I can get 40 strings or nearabout that number of strings, so I just find such a string by brute force, trying changing each character so 4*10 combinations are there, and changing string value to the one which is not present in my set of strings, and incrementing the count of moves by 1.Finally I print all the new strings(or old ones in case of unchanged....)!
Thanks, my algorithm was exactly what you said. I just realized that my implementation was wrong..TT
The problemset is nice although i performed badly this time :(
"L — move the cursor one character to the left (remains in place if it already points to the first character);"
"It is guaranteed that all characters in a string are valid commands."
Somehow I thought the second line meant that there can't be an input where you go left from the first position...... (and it doesn't seem to even be in the pretests?)
(Also trying to fail $$$O(n\log n)$$$ segtree solutions with $$$n \le 10^{6}$$$ and 1s TL is not really cool as many such implementations actually would pass. I think this has been said by many people in different contests, but either give up on failing these solutions or increase the constraints so that it would clearly fail all (or at least those without extremely heavy constant optimizations attempts) "bad solutions" (in this case it's hard to increase because of I/O size though, so maybe some input/output compression would work))
I think this might have been in pretest 5. Luckily, I had an assert that checked L was valid... But I agree this is confusingly worded
Welp my solution failed system tests because of that so I thought it might not be in the pretests.
I don't think it is in the pretests either, as I failed on the same thing.
I failed on pretest 5 due to my pointer going out of bounds i.e. -1, so it was in the pretests, although it didn't affected ur solution.
I didn't deal with this situation in my program,pretest passed,but system test failed.
MikeMirzayanov Did you just banned Ashishgup only because he wrote "A-E are classical".
He is not banned, he is temporarily in the read-only mode. I believe that the rules should be the same for everyone. And any discussion of problems during the contest is unacceptable. We cannot predict how this or that opinion about the problems will affect the participants. I am pleased to discuss the problems, but this can only be done after the end of the round.
Too much easy problem set!
Can anybody tell me if this solution is correct for problem E? My solution use segment tree without lazy propagation. For each node in the segment tree I know v[nod].left = number or '(' without a pair (basically open) , v[nod].right = same but for ')' and v[nod].depth = how many colors do I need. How to find v[nod].depth if we know every information for its children? v[nod].depth = max ( v[ 2*nod ].depth, v[ 2*nod+1 ].depth) maximum depth of its children + min ( v[2*nod].left, v[2*nod+1].right) this if for: '(' CONFIGURATION + CONFIGURATION '))' so in this case I increase the depth with 1 because I make new pairs. I had a bug in implementation so I couldn't submit it, but does anybody have the same approach?
Alternatively, You can consider point updates +1 for '(', -1 for ')' and 0 otherwise. Then maximum prefix sum is depth and minimum prefix sum should be 0 for correct sequence.
yeah, this is the approach with lazy propagation. Or, could it be solved without lazy?
You can maintain the maximum and minimum prefix for each segment node. Then you won't need lazy propagation.
Maybe I am the only one who solved B using mincost-maxflow.
maybe I am the only one who solved B using randomization?
I used srand(time(0)) ; in your code and got WA at first at test-8 , then on test-10. But without using srand(time(0)) , your code gets AC . Any idea why this is happening ?
I'm calling the police
Yeah, you used a bomb to kill a mosquito.
I thought of using Hopcraft Karp algo. but gave up even before I began to code XD
Was it bipartite matching implemented with flows? Cool! Here is my idea: start with the 10 pins; this is part A. Connect each pin with numbers that differ in one place or don't differ at all. You get up to 40 neighbors. This is part B. Now find a perfect matching between A and B. The numbers which pins are matched to are the answer.
My first submission to D got accepted but it doesn't pass
Answer should be 1 right? I saw both of your submissions giving 1 as output :3...
When I ran it in the Codeforces custom test it printed 2.
My first submission should be wrong because my find() function recursively calls find(cur) instead of find(par[cur]), and when I insert the numbers into set< int > cnt, I should insert find(par[cur]) instead of par[cur].
Seems that there's a problem in judge data... Some other solutions also got AC which was actually wrong.. sad :(
Good contest!
I think the problems were much easy and this should've been a div 3... anyways... thanks to the setters.
MikeMirzayanov Supermagzzz My solution for E passed the pre-tests, but after system testing gave TLE on test case 5 which was part of the pretests.65979337
Moreover changing language from c++17 to C++14 got accepted 65994359.
Can you look into it.
See, your solution is on the edge between OK and TL. It is just a random it fits in TL or not. Just try to improve your solution a bit. Also, it is a good practice to verify that your solution fits in TL with some gap on pretests.
As I see this problem can be solved even on Python, so I don't think the TL is too tight.
I Got AC in problem D, I think it shouldn't pass. Consider the following test case: 3 asd qwe aq
your solution outputs 2, but it should be 1! MikeMirzayanov can you please see this?
exactly!
Another similar submission is here: 65988894
I used a O(n) algorithm to solve Problem F.
It can be proved easily that when each of the electrical devices is covered by just one grid, the answer will be the best. And the problem guarantees that every nodes x in the grids will cover a range [l, r]. That means we can disconnect the electrical devices with the gird if we erase the edges connecting to the nodes in the subtree of x. We can get it by doing a dfs/bfs. Then the problem is transfromed to an easier problem: There are some ranges, each range has a value. we need use them to cover the range [1, n] and maximize the sum of these values. dp[i] means the maximum sum of value when the range [1, i] is be coverd. For dp[i], we just need to check the ranges beginning at i + 1 to transform it. So every range will be used just one time. It also solves in O(n).
F can be easily done in $$$O(n)$$$
https://paste.ubuntu.com/p/8SJHkS5w6d/
I'm very confused about range of $$$n$$$ in contest....
It is the first time I reach Purple, thanks to this interesting contest.
I can't understand why my submission for B got WA.
Study how your code performs when the input is 3 0000 0000 1000
Your code makes 2 moves, whereas the minimal moves required is 1.
Thank you.
The templet of segment tree used in Problem E. can be found at https://github.com/HeRaNO/OI-ICPC-Codes/blob/master/UESTC/2156.cpp
But someone else used that templet in E and our codes are almost the same. So I was blocked, but I promise that we didn't communicate with each other during the contest.
I wonder how to solve the misunderstanding.
The main parts of the codes are completely identical:
MikeMirzayanov, why has my 65968043 to 1263A - Sweet Problem been "Skipped"? It's the first time when i see this. By the way, I didn't cheat. At the round verdict was all pretests passed and I leave round with happy thought that I 'll become green. Now I am very disappointed.
Your earlier submission of A accepted so your later submission is skipped.
This is really unfair, king. I think we all must do everything possible of us to correct this blatant act of injustice. MikeMirzayanov, you really need to look into this horrible situation.
Instead of a thousand words:
MikeMirzayanov, maybe I could prove my innocent. Before send I program in ideone.com . In this site there is a page "Recent code". This is my code: https://ideone.com/L2fM6l . It's a public paste. On 23:22 I have found this code here (https://ideone.com/recent/19). So, all users that use ideone are at risk be unrated, don't they?
In the terms of agreement when you register, you are forbidden from sharing or publishing your code before the contest finished. Also I have no idea why you need to paste your code onto public paster. No matter intentionally or not, the fact that your code is somehow published makes your code skipped. This would be fair for everyone.
What is the answer for this input of problem D?
EDIT: How about this?
1
Test case for 1263D - Secret Passwords was weak.
This submission 65988894 gives output 2 for input 3 ab bc ca, but output should be 1.
yeah, I got accepted with the false solution(naive one), after the contest, you can check 66023526 which fails for a simple test case like this: 7 a b c d ab cd abcd
Here the correct answer is 1, but the program outputs 0.
So, I am done with the comments, would like to read the editorial now. Thanks!
in the rating changes the rating predictor rating is not same as the changed rating for this contest has codeforces changed their rating algorithm and forgot to update the predictor????
Oh... You are right. The predictor showed me +12 but I actually have -5 :(
i waited for the standings and they came out wrong :(
cf-predictor used ratings before last educational round so that's why rating changes are inaccurate.
CF Predictor is a 3rd party extension. CF has nothing to do with it.
read this mate https://mirror.codeforces.com/blog/entry/50411
thank you .
yes , i faced same issue.
I don't understand what hacking is. Does anyone explain it to me? And when I get hacked?
https://mirror.codeforces.com/blog/entry/6249
It means that there are some bugs hiding in your code. The bugs may be some easily mistakes such as OVERFLOW, FORGET TO CLEAR MEMORY. Your wrong code with these mistakes can pass pretest data, but have high probability FST. The hacker is helping you to improve your program.
This is the charm of Codeforces I think.
Thanks
Well at least I found out about how editors color the brackets in code today! XD
In my experience they mostly stop responding or crash horribly when you load a huge file of parentheses...
I guess it indicates brute force implementation in editors. :D
Can anyone please tell me how to hack a submission after the contest ? I am getting this message "You cannot hack the submission"
At least when it came out, "uphacking" was restricted to div1 users. Maybe that's still the case. (Source: https://mirror.codeforces.com/blog/entry/68204)
This was a very interesting contest !
There seems to be a problem with the C compiler for problem C. My solution 66003014 submitted in GNU C11 TLEd on test 4 but the exact same solution submitted in GNU C++17 66003340 passed comfortably MikeMirzayanov Supermagzzz
You have to choose the compiler yourself. Different compilers have different efficiencies (optimizations).
I'm pretty sure GNU C11 is the only compiler available for C. There is no reason why a SQRT(N) solution would timeout when compiled in C vs when compiled in C++ (both are compiling the SAME SOURCE code). My guess is that an incorrect TLE multiplier was applied(some sites apply multiplier for different languages so that implementation in slower languages like Java don't TLE)
printf is very slow in C11
Checks out! Replacing printf with putchar brought down the execution time from 2s to 46 ms. Thanks for pointing it out. Something to remember during future contests
WDYT about solving 1263F - Economic Difficulties with min-cost-max-flow? Let every edge have flow one and cost one. The sink is connected to the two root nodes, and the n devices have a single outgoing edge to a sink node; each with flow 1. The min-cost flow will then use as few edges as possible. MCMF can be solved in $$$O(E^2)$$$, which should be small enough since $$$E\approx 2000$$$.
If I'm right, then the whole of the problemset could be solved pretty easily with standard copy-pastable algorithms.
Between witch nodes are you running min-cost-max-flow ?
I connect a source to the two root nodes, and I connect all devices to a sink. All edges have capacity one.
If you pass $$$k \gt 1$$$ units of flow on some edge then these edge have cost $$$k$$$ not $$$1$$$, so I think that your solution are wrong, you have implemented it?
My solution is related to maximum independent set. Consider each tree as a part in a bipartite graph with the vertices are its edges. Now if two edges from different trees cannot be removed simultaneously, connect a edge between them in the bipartite graph. Answer is the maximum independent set of the bipartite graph.
when the editorial will be posted?
Is Problem A solvable with binary search? If yes, can anyone explain a bit :)
Your text to link here...
I can't find the tutorial. I saw someone solved problem A with the following idea. sum <- r+g+b if the smallest two of r,g,b is smaller than the largest one ans = the sum of the smallest two else ans= (r+g+b)/2
Can anyone prove the correctness of it mathematically?
Assume that the values are sorted $$$a \leq b \leq c$$$
If $$$a + b \lt c$$$, then the optimal strategy is to take $$$a$$$ with $$$c$$$ until $$$a$$$ is gone, then take $$$b$$$ with $$$c$$$ until $$$b$$$ is gone. It is impossible to access the rest of the candies in $$$c$$$. Total number of moves = $$$a + b$$$.
Otherwise, the optimal strategy is to take $$$a$$$ with $$$c$$$ until $$$c = b$$$, at which point $$$a := a - (c - b)$$$, then take $$$b$$$ with $$$c$$$ until $$$a = b = c$$$. Then, there are three sub-scenarios:
$$$\geq 2$$$, in which case you can take $$$ab$$$, $$$bc$$$, $$$ac$$$ and decrease all of them by two, then repeat
$$$= 1$$$, in which case you just take any two and leave a single piece,
$$$= 0$$$, in which case you obviously stop
Since the strategy for this scenario always leaves $$$0$$$ or $$$1$$$ candies, the number of steps is $$$\lfloor \dfrac {a + b + c} {2} \rfloor$$$.
I'm pretty new to Codeforces and competitive programming in general. Where do I find the editorials to the problems?
Editorial will be published, you will then see a seperate link for tutorials.
When will Editorials be updated ?
Why MCMF is wrong for F ? see some MCMF solution with same wrong answer on test 5. code
I figured it out .I miss understood MCMF.
Hi, can you share why is it incorrect?
the cost of flow is flow multiply the the cost of this pipe .if a pipe with flow more than one the answer is not equal.
I solved problem E in O(n) by six stacks.
As we can see, for a regular bracket sequence, we can calculate depth of it by simply calculating the max prefix sum of bracket sequence by assume '(' for -1 and ')' for 1,else for 0.
e.g
"((0)())" can convert to 1 1 0 -1 1 -1 -1,and the prefix of it is 1 2 0 1 2 1 0,which the max value is 2 for the answer.
However,we have to deal with the irregular bracket squence like ")(",because it should be output -1(for irregular) instead of 0,this can be solved by calculating the min value of ths prefix sum array.If it is a negative number, it must be a irregular sequence.
Now we just need to deal with the problem by what we said before.
We maintain two stacks for prefix sum,stack A for restoring from begin to current cursor,stack B for current cursor's next position to the end of the prefix array.We can see the each operation will only happen in the curosr's postion,so if the cursor move to the left,we just need to pop the top value of stack B to stack A,moving to right is same.
e.g
"((0) ())", space for separating. For stack A,it is [1,2,0,1]. For stack B, it is [1,2,1]**(looking from right to left,it is '))(')**.
In the same way,we maintain two stacks for max prefix sum and two stacks for min prefix sum.
Thus we can calculate the answer by these stacks just check the top value of prefix sum stack A and prefix sum stack B are the same and sure two min stacks's top value is >=0,if all the condition is true,the answer is the max of two max prefix stacks
The code is here 66020705
Sorry for my poor English >_<
This contest is so great!!!
For me, A is still harder than B,C and D... It required more time than any other task for me... What's the idea behind solving it in one line?
a = [r,g,b] a.sort(reverse = True)
ans = 0 if(a[0]>=a[1]+a[2]): ans = a[1]+a[2] else: ans = a[0] + (a[1]+a[2]-a[0])//2if the maximum of r,g,b is greater than the sum of the remaining two terms than the answer is sum of those two terms.
else the answer will be maximum term + floor((extra sum of next max two terms)/2)
Could you help me find a mistake in my code of Problem B... https://mirror.codeforces.com/contest/1263/submission/66032322
Your code doesn't properly maintain the order of the PINs given in the input. It is appending the changed ones to the end of the list.
How to solve problem E using lazy segment tree? :)
lazily
The problem with problem D is still not fixed? There are still WA solutions out there having AC verdict. :/
Verdict won't change as old submissions won't be rejudged even if some of them are hacked later. But new submissions will face stronger tests so WA solutions will probably not get AC now. See this blog
So, the contestants who submitted wrong solutions and still got AC, will still get the points?
Thanks for the contest!