By 300iq, 3 years ago, translation,

Hi!

August 17, Aug/17/2018 17:35 (Moscow time), there will be a rated Codeforces round #504. Some of the problems will be from VK Cup 2018 finals, and awoo and vovuh have prepared other tasks for the full round.

The problems of this round are proposed, prepared and tested by: MikeMirzayanov, awoo, vovuh, Errichto, Lewin, Endagorion, Um_nik, YakutovDmitriy, Nebuchadnezzar, izban, Belonogov, scanhex, 300iq, qoo2p5, Livace.

There will be prizes from VK social network in this round as well! The participants who took the first 30 places of this round and the round #505, also partially based on the tasks of VK Cup 2018 Finals, will get GP30 points.

Participants are sorted by sum of points for both rounds (if the participant did not participate in one of the rounds, the points scored for it are assumed to be equal to zero), with the maximum time for both rounds from the beginning of the round to the last submission that passed the pretests as tie-break.

The top 10 participants will receive a plush Persik!

There is no country nor language restriction, everyone can win a prize. One don't have to have participated in VK Cup to receive the prize. Exact selection algorithm will be announced before the start of the round.

Good luck!

• +231

 » 3 years ago, # |   +42 maximum time for both rounds from the beginning of the round to the last submission that passed the pretests as tie-break What if the said submission doesn't pass the system test? If it would be counted, it may cost you the price compared to the case where you don't make that submission.
•  » » 3 years ago, # ^ |   -38 http://codeforces.com/blog/entry/61285 Pls see this...getting some issue in contest 504 Question D
•  » » 3 years ago, # ^ |   0 From what I see and understand, even contest 505 will be combiner round right?
•  » » » 3 years ago, # ^ |   0 Yes
 » 3 years ago, # |   +23 Finally, 3 consecutive rated rounds!!!
 » 3 years ago, # |   +90 Gateway Timeout Round
 » 3 years ago, # |   +1 So basically combined contest with prizes. Nice
 » 3 years ago, # |   +91 How many tasks will there be?
 » 3 years ago, # | ← Rev. 4 →   -67 Participate in the CF round with my GIRLFRIEND-Coding( It is impossible for me to have a girlfriend.....:( )!
 » 3 years ago, # | ← Rev. 2 →   0 will it be 20% div2 + 80% div1??thriller one ....
 » 3 years ago, # |   +81 You have to compete in all rounds. Not one, because you are a skillful contestant and you eat a garron of the big flute. You are in a state of temporal madness. You compete in all rounds, you solve all the problems, you hack all contestants in rooms, do I explain myself? You are inhackable brother. In 10 contests you are red.
•  » » 3 years ago, # ^ |   +24
•  » » » 3 years ago, # ^ |   +13 Best video ever!
 » 3 years ago, # |   +21 Hope CF wont fall again in the middle of the contest)
•  » » 3 years ago, # ^ |   0 Hope so!
 » 3 years ago, # |   -64 Hope the pretest will be stronger. I got a failed system test last time.
•  » » 3 years ago, # ^ |   -47 +1
 » 3 years ago, # | ← Rev. 4 →   +22 I pray for the codeforces hardware.
»
3 years ago, # |
-36

# But Is It Contributed?

• »
»
3 years ago, # ^ |
-19

# Are You Contributed?

 » 3 years ago, # |   0 Shall we need to use different languages to solve different problems?
•  » » 3 years ago, # ^ |   +17 You can if you want. :)
 » 3 years ago, # |   +14 Are the questions in English or Russian? Thanks for the reply.
•  » » 3 years ago, # ^ |   0 There will be both languages
 » 3 years ago, # |   0 perfect weekend, three consecutive rounds.
 » 3 years ago, # | ← Rev. 2 →   +7 Wish it won't be a Gateway Timeout Round. Good Luck & High Rating!
 » 3 years ago, # |   +40 How many tasks will be?
 » 3 years ago, # |   0 I have a strange felling I will do great today :D
•  » » 3 years ago, # ^ | ← Rev. 2 →   +9 We hope so ! Good Luck !
 » 3 years ago, # |   +67 Scoring?
 » 3 years ago, # |   0 Let's start, good luck to everone and high rating. :D
 » 3 years ago, # |   -87 Hackforces again.... Please, the huge difficulty increases are resulting in hackforces, try and prevent that, too easy A B C D then a E-bomb
•  » » 3 years ago, # ^ |   +1 How to solve D?
•  » » » 3 years ago, # ^ |   +8 The key observation was that you cannot have an interval of large numbers split by an interval of smaller numbers, i.e, something of the form "...8778..." is not possible. You can use a segment tree to check whether this is violated and then also check whether the largest value is present (as no other value can mask it) and take care of the zeroes (by extending the values from either side).
•  » » » » 3 years ago, # ^ |   +1 Oh damn! I did a similar thing. Perhaps my implementation has a mistake :(Thanks for the response
•  » » » » 3 years ago, # ^ |   0 Exactly, but it is not necessary the segment tree:)
•  » » » » » 3 years ago, # ^ |   +3 sure! there is no need to use segment tree. it can be solved with a simple brute force
•  » » » » 3 years ago, # ^ |   0 I'm trying with your approach. But I'm getting TLE on TC 9. Can you please help me out?? MySol
•  » » » » » 3 years ago, # ^ |   0 What exactly are you doing? The complexity should be
•  » » » » » » 3 years ago, # ^ |   +1 The complexity should be O(N + Q)
•  » » » » » » » 3 years ago, # ^ |   0 With a segment tree the complexity is if I'm not mistaken.
•  » » » » » » » » 3 years ago, # ^ |   0 Don't use a segment tree then
•  » » » » » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 Haha...Well it fits within the Time Limit so we can use it... And if you'll notice, the OP asked what the issue was with his code...and he is using a segment tree...
•  » » » » » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 Segment tree is more complicated to code than O(N + Q)
•  » » » » » » » » » 3 years ago, # ^ |   0 Maybe so...but that's not the issue here... I was simply conveying the complexity of the OP's code.
•  » » » » 3 years ago, # ^ |   +1 Maybe we don't need segment trees. All we need is a monotonous stack.
•  » » » » » 3 years ago, # ^ |   0 You can refer to my code for more details.
•  » » » » » 3 years ago, # ^ |   +4 Exactly a stack! I don't code it but I thought in it.
•  » » » » » » 3 years ago, # ^ |   +4 You can also see the solution of elnomada1996 :)
•  » » 3 years ago, # ^ |   +97 Numbers of ACs to E is basically one third of ACs to D. I wouldn't call that big jump in difficulty.
•  » » 3 years ago, # ^ |   +116 I don't think E was very hard for a div1C difficulty problem.It even had 2 times higher query limit than it needed.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +8 Interesting...i did get AC but my approach uses almost all the queries in worst case(no wonder am just blue)...How do you do that in half the query limit?Edit : Now when i think about it, i realized that yeah...half of my queries are actually utter useless! lol...
 » 3 years ago, # |   0 Hacking process or the compilers have the big problem with RE. I wrote two tests on which the programs had had to get RE, but they'd got OK. That's really strange... :(
•  » » 3 years ago, # ^ |   0 Compilers used in local machines and Codeforces servers might not be the same. So, next time, perhaps you should consider testing something through "Custom invocation" first.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +18 In C++ programming mistakes won't necessarily behave like you expect them to. Entering undefined behavior means anything can happen, the program may crash, print an incorrect answer or even appear to "work".
 » 3 years ago, # |   0 i tried this hack attempt to a solution that gives "no" while it should be "yes" to problem A2 3a*asdwhy it failed ?
•  » » 3 years ago, # ^ |   0 Which one failed? The hack, or the generator/validator/checker?If it was the hack, show the submission you intended to hack, so we can have a brief overview.
•  » » » 3 years ago, # ^ |   0 my hack failed I can't open the submission now but the username is ATS
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   0 You should see more about the substr function here.As it said, exception is thrown only when pos is greater than the string' size, so it'd be not the case.Furthermore, the "inner" condition (S.substr(p + 1, N - 1 - p) == T.substr(M - (N - 1 - p), N - 1 - p)) was correct: two strings being compared were both empty strings (you can check the code yourself, or maybe run it through Custom invocation).P/s: ATS' solution for reference: Solution 41688303
 » 3 years ago, # | ← Rev. 2 →   +8 Please say F can be done with HLD with range updates and point query... If so, any cute way to get rid of HLD?Also E needs just 2*n-2 queries right??
•  » » 3 years ago, # ^ |   +29 My solution for E also only need 2n - 2 query. The 4n query limit is probably to distract the contestant.
•  » » » 3 years ago, # ^ |   0 How to do it?I saw 4*n and started thinking that I have to break the square into 4 squares and then do something?
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +32 If the problem has no condition that two cells in query must have mahhatan distance at least n - 1, from cell (x, y) one can try to go down and ask if there is a path from there to (n, n) (make a query with (x + 1, y) and (n, n)). If yes, go to cell (x + 1, y), otherwise go to cell (x, y + 1).With the distance condition, split the process into two part: find a way to go from (1, 1) to some cell (x1, y1) in the sub-diagonal of the matrix, and find a way to go from that cell to (n, n). To do the later one, find a path from (n, n) to some cell (x2, y2) by asking the query with cell (1, 1), and then reverse the path.If one prioritize going down in the first part, and prioritize going left in the second part, it can be proved that (x1, y1) will coincide with (x2, y2), thus the answer is found.
•  » » » » » 3 years ago, # ^ |   +6 can you give a proof or an intuition as to why they would coincide
•  » » » » » » 3 years ago, # ^ |   +19 I think the best intuition for this one is: if you go from (1, 1) to (n, n) prioritize going down, and go from (n, n) to (1, 1) prioritize going left, these two path are the same. Otherwise, if the second path take some route below the first one, since the first one prioritize going down, it would have taken that route as well.
•  » » » » » » 3 years ago, # ^ |   +6 Think of it as lexicographicaly smallest path, where 'D' comes before 'R'. Trying to greedily put as many 'D'-s as possible at the begining is the same as trying to put as many 'R'-s at the end as possible(or 'L' if you reverse the direction).
•  » » » 3 years ago, # ^ |   0 With 4n you can be less efficient when finding the next cell to go to though (like trying both right and down although trying only one of them is enough). But yeah, this is probably to make the solution more obscure. xD
•  » » 3 years ago, # ^ |   0 Yeah, my solution works in 2*n — 2 queries too
•  » » » 3 years ago, # ^ |   0 Technically, each query gives you a single instruction. So you don't need to make the last query -- 2n - 3 suffices.
•  » » 3 years ago, # ^ |   +6 I used simple set for F and I would probably get TLE. I used 2*n-2 queries for E too.
•  » » » 3 years ago, # ^ | ← Rev. 3 →   +16 Actually set passes, but it's pretty tight (~2.7s / 3s): 41729054 41726211This is probably the same way you did it, but here's a quick explanation anyways: you store in a set pairs {cost of edge, index of edge} for all edges, such that exactly one of its endpoints is in the subtree you're currently handling. Then the maximum value you can put for the edge going up from the subtree is the minimum value for any such edge. To maintain this, keep the aforementioned set, and merge them using the standard smaller-into-larger strategy, except that if you would insert a pair that already exists, delete it instead (both of that edge's endpoints are in the current subtree).kllp told me this strategy after the contest. (fun story: During the contest he got memory limit exceeded because his arrays were of size 5e6, not 5e5. When he fixed that he got AC :Dd)
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   0 can you please explain the logic behind this part only "such that exactly one of its endpoints is in the subtree you're currently handling"?
•  » » 3 years ago, # ^ | ← Rev. 3 →   +13 In F, one can use path compression. 41719592
•  » » 3 years ago, # ^ |   +4 i didn't use hld but you can i guess, i changed updates to — minimize edges between a node x and an ancestor y of x with value val. I kept priority queue for each node, then added smaller queue to bigger one in dfs when traversing the tree. So i found the value of each edge offline.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +13 I think I have a cute way to get rid of HLD!We have some data of the type "All the edges in the path from u to v have to be at most x", and we want to find the upper bound for each edge. We can assume u is always an ancestor of v.Build array bound[MAXN][LOG(MAXN)], which means the edges in the path from v and it's 2b-th parent must be at least bound[v][b]. And also we define par[v][b] as 2b-th parent of v. Then we can easily decompose paths to blocks that exist in bound array. And after all, we do the following: for(int b = B - 1; b >= 1; b--) for(int i = 0; i < n; i++) { int x = bound[i][b]; bound[i][b - 1] = min(bound[i][b - 1], x); bound[par[i][b - 1]][b - 1] = min(x, bound[par[i][b - 1]][b - 1]); } and bound[v][0] is the upper bound for the edge between v and it's parent.
•  » » 3 years ago, # ^ |   +8 A way to get rid of HLD is to use union-find set.Consider this process: for each i, mark all edges in the path between fai and fbi with value fwi on MST, if an edge has been marked, then skip. Because each edge will be marked at most once, we can optimize the complexity of finding next edge which hasn't been marked.Use a union-find set to maintain all nodes, at the beginning all sets contain only one node. If we mark an edge (pi, i) (pi is the father of i on MST), merge i's set into pi's set. If we do this, at any time the representative element of i's set is a node j, while edge (pj, j) is the first edge from i to the root which hasn't been marked.While marking all edges in the path between fai and fbi, let u = fai, v = fbi. Each step, let u, v be the representative element of its set, select the deeper node, find the first edge e using union-find set, and marked e with value fwi, until u = v.
 » 3 years ago, # |   0 Does anyone have any idea about how the grid was for pretest 6 in problem E?
•  » » 3 years ago, # ^ |   0 I'm not sure because I didn't fail on that test but might it just be an empty grid? (of any size, probably >2) There's an edge case where if you don't change your preferred move on the second half then the paths might not line up.
 » 3 years ago, # | ← Rev. 3 →   -97 Ohhh, it is not hackforces, it is F***forces
•  » » 3 years ago, # ^ | ← Rev. 2 →   -71 Yeah, Yeah, Yeah downvotes are proof for F***forces
 » 3 years ago, # |   +2 How to solve E?
 » 3 years ago, # |   -7 Problem D :For input : 3 5 0 0 0Output : YES 1 1 1why is this wrong ?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +26 The last query was with i = q, so q has to appear at least in one position.
•  » » 3 years ago, # ^ |   +1 There has to be at least one 5. 5 cannot be overwritten
•  » » 3 years ago, # ^ |   +1 because last query will affect atleast 1 value. there would be atleast one 5 in the final answer.
•  » » 3 years ago, # ^ |   +1 every query has to be applied on atleast one element of the array. So if the output is 1 1 1 that means you didnt apply 2 3 4 5 queries
•  » » 3 years ago, # ^ |   +1 because q = 5 should be in the final array
 » 3 years ago, # |   +7 Should we (somehow, probably with some dp) calculate cut instead of flow (in G)?
•  » » 3 years ago, # ^ | ← Rev. 2 →   -52 Write Blogewoosh #3 about it
•  » » 3 years ago, # ^ |   0 Or maybe Dilworth things?
•  » » » 3 years ago, # ^ |   -43 What is Dilworth?
•  » » 3 years ago, # ^ |   +23 I replace your dinic algorithm with HLPP. It's more than 100 times faster now.And it can finish in about 8 seconds on my own laptop. You dinic code is still running now. However, it can't finish in 10 seconds on the custom test.Maybe we can squeeze it into the time limit by a faster flow algorithm/implementation or reducing the number of edges.
•  » » » 3 years ago, # ^ |   +3 Sorry, what is HLPP? A quick google search turned up nothing.
•  » » » » 3 years ago, # ^ |   +24 Highest label preflow push algorithm / Highest label push relabel algorithm.
 » 3 years ago, # |   +74 Whew. Boys and girls, my second CF round done on mobile internet. I mean dial-up connection through Ubuntu Network Manager, with help in detecting the phone as a modem from ppp utilities; transfer speed a few kilobytes per second. From a train to boot. I didn't know the meaning of stress and overload with tasks to check until now — the connection can randomly drop, the only moderately fast way of competing is through lynx so I have to switch between terminals, all my browser tabs are terminal tabs, if lynx hangs then I have to log in again, I have to send files from the same directory where I open lynx.... I'm surprised I was able to write this comment at all, JS doesn't load very fast (if at all) and images are even worse.The round on Sunday will be the same, except not from a train, but with far worse connection. I'm masochistically looking forward to it.
 » 3 years ago, # |   -92 From now, I will read first all tasks and see is something Interactive — IF (interactive) skipRound();
•  » » 3 years ago, # ^ |   +56 This sounds ridiculous. What this problem has done to you so that it activated so much hatred in you? It was cute and simple.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   -25 No, I do not hate this concrete task. Round was quite nice. I do not like Interactive tasks in global — I think they are much more guessing and lucky than all other types of problems. It is my opinion and I believe I won't change it soon.
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +38 "I do not like Interactive tasks in global — I think they are much more guessing and lucky than all other types of problems." — that part about guessing/luckiness is just BS. I guess this is just your unreasonable prejudice probably resulting from some fails on interactive tasks.
•  » » » » » 3 years ago, # ^ |   -8 I won't say it is not my prejudice — but still I do not like them :P
•  » » » » » » 3 years ago, # ^ |   +13 I dont like output only problems too, cause I never actually solved one :).
•  » » » » 3 years ago, # ^ | ← Rev. 4 →   +26 "I do not like Interactive tasks in global — I think they are much more guessing and lucky than all other types of problems."You haven't encountered any output-only problem in your life, right?I think that guessing is actually an important part in solving problem. That's how you gain the idea and observation that are required to solve the problems. Experience is a kind of shortcut that allow you to make the observation faster.
•  » » 3 years ago, # ^ |   +10 Then why did you create interactive problem, if you hate them. https://www.codechef.com/AUG18A/problems/INMAT
•  » » » 3 years ago, # ^ |   0 I knew someone will ask it :DBut I must disappointed you, both tasks used on the contests are not my tasks. They were on National Selection for IOI. As I am part of committee and was participating in preparation of the tasks I could take testcases and official solutions(I added some other testcases for this one too).Normally people from Codechef knew that is not initially mine, we knew that may be some problems if anyone had seen it before, but I think everything was great during contest and you all got 2 new tasks.Today Cook-off will have all my tasks and they are new for everyone I hope :)
 » 3 years ago, # |   -44 Really hard to understand prob C. "Subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements." What is elements,, order,, English is too hard....
•  » » 3 years ago, # ^ |   0 Subsequence is a string that can be obtained after deleting some symbols from original string
 » 3 years ago, # |   +16 G looks like problem C from the last World Finals. I guess it has a similar solution with merging sets or treaps.
 » 3 years ago, # | ← Rev. 2 →   +15 F*** your pretests
 » 3 years ago, # |   +39 is this the hardest div2A in the history of codeforces
•  » » 3 years ago, # ^ |   0 No, 592A - PawnChess seems to be harder :)
•  » » 3 years ago, # ^ |   +48 You can check 200A - Cinema.
•  » » 3 years ago, # ^ |   -26 No , it was rather easy but some noobs made stupid mistakes
 » 3 years ago, # |   0 any idea about pretest 7 for problem D ?
•  » » 3 years ago, # ^ |   0 Might be because of including 0's in range minimum.Try this: 8 4 0 1 0 2 4 0 2 3possible answer: YES 1 1 1 2 4 4 2 3
•  » » 3 years ago, # ^ |   0 I had problems with test 7 too, but this test helped me.3 30 1 3YES1 1 3 or 2 1 3
•  » » » 3 years ago, # ^ |   0 any idea about 10th pretest case. I failed on it. Could not figure out my mistake :/
 » 3 years ago, # |   +15 Weak pretests = Never ending system testing !!
 » 3 years ago, # |   -8 Can anyone see something wrong in here?http://codeforces.com/contest/1023/submission/41722815I noticed that the second lower_bound should be changed to upper_bound, but didnt have the time to submit it.....Is it AC if I change to upper bound?
 » 3 years ago, # | ← Rev. 5 →   -8 In E, as long as the distance from my current cell to the destination is at least n, then using one query I can know to which cell I should move such that it is allowed and it can reach the destination.But when the distance from the current cell to the destination is n-1 or less (so the distance from the next cell to the destination is n-2 or less), what strategy should be followed then?EDIT: Never mind. The answer to my question (which doesn't have to query such distances less than n-1) is here http://codeforces.com/blog/entry/61254?#comment-451801
 » 3 years ago, # |   -8 How to solve C?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +6 For each '(' find corresponding ')'. Delete these pairs from the string while its length is greater than k
•  » » » 3 years ago, # ^ |   +3 Damn that's a simple solution. Thanks!
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 What does it mean "corresponding"? I was found pairs "()" on the beginning and on the end of string. If I can't find, I delete '(' from the beginning and ')' from the end. Can I claim, that I find corresponding chars? Or maybe, I must find nearest ')'? MySolSorry for poor english.
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +10 Make an empty stack. For each character in string, if it is '(' then put it on the stack, else remove the top '(' from the stack, and this ')' becomes corresponding to removed '('.
 » 3 years ago, # |   +15 How to solve A?
•  » » 3 years ago, # ^ |   -6 your question is soo tough please wait Editorial like me!
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 t[:-len(v)].startswith(u) and t[len(u):].endswith(v)After a red bold number showed, I found this — t[:-0].
•  » » 3 years ago, # ^ |   +8 Maybe Python will help.I tried Python's unfamiliar regular expression, found it didn't work, then waste a lot of time using C++'s strtok...All I actually need is Python's split、startswith、endswith...
•  » » » 3 years ago, # ^ |   -18 It was sarcasm dude
•  » » 3 years ago, # ^ | ← Rev. 2 →   -8 I have a solution using STL string functions xD
 » 3 years ago, # |   +16
•  » » 3 years ago, # ^ |   -11 But you didn't lock any problems...
 » 3 years ago, # |   -65 Hey noobs , how can you fail A? i can't understand you, noobs. it is rather easy task but you failed it. noobs.
•  » » 3 years ago, # ^ |   0 really ez, just don't take the case s.size() > t.size() and s dosen't have the character *, but take the case s.size() — 1 > t.size() ans s does have the character *, REALLY EASY
•  » » » 3 years ago, # ^ | ← Rev. 2 →   -28 noobs. how is it possible to forgot to check these easy cases??
•  » » » » 3 years ago, # ^ |   +9 PLEASE LEARN ENGLISH stfu
•  » » 3 years ago, # ^ |   0 dude, some cases where so tricky! even fateice's A got WA, also pretests didn't seem to be so strong
 » 3 years ago, # |   +10 Can someone please explain how to solve D ?
•  » » 3 years ago, # ^ | ← Rev. 4 →   +23 if there are three indices i < j < k such that ai = ak and ai > aj and aj > 0 then the answer is NO, it can be checked with segment tree. if there is no q in array and no 0 in array, then the answer is NO. otherwise the answer is YES. if there is no q in array and there is any zero in array, make it equal to q. for each zero , make it equal to any neighbour nonzero element.
•  » » » 3 years ago, # ^ | ← Rev. 3 →   -12 That is too complicated. Let me introduce an easy one.Iterate over a skipping 0's. There should be a increasing prefix, a sequence S full of maximum value and a decreasing suffix. Or a is invalid.Consider a but not to skip 0's. If maximum value is less than q, try to find a 0 surrounded by the elements in S and replace it with q. Or a is invalid. (Because q must appear in a according to the description.)Replace 0's with previous element in a iteratively (or replace it with 1 if there is no previous element).
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   +24 5 31 2 1 3 1 is invalid?
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   +5 Holy EFF! You should be rewarded with 100 points.
•  » » » » » 3 years ago, # ^ |   +7 Oh here goes my rating
•  » » » 3 years ago, # ^ |   0 I thought the exact same solution but couldn't implement. Instead of using Segment Tree I was stuck on using Java TreeSet. Can you explain how segment tree would help here?
•  » » » » 3 years ago, # ^ |   +4 for each i from 1 to q if there is any i in array, I know when its first and last occurence in array. If the minimal element (except for zeroes) in range between its first and last occurence is less than i, then the answer is NO. Minimal element on range can be found using segment tree.
•  » » » 3 years ago, # ^ |   0 Thank you !!
•  » » » 3 years ago, # ^ |   0 For the first check, I didn't use segment tree, I used an array of vectors vector v[N] that save in each vector i the indeces where the number i appears in the given array, and as it is known, each vector will be sorted automatically. Now, for each i where 1 <= i < n I will check for each index j where 0 <= j < v[i].size() if v[nxt][0] <= v[i][j] <= v[nxt][lst] where nxt is the next number after i that appear at least once in the given array, and lst is the last index in the vector of nxt.And if that condition is true then the answer is NO.
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   +5 your solution says "YES" for test4 32 3 1 3Next time when you want to share your solution, please check if it is not wrong.
•  » » » » » 3 years ago, # ^ |   0 I commented after I had got AC, but you are right that this test hacks my solution, so it is wrong. Sorry about that. MikeMirzayanov, please, check this situation.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Applied the same, didn't know where I went wrong.EDIT: Apparently I built segment tree without handling the case when the length of range is 1 and element is 0. It worked after that :(
•  » » » 3 years ago, # ^ |   0 Why is it optimal to always set 0 to q?For example what if you have: (a < q) 0 a a a 0 and wouldn't [q a a a q] be invalid and we should set it to [q a a a a] instead?
•  » » » » 3 years ago, # ^ |   0 i mean set 0 to q only once if there are no q in array.
•  » » 3 years ago, # ^ |   +10 First, there are a few nasty cases related to the last query: is there any q in the input array, or else is there at least one zero to put it there...After that, I had another approach, somewhat technical yet trivial on the other hand. For each query from 1 to q, remember the first and the last index for this query. (For query 1, let's say it covers the whole segment, just to get rid of zeroes.) Now process all queries in order; to do it in , we can just use a segment tree. Alternatively, a scanline-like approach would also work, treating first and last indices as "query started" and "query ended" events, and processing them from left to right. Finally, check that what we got corresponds to the non-zero entries of the given array.
•  » » » 3 years ago, # ^ |   0 i thought about "segtree","priorityque",etc at the first glance,but the time limit 1 sec roared at me,"_stay away kid_"...
•  » » 3 years ago, # ^ |   +10 Consider the construction of a as follows: First, place 1's from the start to the end. Then, place the smallest possible segments for each number (so, for query q, go from the first instance of q to the last one). If there are no instances of q, place it where you will eventually place the last query (so, don't worry about it). If the last query is empty according to above setup, put it on a 1. If the last query is empty and there are no 1's, then the situation is impossible.Of course, this is O(NQ). We want to do it a bit faster, so let's store the ends of each segment in some array. Then, go from the first position of a to the end, while maintaining a priority queue of the segments you are currently looking at. For each number in a, add it to the queue. Check if that number is the end of a segment, if so, remove it from the queue. If at any point the highest number in the segments is greater than the number in a, then it is impossible. When you come to a zero, just put whatever number is in the queue currently or 1 if there are none. But, if it is the last zero and there is no segment with the last queue value, then place the last queue number instead.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +3 Gassa , WolfBlue Thank you..Finally got it !!
•  » » 3 years ago, # ^ |   +4 I did D with just a priority queue by constructing what the array has to look like after the queries (41700329).You find the leftmost appearance for every number, and the rightmost appearance for every number. Then, with a priority_queue, you go left to right, doing the following: If the value at the current index is 0, continue Otherwise, if it is the current indexes values leftmost appearance, add it into the priority queue While the rightmost appearance of the topmost element of the priority queue is less than the current index, pop it. If the priority queue is not empty, set the value at the current index in your construction to the largest value in the priority queue. This achieves the same as having query i fill between leftmost appearance of i to rightmost appearance of i.After this, if the number q (from the last query) doesn't appear, put it at some zero. If q doesn't appear, and no zeroes exist, fail. This is since all intervals have nonzero length.Then check that at all indexes that don't contain zeroes in the original array, your construction matches the original array. If it doesn't, fail.Then fill all zeroes with arbitrary adjacent elements, and output the construction.
 » 3 years ago, # | ← Rev. 2 →   +84 Problem C, D and E today are great.
 » 3 years ago, # |   0 In problemE ,I ask a wrong query. But why return me a TLE and MLE rather than WA or invalid input? As I know, every round in codeforces didn't return TLE and MLE in the past time. I'm very angry now, it wastes me too much time.
•  » » 3 years ago, # ^ |   +45 Answer "BAD" instead of "YES" or "NO" means that you made an invalid query. Exit immediately after receiving "BAD" and you will see Wrong answer verdict. Otherwise you can get an arbitrary verdict because your solution will continue to read from a closed stream.Maybe this?
•  » » 3 years ago, # ^ |   +16 Don't be angry, be careful.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +10 "Answer "BAD" instead of "YES" or "NO" means that you made an invalid query. Exit immediately after receiving "BAD" and you will see Wrong answer verdict. Otherwise you can get an arbitrary verdict because your solution will continue to read from a closed stream." EDIT: I got ninja'd.
 » 3 years ago, # | ← Rev. 4 →   +1 what a great contest!
 » 3 years ago, # |   +25 Kudos to problemsetters :D The problem set was balanced with fun tasks(specially D)
 » 3 years ago, # |   +1 I think there is either a problem in the solution of A or the test cases are very weak. For 7 7abc*abcabc!abcthe answer should be NO.But codes that give YES are also getting accepted. I think the constraint that * can only be replaced by lowercase Latin letters has being ignored.
•  » » 3 years ago, # ^ |   +14 the string t consists only of lowercase Latin letters
•  » » 3 years ago, # ^ |   +6 The third line contains string t of length m, which consists only of lowercase Latin letters.
•  » » 3 years ago, # ^ |   +5 ...the string t consists of only lowercase Latin letters...The test is invalid.
•  » » 3 years ago, # ^ |   0 Problem the statement, "The third line contains string t of length m, which consists only of lowercase Latin letters."
 » 3 years ago, # |   +133 Thank you for the contest!Problem E is very nice.
•  » » 3 years ago, # ^ |   +20 I'm glad you liked it :)
 » 3 years ago, # |   0 How to view on which test case my solution was hacked?
•  » » 3 years ago, # ^ |   0 You can see that after the contest is finished.
 » 3 years ago, # |   +16 Freaking A again!
 » 3 years ago, # |   0 my E will fail. (
 » 3 years ago, # |   +5 Editorials please!
 » 3 years ago, # |   +9 Really weak pretests :(
 » 3 years ago, # |   0 tc 87 for problem A ??
 » 3 years ago, # |   +32 Deadly problem A :D
•  » » 3 years ago, # ^ |   0 Even less than B and C. be scared.
 » 3 years ago, # |   +12 What were the problems that were taken from VK Cup finals 2018?
 » 3 years ago, # |   -10 F was easier than A!
 » 3 years ago, # |   0 can any one help me with the Problem B in CF round#504 ended few hours ago?? i am not getting the logic of the solution of others may be that is math logic please explain if any one can help than...?[problem:B. Pair of Toys ][contest:http://codeforces.com/contest/1023]
•  » » 3 years ago, # ^ |   0 Let me give you a hint.Suppose n == 10, k == 10So you can make 10 in 4 ways 1. 1 + 9 2. 2 + 8 3. 3 + 7 4. 4 + 6So, you can now observe that, you can make k in (k-1) / 2 ways if n >= k-1. Try the rest yourself :)
 » 3 years ago, # | ← Rev. 6 →   0 What is going on with my solution for problem E? I submit a query and, even though I never receive BAD as an answer, I do not receive an answer sometimes on test case 18 (see diagnostics). Does the interactive program print extra characters or whitespace?Edit: Never mind, the diagnostics are just bogus.
 » 3 years ago, # |   +3 when will be the solutions available?
 » 3 years ago, # |   +3 How to solve problem B, please explain the logic of math behind it.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +5 Imagine you have n=10, in how many ways can you make the sum 10?1+9 = 2+8 = 3+7 = 4+6 = 10 (4 pairs)Do you see the pattern? Now, why is this surely the answer? Well, because it is stated that the pairs (a,b) and (b,a) are the same and because we have each number only once. Now, there are 3 cases to consider: 1. n>=k 2. k-n>n and 3. k-n <= nLets think about the first one together, then you can think about the other two:n>=k means that we have numbers that are bigger than the sum k. You can't use such numbers because, well, they are already bigger than k. What is the biggest number you can use then? Its k-1, because you can pair it with 1 to sum k. So just assume n=k-1 and count the pairs like I did in the first example. You will end up with (k-1)/2 pairs.
 » 3 years ago, # |   +1 Can anyone explain why this code gives TLE for Problem C . Link for the solution http://codeforces.com/contest/1023/submission/41695850
•  » » 3 years ago, # ^ |   +5 You allocate a new copy of the answer string on each iteration. Try  ans += '(';  instead.Even better, just print the output directly to cout.
•  » » 3 years ago, # ^ |   +5 Use a+=x instead of a=a+x for strings. AC solution: 41731870
•  » » 3 years ago, # ^ |   0 When you use a = a+'(' , first of all it creates a copy of a and then it inserts ( and then it assigns to your main string a . you can simply do this : a+='(' . It will just insert the character
 » 3 years ago, # |   0 CONFUSED BETWEEN PYPY2 AND PYTHON2I have been using pypy2 for over a month and I shifted to pypy2 from python2 just because pypy2 is faster than python2, but today when I tried question C using pypy2, it gave TLE and when I submitted the same code with python2, it worked fine. Pypy2 solution: 41730885 -- verdict=TLE. Python2 solution: 41730897 -- verdict=Accepted Can someone tell me when to use python2 instead of pypy2 ?????? Thanks
•  » » 3 years ago, # ^ |   0
•  » » » 3 years ago, # ^ |   +8 wow thanks man collares that was exactly what I needed :)
•  » » » 3 years ago, # ^ |   0 Thanks A lot :)
 » 3 years ago, # |   +8 Benq kept his promise to become a LGM :)Congratulations !!My mission is nearly done unless you win the IOI!
 » 3 years ago, # | ← Rev. 2 →   +17 Since a lot of people seems to be using max segtree for D (my in contest idea was lazy max segtree but it would go against my morals to submit something like that), I thought I'd elaborate on the sweep/set technique.Basically you store O(n) amount of start, and end events.Here is how you calculate them: Spoilerfor (int i = 1; i <= n; i++) if (leftV[arr[i]] == 0) { leftV[arr[i]] = i; st[i].push_back(arr[i]); } for (int i = n; i >= 1; i--) if (rightV[arr[i]] == 0) { rightV[arr[i]] = i; ed[i].push_back(arr[i]); }Then you can use this information to calculate, for a point, which values have hit their leftmost point but not yet their rightmost point. We call the maximum of these values "val", in my code I called it "maxcover".This can be stored in set , or priority_queue (heap), because you only care about the maximum. (I think mango_lassi did this) Codefor (int i = 1; i <= n; i++) { for (auto e : st[i]) s.insert(e); //starting events (inclusive) maxcover[i] = (*s.rbegin()); for (auto e : ed[i]) s.erase(e); //ending events (inclusive) }Then using this information you can optimally assign any 0 values to val[i] described above.
 » 3 years ago, # | ← Rev. 3 →   0 C looked easier than A. Link for Editorial of CI have also tried to explain A's approach. Link for Editorial of A
•  » » 3 years ago, # ^ |   +3 Thanks a lot buddy. A nice solution
 » 3 years ago, # |   +29 My problem F got TLE because I didn't remove the "cerr" in my code. So my code printed 5e5 integers to stderr...... (It is interesting that "cerr" in my code was not executed for samples) I know this is a hilarious mistake and it is my own fault... Well, I expected this would get "WA", but I got "Pretest passed" instead... QAQ
•  » » 3 years ago, # ^ | ← Rev. 3 →   0 Stderr is ignored when checking correctness, cerr can cause TLE only, it can't cause WA. In order to not worry about time it takes I suggest you do the following:1) Compile with -DLOCAL flag locally2) Add #ifndef LOCAL #define cerr if(0)cout #endif to your templates.
•  » » » 3 years ago, # ^ |   0 Thank you! I'll try this next time XD
 » 3 years ago, # | ← Rev. 3 →   +11 Problem C was easier than A...Just remove n-k characters from the string. When you remove '(' from the string, remove ')' from it too. Where index of '(' is less than ')'.
 » 3 years ago, # |   0 Aha, I believe there will be tutorials soon. ;)
 » 3 years ago, # |   0 thanks to problem A ,haha ,good question
 » 3 years ago, # |   +32 Weak testcases in DMy solution gives NO for Testcase2 8 0 5 
 » 3 years ago, # |   +8 When will the editorial be published? I'm so eager to see how problem G can be solved. (Because nobody has solved it yet :-)
 » 3 years ago, # | ← Rev. 2 →   +18 In D shouldn't be the output of the following testcase YES but it's showing 'NO'. 3 3 2 1 3 Weak test cases.solution
 » 3 years ago, # |   0 Can anyone explain what is meant by the error or what does it mean in the following E problems solution? Solution link isYour text to link here...Thanks in advance:)
•  » » 3 years ago, # ^ |   0 Why have you done cout << dp[i][j] ?
 » 3 years ago, # |   +18 Where's the editorial?
 » 3 years ago, # |   +28 While I was looking through the top Accepted solutions for 1023D I found out that someone got his solution accepted on the following test case: 5 4 4 3 3 3 4 Answer his code produces is 'YES'.According to me the answer should be 'NO'.Can someone explain to me how this solution got accepted?
•  » » 3 years ago, # ^ |   +23 Also this test 3 3 2 1 3 Real answer is "YES", but his answer is "NO".
 » 3 years ago, # |   +16 still waiting for editorail...
 » 3 years ago, # |   0 Can someone explain what I must to do in C?Sorry for poor english.
•  » » 3 years ago, # ^ | ← Rev. 3 →   +8 Given a regular bracket sequence with size n, you have to find a subsequence of it with the size k, which is also a regular bracket sequence (answer guaranteed to exist).A subsequence of a string is created by removing some (maybe none) characters of that string, and keeping the remaining characters by the original order (more details on that below).A bracket sequence is a sequence/string consisting only of ( or ).We can define the term "regular bracket sequence" recursively, like: "" (empty string) is a regular bracket sequence (RBS). If R is a RBS, then "(R)" (R being inside a pair of parentheses) or "R()" or "()R" (the string "()" stands right before/after R) is also a RBS. Take the first sample test for example.With the string ()(()), there are many subsequences with the length of 4, like ()((, ()(), ())), (((), (()), )((), )()).Among them, only a few are regular bracket sequences, like (()) or ()().You can choose any sequence among these — they are all valid answers.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 Maintain a stack and traverse the string. If you encounter '(', push onto stack. If you encounter ')', pop from stack. This removes 2 elements from the final string. You need to pop (n — k) / 2 times. Print the contents of the stack.
 » 3 years ago, # |   0 Can anyone suggest what I am missing out in my submission for question D. 41737987
•  » » 3 years ago, # ^ |   0 5 31 2 1 3 1Your program answers NO while the answer exists.
•  » » » 3 years ago, # ^ |   0 Thank you for helping me figure out my mistake.
 » 3 years ago, # |   +8 Can anybody tell the link of editorials for this contest?
 » 3 years ago, # |   +8 Where is editorial?
 » 3 years ago, # | ← Rev. 2 →   +11 Can someone please explain the stack or priority_queue method for solving D. I was able to solve it using Segment Trees but even after reading comments, I couldn't understand how to do it using stack or priority_queue.
 » 3 years ago, # |   0 Why does 4*n number of queries seem inefficient in problem E ?https://codeforces.com/contest/1023/submission/41731400
•  » » 3 years ago, # ^ |   0 Try this: 9 ......... ####..... ...#..... ...#..... ......... ...#..... ...#..... ...#..... ...#..... Your program correctly goes to r=5, c=5 and then asks ? 5 4 9 9 which is YES (? 1 1 5 4 would lead to NO if that query was allowed). Your program then stumbles around in that trap, querying some fields repeatedly, using up more than 4*9 = 36 queries...
 » 3 years ago, # |   +3 Can someone explain a solution with HLD for problem F?
•  » » 3 years ago, # ^ |   0 I can explain the idea.We can obtain a minimum spanning tree T of the graph by setting the weights on our edges to 0 and running any MST algorithm, since we know that we will eventually set the weights on our edges such that they will all be included in the MST.The main observation is that given any edge e = (u, v, w), we know that the path from u to v in the minimum spanning tree T cannot contain any edge e' with weight w' > w. Otherwise, T - e + e' would be a lower cost MST. We can use HLD to compile all such constraints imposed by our competitor's edges and determine the maximum possible weight for each edge in the MST.However, I am not sure if it's an intended solution. I was barely able to squeeze my HLD implementation under the 3s time limit. To do it I had to make use of the fact that we update arbitrary paths but only query single edges, so we can use a segment tree without lazy propagation: http://codeforces.com/contest/1023/submission/41885123Interestingly, you could modify it further using the fact that all of the queries come after all of the updates; it is not even necessary to use a segment tree at all.
 » 3 years ago, # |   0 can someone please provide a test case where this solution will fail http://codeforces.com/contest/1023/submission/41825727
•  » » 3 years ago, # ^ |   +3 3 5 1 1 1 
 » 3 years ago, # |   +16 Where can I find the editorial of this round?
•  » » 3 years ago, # ^ |   +5
 » 3 years ago, # |   0 O(n) solution for Problem D C++: https://codeforces.com/contest/1023/submission/41909557 Java: https://codeforces.com/contest/1023/submission/41909242
 » 3 years ago, # |   +3 editorial ???
•  » » 3 years ago, # ^ |   0
 » 3 years ago, # |   0 Can someone please tell me what is wrong in my logic? And a counter example to prove it wrong in a case: http://codeforces.com/contest/1023/submission/42091597Thanks.
 » 3 years ago, # |   0 Hi,I saw an accepted submission to problem D that shouldn't be accepted. For instance, the submission 41770128 in the list of submissions to problem D returns Yes to 5 3 1 3 1 1 3It should be "NO", shouldn't?
 » 3 years ago, # |   0 For problem D of the contest following test case: 4 4 4 2 1 3 Some have answer: YES 4 2 1 3 But some solution printing "NO" instead are also accepted. Please include this test case.