By awoo, history, 3 weeks ago, translation,

Hello Codeforces!

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

WORK & STUDY OPPORTUNITY IN BANGKOK — B.GRIMM POWER x HARBOUR.SPACE UNIVERSITY

B.GRIMM POWER has partnered with Harbour.Space University to offer Bachelor's and Master’s degree scholarships in Data Science as well as work experience in one of the main infrastructure developers in Thailand.

B.Grimm Power PCL (B.Grimm Power), is a Thailand-based electricity generating and distribution energy company. B.Grimm Power is involved in the development, financing, construction and operation of power plants. Its product portfolio includes solar, hydro, wind power, and Diesel.

We are looking for various junior to mid-level candidates to work on solving tasks in the following fields:

• Data analysis
• System integration
• AI
• Forecasting Modeling

All successful applicants will be eligible for a 100% tuition fee scholarship (22.900 €/year) provided by the B.GRIMM POWER.

CANDIDATE’S COMMITMENT

Study Commitment: 3 hours/day

You will complete 15 modules (each three weeks long) in one year. The daily class workload is 3 hours, plus homework to complete in your own time.

Work Commitment: 4+ hours/day

Immerse yourself in the professional world during your apprenticeship. You’ll learn from the best and get to apply your newly acquired knowledge in the field from day one.

REQUIREMENTS:

• Industry experience
• International exposure
• Eager to learn
• Entrepreneurial mindset
• (Thai Language is a plus, not a must)
Apply Now

UPD: Editorial is out

• +166

 » 3 weeks ago, # |   -45
•  » » 3 weeks ago, # ^ |   0 I like the education field
•  » » » 3 weeks ago, # ^ |   +169 .
•  » » » » 3 weeks ago, # ^ |   +9 Just realised D had more solves than C, I guess I could have tried to solve it. C got me working way too many cases, but, all in vain.
•  » » » » » 3 weeks ago, # ^ |   0 so was i
•  » » » » » 3 weeks ago, # ^ |   0 me too
•  » » » » 3 weeks ago, # ^ |   0 That's so true.
•  » » » » » 3 weeks ago, # ^ |   0 As the loser of the game
•  » » 3 weeks ago, # ^ |   +8 Skill issue
 » 3 weeks ago, # |   +16 I hope that the round will be interesting not only in words, but also in deeds)
 » 3 weeks ago, # | ← Rev. 2 →   +16 codeforces is life Changer
•  » » 3 weeks ago, # ^ |   +1 Would you care to explain how?
 » 3 weeks ago, # |   +6 Super excited! I love edu rounds
 » 3 weeks ago, # |   0 Hopefully this one can break through and get a satisfactory placing
 » 3 weeks ago, # |   0 Where should I put my heart on a night alone
 » 3 weeks ago, # |   0 " After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally. " It's mean I can hack ????
 » 3 weeks ago, # |   +62
•  » » 3 weeks ago, # ^ |   +61 When you use n<<1 instead of n*2 int n=1; n=n+n*2; cout<
•  » » » 3 weeks ago, # ^ |   +13 put paranthesis
•  » » » 3 weeks ago, # ^ |   0 but if you do like this int n = 1; n = n + n * 2; cout << n; // 3 cout << endl; int n = 1; n = n + (n << 1); cout << n; // 3then there is no problem-----
•  » » » » 3 weeks ago, # ^ |   +3 But this will cause more troubles than n*2.
•  » » » » » 3 weeks ago, # ^ |   0 n |= n << 1 
•  » » » » » » 3 weeks ago, # ^ |   0 This will also bring wrong answer, for example: int n=7; // (111)2 n+=n*2; // (111)2 + (1110)2 = (10101)2 cout<
 » 3 weeks ago, # |   +3 hoping for a nice round
 » 3 weeks ago, # |   -27 gimme CM pls xD
•  » » 3 weeks ago, # ^ |   +3 good luck!
•  » » 2 weeks ago, # ^ |   0 You didnt give me CM :(
 » 3 weeks ago, # |   0 I hope that the round will be interesting.
 » 3 weeks ago, # |   0 no
 » 3 weeks ago, # |   +20 The Method of Four Russians?
 » 3 weeks ago, # | ← Rev. 2 →   +38 Today problems difficulty gap visualization:
•  » » 3 weeks ago, # ^ |   +7 And E&F are much more difficult than D...
•  » » » 3 weeks ago, # ^ |   +19 E&F unsolveable for target audience.
 » 3 weeks ago, # |   +51 I hate this round. C is harder than D, that's really not good :)
•  » » 3 weeks ago, # ^ |   +8 I just can't find my mistake in C. Also having invested too much time in C, I don't want to try D.
•  » » » 3 weeks ago, # ^ |   0 Take a look at Ticket 15899 from CF Stress for a counter example.
•  » » » 3 weeks ago, # ^ |   0 try (?())? answer should be YES
•  » » 3 weeks ago, # ^ |   +4 Nice round. But C was definitely harder than D.
•  » » 3 weeks ago, # ^ |   +1 Yeah. I'm curious to see the editorial for problem C.
•  » » » 3 weeks ago, # ^ | ← Rev. 4 →   +13 What I did is, if we have to place a number of '(' and b number of ')' in place of the question marks, then it will certainly work to first place a '(' and then place all b closing brackets. (We need to always maintain that count( '(' ) > count( ')' ). The method that is second best to follow the criteria, is we instead place '(' on question marks 1 to a-1, and a+1. If this produces a valid sequence different from the previous one, then the first answer is not unique. Else, there is only a single solution to the problem.
 » 3 weeks ago, # |   +20 No more hard C please! (As a specialist)
 » 3 weeks ago, # |   +19 How to solve F?
•  » » 3 weeks ago, # ^ |   +53 I imagine the problem as a trie of height $n$. A multiset of strings is then an assignment, assigning a weight to each leaf of the trie (the number of strings in the multiset corresponding to that path in the trie). You get to set a limit $c[s]$ to each non-root vertex denoting the maximum sum of weights in that subtree. However, the actual limit of maximum sum of weights in that subtree is smaller, namely $d[s] = \min(c[s], d[u] + d[v])$, where $u$ and $v$ are the children of that vertex.Let $\mathrm{dp}[i][x]$ be the number of ways to assign $c$-s in a subtree of height $i$ such that the true limit is exactly $x$. Clearly $\mathrm{dp}[0][x] = 1$ for $1 \le x \le k$ and $0$ otherwise. In the general case, for $1 \le i < n$ and $1 \le x \le k$: $\mathrm{dp}[i][x] = (k - x) \displaystyle \sum_{y + z = x} \mathrm{dp}[i - 1][y]\, \mathrm{dp}[i - 1][z] + \sum_{y + z \ge x} \mathrm{dp}[i - 1][y] \, \mathrm{dp}[i - 1][z].$The first term corresponds to the case where the sum of limits in the children is $x$ and we pick a higher limit at the vertex; the second term corresponds to the case where the sum of limits in the children is at least $x$ and we pick $x$ as the limit at the vertex. For $i = n$ it is a bit different because you don't get to pick a $c$ there.The convolutions in the formula above can be calculated using FFT: you calculate a layer of the DP, then use FFT to "square" it and calculate the new one, and so on. The answer is $\mathrm{dp}[n][f]$.
•  » » » 3 weeks ago, # ^ |   0 Why are the no collisions in the dp formula in each term?
•  » » » » 3 weeks ago, # ^ |   0 What do you mean by collisions?
•  » » » 3 weeks ago, # ^ |   +5 "the second term corresponds to the case where the sum of limits in the children is at least x and we pick x as the limit at the vertex."I do not understand this idea, how can we choose a smaller limit than the sum of the children? Do the children sum equal the number of strings that have the prefix at node v?Could you help me with that?
 » 3 weeks ago, # | ← Rev. 2 →   +11 It is too hard to find out what's wrong with my solution in F with only 1 small example. Shouldn't it be more?
 » 3 weeks ago, # |   +18 I always seem to screw edu rounds :(
 » 3 weeks ago, # |   0 what is wrong with my code for D? link : https://codeforces.com/contest/1709/submission/165206888
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   0 y1 can be bigger than y2Got the same bug during contest:(
•  » » » 3 weeks ago, # ^ |   0 fixed thanks
•  » » 3 weeks ago, # ^ |   +6 You need to notice that y1 is no need smaller than y2, and you should query the segment tree from min(y1,y2) to max(y1,y2) instead of y1 to y2. This bug just delay me 30 mintues from getting accepted.
•  » » » 3 weeks ago, # ^ |   0 this bug will cost me my sleep today :(
•  » » » » 3 weeks ago, # ^ |   0 Same bro ;;--;;
•  » » 3 weeks ago, # ^ |   0 y1 can be greater than y2. One small change and you would've got AC :_) 165216733
•  » » » 3 weeks ago, # ^ |   +4 :( i wanna cry
•  » » » » 3 weeks ago, # ^ |   0 Me too...:(
 » 3 weeks ago, # |   +10 yes_no_forces :)
 » 3 weeks ago, # |   0 I know C's solution will be super cool. Not able to code the solution on time but it's a great problem.
•  » » 3 weeks ago, # ^ |   0 maybe it is dp and stack
•  » » » 3 weeks ago, # ^ | ← Rev. 4 →   +12 It was adhoc. Video Solution for Problem C & Problem D.
•  » » » » 3 weeks ago, # ^ |   0 thanks
•  » » » » 3 weeks ago, # ^ | ← Rev. 5 →   0 Got AC in C thanks to that. Even though my code is not solving the problem correctly xDInput: 1 )? My Output: YES But whatever. I take the AC
•  » » » » » 3 weeks ago, # ^ |   +8 The sequence in problem was generated from a valid RBS. So your input is wrong.
•  » » » » » » 3 weeks ago, # ^ |   0 ohhh, thanks!
 » 3 weeks ago, # | ← Rev. 2 →   0 Anyone getting RTE out of nowhere? Or its just me ?Anyone tell me what tf is wrong with this simple code that its throwing RTE
•  » » 3 weeks ago, # ^ |   0 For me, I found out it was because I was taking the max of an empty array...
•  » » 3 weeks ago, # ^ |   0 same on A, rewrited on python..
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +3 cin >> n; vll a(3); for (int i = 0; i < n; i++) { cin >> a[i]; }in this part n is not the size of array. the size is always 3.n is the number on the key in your hands.it's called x in the problem statement.
 » 3 weeks ago, # |   +18 i hated c
•  » » 3 weeks ago, # ^ |   +12 I couldn't even get that far lol. Just totally baffled me.
 » 3 weeks ago, # |   +11 got tle on D becouse i used standard cin instead of ios_base::sync_with_stdio(false); cin.tie(NULL);:(
•  » » 3 weeks ago, # ^ |   0 Arrrrggggghhhh — same for me....
•  » » 3 weeks ago, # ^ |   +8 In this problem we have $m + 5q = 2 \cdot 10^5 + 10^6$ input numbers, pretty big input.
 » 3 weeks ago, # |   +91 The sample test case of D was frankly useless. I spent 40 minutes thinking there was a bug in my Sparse Table, only to notice later that the x coordinates were being given from the bottom instead of from the top as usual. Even in the problem statement this was not mentioned in bold. Imho, if there's only one sample test case, it should be at least robust enough to not work for inverted coordinates.
•  » » 3 weeks ago, # ^ |   +4 Exactly this is ridiculous my wrong submission was because of this thing. Even the second test does not include hacks for that bug.
•  » » 3 weeks ago, # ^ |   0 same
•  » » 3 weeks ago, # ^ |   +13 today's B and D did feel weirdly lazy/obfuscated...
 » 3 weeks ago, # |   +14 How to solve E?
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +11 Root tree from any node. Let val[v] = XOR of values from root to v. XOR of path (x, y) will be val[x] XOR val[y] XOR a[lca(x, y)]. Now if XOR of path is zero you need to change value at lca(x, y). Doing dfs if there is a path in subtree with XOR 0 you can just delete it. Answer is number of deleted subtrees.
•  » » » 3 weeks ago, # ^ |   +5 I'm a little confused — how to find if there is path in subtree with xor 0 efficiently?
•  » » » » 3 weeks ago, # ^ | ← Rev. 2 →   +14 Small to large trick, you can read editorial of problem E here.
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +12 There are few observations. The first one was that if we change a value for a vertex, we can ensure that any paths going through that vertex is never zero as there are only $n^2$ possible different xorpath values versus infinite choices for the value. The second observation was that let's say we know the optimal connected subset of vertices in subtree of root $t$ that are good, let $S_t$ denote this set. If we iterate over the children of vertex u and merge all $S_{c_i}$, where $c_i$ is the ith children of $u$ and if there is a bad path in the resulting set, we remove u. We can simulate this via small-to-large with sets which gives us $O(nlog^2(n))$. EDIT: Oops, I messed up the details for the first observation.
•  » » » 3 weeks ago, # ^ |   +6 Isn't $n^2=1e10>2^{31}$ ?
•  » » » » 3 weeks ago, # ^ | ← Rev. 4 →   +42 You can ignore that because in this problem you can replace the value by any positive integer.
 » 3 weeks ago, # |   0 Nice contest. Solved A, B Din't get time to see problem C.
 » 3 weeks ago, # |   0 misunderstood D -> Wrong Answer*6 -> rank 1000+ -> absolutely rating fall :(
 » 3 weeks ago, # |   0 In C, first I greedily create a valid sequence changing the '?' to '(' while possible, then changing the others to ')'. From these that previously were '?', I swap the last '(' and the first ')'. If this is a correct sequence, then the sequence is not unique. Otherwise, it is. Why does this work, i.e., why could there not be any other choice except the swap I tried?
•  » » 3 weeks ago, # ^ |   +11 Swapping same type of bracket makes no difference.If you try to swap any two brackets of different types, the prefix sum over all these must be >= 2 at all points. Swapping the last '(' and the first ')' is equivalent to checking if min_range(last '(', first ')') is greater than 2. For all other swaps, they all include this subsequence in this swap, so you only need to check this subsequence.
•  » » 3 weeks ago, # ^ |   +3 Like if any other swap work then this will work for example for checking whether a string of parenthesis is correct or not we create a array and do +1 for ( and -1 for ) if we find negative anywhere then it is not allowed string so you already know one solution exist and now what can you try to avoid negative number in array you keep on delaying ) so that the chances for negative number is least
•  » » 3 weeks ago, # ^ |   +3 that swap is the most likely swap to be successfull except the ((()))) last ( comes before first ) sequence for a sequence to be valid a) the numbers of '(' and')' have to be equal b) counting from the first, the number of '(' has to be equal or greater than the number of ')' by b) that swap creates the sequence most likely to be valid
 » 3 weeks ago, # |   0 What is intended solution for C?I came up with: First substitute '?' by '(' from left side, from right side by ')'. Then swap the rightmost substituted '(' with the leftmost substituted ')'. If this results in a RBS then ans=NO, else YES.But somehow not able to make it work until end, maybe some edgecase ?
•  » » 3 weeks ago, # ^ |   +3 number of '?' can be less than 2
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 I had the same idea. Here is my reasoning why it should work: let a be your first BS. Say we have constructed a greedily. a is an RBS. Say there is another RBS b and let i be the first index where it differs from a. Consider the BS c which is equal to b up to i and constructed greedily after. You can see that if b satisfies RBS conditions, then so does c, then so does your BS with the swap.
•  » » » 3 weeks ago, # ^ | ← Rev. 3 →   0 We don't even need that. Say a is the first BS, b is the BS with the swap, and i is the first index where a and b differ. If b is not a RBS, then b[...i] has more closing than opening brackets. But for any other candidate BS c, c[...i] would have at least as many closing brackets as b[...i], so it wouldn't be a RBS either.
•  » » 3 weeks ago, # ^ |   0 Turned out simple bug: f[s[i]=='(']++; assuming f[0] is the number of open brackets :/
 » 3 weeks ago, # |   +15 How to solve Ca) How to check if there is a substitution which gives correct paranthesis? First substitute only open parenthesis, then only closed. Example: ??(?))?)(? -> (((())))() there was 2 open parenthesis, hence first $n/2-2 = 3$ substituted will be open. Check, that this is a correct substitution.b) How to check if there is another substitution? If there is another substitution, there has to also be a substitution as in a), but with swapped last open and first closed parenthesis. Example: ??(?))?)(? -> ((()))()() here first were substituted $3-1$ open, then $1$ closed, then $1$ open, then $2-1$ closed. Check, that this is a correct substitution. If yes, answer is NO, otherwise YES.
 » 3 weeks ago, # |   0 what was the technique used to solve the second qeuestion ? can anyone also provide the code
•  » » 3 weeks ago, # ^ |   0 Prefix Sum Technique
•  » » 3 weeks ago, # ^ |   0 precomputation with prefix sum,
 » 3 weeks ago, # |   0 When i can see other test?
 » 3 weeks ago, # | ← Rev. 2 →   0 Somebody, please help me find mistake in my submission for D. 165211545 Edit: found it
•  » » 3 weeks ago, # ^ |   0 You can see the test cases(as yours is wrong at small test case) and run on your local to debug
 » 3 weeks ago, # |   +11 D << C, D is much easy as compared To c
 » 3 weeks ago, # |   +9 Anyone else who just assume y1 <= y2 in problem D and keep failing test case 4 ?
•  » » 3 weeks ago, # ^ |   0 :(
•  » » 3 weeks ago, # ^ |   0 Me:(
•  » » 3 weeks ago, # ^ |   0 ME ;-;
 » 3 weeks ago, # |   +6 Can someone tell me what the fuck is this? Compiled file is too large [44391155 bytes]I mean I just used NTT and voila.
•  » » 3 weeks ago, # ^ |   +10 your global arrays are too large. it's basically an MLE for when you have statically allocated arrays
•  » » 3 weeks ago, # ^ |   +10 probably templates generate too much code?
 » 3 weeks ago, # | ← Rev. 4 →   +4 I think C can be done like this, Imagine replacing ? with $+1$ or $-1$. If I have $x$ question marks with $+1$ and $y$ question marks with $-1$, ($x,y$ can be easily found by forming simple equations). Then, note that it is always better to put question mark with $+1$ value behind the question mark with $-1$ value, So I only need to check for string in which replaced values of question marks looks like this: $(1, 1...1,-1, 1, -1, -1...-1)$ If this string turns out to be RBS, then answer is "NO", otherwise ans is "YES".Note that the problem gurantees that at least one valid RBS is possible, so replaced question marks which looks like this should always form valid RBS: $(1, 1...1,-1...-1)$PS: Why solutions come to my mind automatically after the contest which i mess up :(
 » 3 weeks ago, # |   -11 I am a simple guy i f**k up one problem, then i f**kup in rest of them also, stressing that i f**ked up in previous problem:)
 » 3 weeks ago, # |   0 Can anyone help me find mistake in 165181854 ? got TLE in 7th case maybe string error?
 » 3 weeks ago, # |   +7 http://acm.hdu.edu.cn/showproblem.php?pid=4915 It is a big OJ in China. And this is a classical （） problem.
 » 3 weeks ago, # |   0 Any idea about test case 7 of Problem E?
•  » » 3 weeks ago, # ^ |   +14 Take a look at Ticket 15896 from CF Stress for a counter example.
 » 3 weeks ago, # |   0 [submission:165213863]idk why is this submission wa
•  » » 3 weeks ago, # ^ |   0 Found it.Forgot that when all ? are left brackets the array goes to a point that is a undefined zero
 » 3 weeks ago, # |   +71 No difficulty of thinking, but coding. A boring competition.
•  » » 3 weeks ago, # ^ |   -68 as you are a red name, I think it's quite natural for you to have no difficulty of thinking in edu contest.
•  » » » 3 weeks ago, # ^ |   +51 I mean compare with other div2 contest, this one is quite boring.
•  » » » » 3 weeks ago, # ^ |   +33 E and F, it is natural to think of dp. And one using data structure another using FFT to optimize the transition.
•  » » » » » 3 weeks ago, # ^ |   0 Yeah, it is natural to think of a dp. But if a problem is solved by a thought "hey, this is dp", this does not mean it is a bad task. However, today's E was quite easy to code, so the only really challenging in implementation task is F.
•  » » » » » 3 weeks ago, # ^ |   -13 Was it like easy dp? idk really
•  » » » » 3 weeks ago, # ^ |   +34 But need quite code capability.
•  » » 3 weeks ago, # ^ |   +4 Also, edu contest is usually implementation based, not so much observation.
 » 3 weeks ago, # |   -59 Nice problems. C requires a smart observation. D is basic segment tree usage. E is basic small-to-large problem.
•  » » 3 weeks ago, # ^ |   0 what's the smart observation for C?
•  » » » 3 weeks ago, # ^ |   0 greedily fill the first several ? with ( and others with ). Then swap the last filled ( and first filled ).
•  » » » » 3 weeks ago, # ^ |   0 Could you please explain why swapping those two specific brackets works? Like what's wrong with swapping the first filled '(' and the first filled ')' ?
•  » » » » » 3 weeks ago, # ^ |   0 Take the case ??()?? for example. The best case would be to fill all ( first and then all ), i.e. ((())). If you try swapping the "inner 2" brackets as how Aging1986 had mentioned, you'd get ()()(), which is a rbs so the answer is NO. If you swap any other two brackets you won't get an rbs.This is because when you swap the "inner 2" brackets, you've already placed all ( as much to the left as possible and all ) as much as to the right as possible, so this would always be the next best case in some ways if it is possible.
 » 3 weeks ago, # |   0 I am a little confused. The only difference between these two submissions is： ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); Why it can speed up about 1s???165215022165212687
•  » » 3 weeks ago, # ^ |   0 The input if fairly big, up to 1e6 numbers, so reading input unoptimized takes relevant time.
•  » » » 3 weeks ago, # ^ |   +3 All right, thx! I will optimize the input in the following contests.
 » 3 weeks ago, # |   +13 Who also had WA8 in E because you inserted not after checking for every vertex, but immediately after you checked for this vertex?
•  » » 3 weeks ago, # ^ |   -10 I had WA8 for a different reason: I thought the problem only cares about leaf node.
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 I just was shocked when 6 of my 7 friends who had a submission in E had the same problem.
•  » » » » 3 weeks ago, # ^ |   +8 I found I actually WAed because of the sane reason once.
 » 3 weeks ago, # |   0 165203640 Can you please tell where this is failing?
•  » » 3 weeks ago, # ^ |   0 Take a look at Ticket 15898 from CF Stress for a counter example.
 » 3 weeks ago, # |   0 The editorial will be uploaded tomorrow?
 » 3 weeks ago, # | ← Rev. 2 →   +11 why did you number the rows from bottom to top ??!
•  » » 3 weeks ago, # ^ |   0 It is edu contest, that is usually implementation based. In this sense, reversing the usual orientation actually spices up the problem.Also they made statement of B stupid irritating to make it more thrilling.
•  » » » 3 weeks ago, # ^ |   0 that is usually implementation based. Wait, are we talking about Educational Rounds or Extended ICPC Rounds in general
•  » » » » 3 weeks ago, # ^ |   0 Educational Rounds
 » 3 weeks ago, # |   0 Can anyone explain to me why my solutions with sparse table and segment tree could not pass until I changed cin to scanf? Other contestants did not seem to have the same problem. 165180154 165184210
•  » » 3 weeks ago, # ^ |   0 Add this line: ios_base::sync_with_stdio(false); cin.tie(NULL);
•  » » » 3 weeks ago, # ^ |   0 Yeah, I forgot this template part, makes sense now. My guess was that I messed up somewhere in the main part and had to compensate for it with fast input. No way 2000 div2 people would just casually submit scanf solutions first try LMAO
 » 3 weeks ago, # |   0 I thought C can be solved using BFS. If at any level if we have two same values then it means there are 2 different paths so print "NO". Finally, check if the last level contains the element 0.Is this approach wrong?
•  » » 3 weeks ago, # ^ |   0 Take a look at Ticket 15900 from CF Stress for a counter example.
 » 3 weeks ago, # | ← Rev. 2 →   0 So hey, how do you decide whether to keep working on a problem or bailing/skipping?Feel like I hit the worst of both worlds (again) today's C where I had a brute forcer to get lots of (negative, WA) feedback, and therefore spent juuuust enough time failing there to make sure my AC on D came after contest end (and after the same switched-column bug seemingly everyone else had, but then also some MLEs because I left in the simulated grid, woops).
•  » » 3 weeks ago, # ^ |   +3 well, I have failed C and solved D on previous 2 contests, so I just move to D if I don't get the idea for C within 10 minutes. I think that D problems can be solved methodically, while C problems are a "you either know it or you don't" style.
 » 3 weeks ago, # |   0 In problem C, I thought of first balancing the brackets in the following way : if the number of '(' is more or less than its counterpart, make the number of '?' equal to the difference of number of '(' and ')' become whichever has the minimum count among '(' and ')' and the excess '?'s will be converted according to the one having the greatest count among '(' and ')', extreme ends will be dealt with accordingly with the greatest count among '(' and ')', as the extreme ends can only have one choice.Now, we reach a case where all the '?'s are in the middle of some brackets and the brackets are balanced. Obviously, the number of '?'s will be even and each '?' can be paired as '()'. If the number of '?'s is zero, this is a unique RBS. Assume we have some positive number of '?'s. Now, if there is at least one '(' to the left of the leftmost '?' and at least one ')' to the right of the rightmost '?', then we can also do it in one other way, i.e. ')('.I don't know where I'm going wrong, could someone point out what I'm doing wrong or missing ?
•  » » 3 weeks ago, # ^ |   0 Consider that logic, then prepend "()" to the input. Obviously that prefix does not change the answer, but you might get another answer with your algo.
•  » » » 3 weeks ago, # ^ |   0 Thank you for pointing out the error in my logic.
 » 3 weeks ago, # |   +30 Fuck n,m in D.
•  » » 3 weeks ago, # ^ |   +14 agreed
•  » » » 3 weeks ago, # ^ |   -37 Disagreed.
•  » » 3 weeks ago, # ^ |   +6 I got wa three times for this
 » 3 weeks ago, # | ← Rev. 2 →   +8 My stupid mistake in D was, I just assumed yf > ys for all cases(ik I am dumb) hence segtree quires were giving wrong answer
•  » » 3 weeks ago, # ^ |   0 Samee man, bro, same. Too sad, I realised this just after the contest
 » 3 weeks ago, # |   0 A < B < C (Because of observation that we need to make only two distinct valid string for answer "NO") > D
 » 3 weeks ago, # |   0 This contest had a decent amount of prefix sums lol.
•  » » 3 weeks ago, # ^ |   0 I had learnt about this pre-built(partial_sum) method to create prefix sums yesterday, unfortunately I was not prepared for custom operations.Its simple in case of addition. You can read about it here: https://en.cppreference.com/w/cpp/algorithm/partial_sum
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 For custom operations, I would suggest taking a look at inclusive_scan() & exclusive_scan().
 » 3 weeks ago, # |   +2 unbalanced round makes contest boring
 » 3 weeks ago, # |   0 Excuse me if my question is stupid, but is this round not getting rated, or will there just be some delay?
•  » » 3 weeks ago, # ^ |   0 After 12 hours seccion of hacking ratings would update
 » 3 weeks ago, # |   +3 How to solve E?
•  » » 3 weeks ago, # ^ |   +20 Notice that changing the weight is equivalent to removing that vertex.One approach is to remove the centroid and solve the remaining trees recursively and then remove the centroid if there still exists a zero path going through the centroid.It can also be solved using dfs and small to large merging.
•  » » » 3 weeks ago, # ^ |   0 what value should be on vertices which were removed before some other centroid?
•  » » » » 3 weeks ago, # ^ |   0 A unique power of two
•  » » » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 So when we changed some vertex we dont add its value to some xor value, right? UPD: got it thx
•  » » » 3 weeks ago, # ^ |   0 How do you check if there still exists a zero path going through the centroid? Also, what will the recursive subproblem calls return? I kinda know only the basic idea of centroids, should definitely read up on that
•  » » » » 3 weeks ago, # ^ | ← Rev. 6 →   +18 edit: apparently this is not the centroid solution. I didn't know that was thing, below I am describing the standard dfs solution.First of all notice that we just need to save the xor of all the values from root to a vertex $u$ (call that $f(u)$). Then the xor of the path between two vertices $u,v$ is $f(u)\oplus f(v) \oplus a[lca(u,v)]$.So now the problem is keeping the sets $S(x)$ with all values $f(u)$ for $u\in\text{Subtree}(x)$. That way you can check if there is a 0 xor path efficiently by going through all children $v$ of $x$ and checking if $f(x)\oplus a[x]\in S(v)$ because $f(x)\oplus f(v) \oplus a[x] \iff f(v) = f(x) \oplus a[x]$. In that case you "delete" the vertex, clearing it's corresponding set.To merge the sets fast enough you merge the smallest one with the bigger one. Doing this is fast enough since the number of times a vertex's value $f(x)$ will move to another set is $O(\log n)$ because each time you decide to move it to another set of length $L' \geq L$ ($L$ is the current length) the new set will be of length $L+L' \geq 2L$, this can happen at most $\log n$ times. Judging from the comments here, the last paragraph describes a well known technique usually referred to as "small to large" and it is specifically useful for problems with sets in trees.
•  » » » » » 3 weeks ago, # ^ |   +6 Small to large is not needed for the centroid solution.
•  » » » » » 3 weeks ago, # ^ |   +3 Thank you for the brilliant explanation! Finally got accepted:)
•  » » » 3 weeks ago, # ^ |   0 how do you prove that centroid works out?
•  » » » » 3 weeks ago, # ^ |   0 Any vertex works out, centroid guarantees time complexity.Think about all paths with zero xor. All of them will get at least one vertex removed. If we remove a vertex, solve the subtrees recursively and don't need to remove the current vertex it's easy to see that it is optimal (because zero paths not containing this vertex would need to be removed). If we end up needing to remove this vertex, the recursive calls would have removed the same sets, because the zero paths containing the centroid would have been removed as we remove the vertex.
•  » » » » » 3 weeks ago, # ^ | ← Rev. 4 →   0 I think that using just any optimal solution in each subtree of a vertex is not enough.(X)--(_)--(root)--(_)--(X)In the example above, we have a chain of 5 nodes, the root is the center, and nodes marked with X are removed. Each subtree of the root has a optimal solution, but they don't combine into an optimal solution for the entire tree (the root must be removed as well). You need some extra property for the optimal solution in each subtree: (maybe, for example, among all optimal solutions in a subtree, we select the one where the removed vertices are as close to the root (this is not precise, it's just an idea))
•  » » » » » » 3 weeks ago, # ^ |   0 Can you provide a counterexample with weights instead?
•  » » » » » » » 3 weeks ago, # ^ |   +3 Sample input 3.
•  » » » » » » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 In this case second and fourth nodes woudl be removed...
•  » » » » » » » 3 weeks ago, # ^ | ← Rev. 2 →   +5 This is sample case 3 Root the tree at node 3. Both subtrees have optimal solution (one node removed). But they do not combine into an optimal solution for the entire tree (node 3 must be removed)Each subtree has two optimal solutions. In the left subtree you can either remove node 1 or node 2. If your recursive call returns the wrong optimal solution for the subtree, you can't use it to construct an optimal solution for the entire tree.
•  » » » » » » » » 2 weeks ago, # ^ |   0 Hmm, maybe the centroid solution does not work after all
 » 3 weeks ago, # |   0 hey, I had a question: I wasn't able to participate as I had a school assignment I needed to complete. I just noticed I can still take part in the open hacking... if I do, will it affect my rating?
•  » » 3 weeks ago, # ^ |   0 no
 » 3 weeks ago, # |   -17 How to solve E?
 » 3 weeks ago, # |   +2 I couldn't solve C :sob:
•  » » 3 weeks ago, # ^ |   0 You haven't even upsolved/participated, Have you participated with alt account? If yes how did you become a tester that violates the rules of codeforces :|
 » 3 weeks ago, # | ← Rev. 3 →   0 https://codeforces.com/contest/1709/submission/165219365I write this code but it gave WA in test case 2 in "?)?(??" sample.Can someone please explain what is wrong with my code?
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   0 The code only seems to cover the simple YES-instances, where the number of ? is exactly equal to the number of ( needed, or the number of ) needed after ensuring the first and last characters are correct. However, there are other YES-instances that your code doesn't cover, like this example of ?)?(??. The only valid RBS here is ()(()). No other RBS fits, so the answer is YES.For the correct approach, I advise checking the editorial. Basically, you figure out how many hidden ( and hidden ) there are. Here, there are an equal number of visible ( and ), while there are four ?, so this means there are two hidden ( and two hidden ). Then we fill up the ?s, first with all ( until one, then one ), then one (, then the rest of the ). For the example of ?)?(??, the result is ())((). We then check if this is valid or not; in this case, it is not valid, because the prefix ()) has more ) than (. Therefore, the RBS must be unique, i.e., only valid choice is all (s, then all )s. Note that a valid RBS requires that the total number of ( and ) are equal, and that there is no prefix with more ) than (.
•  » » » 2 weeks ago, # ^ |   0 Thank you bro
 » 3 weeks ago, # |   0 Me : don’t need to know segment tree to hit expert Edu Round 132: Hold my beer !
 » 3 weeks ago, # |   -15 What a poisonous codeforces round. I used to believe in your codeforces educational round,thinking you have high-standard problems and rounds,but this time you make a big fault in problem C and let many participants down, hope you could learn form this failure and adjust the difficulty in future rounds!
•  » » 3 weeks ago, # ^ |   +2 Prob D was such a good intro to segment tree though. But yes C was too much of an ad-hoc problem to be considered educational. (although bracket sequence problems are very standard)
 » 3 weeks ago, # |   0 I have a serious problem for a long time! If I use the segtree in Python, it must be TLE, so does it mean that segtree in python doesn't allow in the contest? if not, I think the tester of the contest should test some of the version to let it accepted, quiet confused~
•  » » 3 weeks ago, # ^ |   0 A lot of times I just translate the tutorial solution of C++ into Python, and then it TLE, so unfriendly to Python user
 » 3 weeks ago, # |   0 Editorial?
 » 3 weeks ago, # | ← Rev. 2 →   0 can somebody check my TLE submission for E my complexity is O(NlogN) and I also used bitset :)
 » 3 weeks ago, # |   +1 How to solve problem F?
 » 3 weeks ago, # |   0 i was solving d using segment tree but getting tle again and again on test case 11 can anyone help please. 165261850
•  » » 3 weeks ago, # ^ |   0 This is probably very frustrating to hear, but please add " ios_base::sync_with_stdio(0); cin.tie(0); " to all of your submissions. Then, things like this will not happen again.
•  » » » 3 weeks ago, # ^ |   0 thanks a lot bro , quite sad to loose this question in contest because of that one line
 » 3 weeks ago, # |   0 where are the editorials tho? will it be posted after the hacking phase?
 » 3 weeks ago, # |   0 How to prove that C's approach is correct
•  » » 3 weeks ago, # ^ |   0 let '(' be 1, ')' be -1， then a parentheses sequence is regular iff the prefix sum off this sequence is nonnegtive at every position and the sum is zero.You can use this conclusion to proof the correctness.
•  » » 3 weeks ago, # ^ |   0 Use the typical exchange argument. Suppose you have adjacent $-1$ and $+1$. Is it good to swap them?
 » 3 weeks ago, # |   0 why tle on my soln Queestion D; https://codeforces.com/contest/1709/submission/165267723 ?
•  » » 3 weeks ago, # ^ |   0 tle on test case 11 can somebody help
•  » » » 3 weeks ago, # ^ |   0 use fast read lol
 » 3 weeks ago, # |   0 The test "?(" can hack many accepted submissions for Problem C. But I miss the hack time.
•  » » 3 weeks ago, # ^ |   +6 No, Because it's written in the problem statement that the main string was an RBC before putting '?'s in it, So your test is invalid!
•  » » » 3 weeks ago, # ^ |   0 Sorry，I didn't notice.Thanks for your reply.
•  » » » » 3 weeks ago, # ^ |   0 You're welcome, Could you please explain the proof of your solution for problem C? Thanks in advance.
•  » » » » » 3 weeks ago, # ^ |   0 I'm sorry.I think about it carefully, and I find that I can't strictly prove it.
 » 3 weeks ago, # |   0 any hints for D??...like where should I start from :)...
•  » » 3 weeks ago, # ^ |   0 Try to find a way, how robot can always go
•  » » » 3 weeks ago, # ^ |   0 okk
 » 3 weeks ago, # |   0 Why is it unrated for me?
•  » » 3 weeks ago, # ^ |   0 Dude, the ratings will be published in a while... hacking phase was finished just few moments ago, they will update the ratings soon ::).. It happens in educational rounds , its normal...
•  » » » 3 weeks ago, # ^ |   0 Ohhh thenks ☺️
 » 3 weeks ago, # |   0 I couldn't solve C, but looking at some submitted solutions, I could reverse engineer the logic (after getting rid of some vacuous code in those submissions). Let's make a simple observation. If we go over the input string character by character, the string becomes invalid if number of )'s becomes greater than number of ('s plus number of ?'s at any point. You cannot close more parenthesis than have been opened at any point. Now, maintain two values, surplus of )'s, i.e., number of )'s minus number of ('s, call it sp, and number of ?'s, call it q. Since there is always a way to substitute ?'s in the input (guaranteed by the problem statement) to get a valid RBS, we know that sp can never become greater than q. Also, we know for sure that if sp becomes equal to q, then all those question marks must be opening parenthesis. Notice that exactly one of sp and q changes in each iteration and by at most 1. Now, here comes the crucial observation that I believe made this problem hard for many people (including me). Actually, as soon as sp becomes equal to q-1, we know that none of those question marks can be a closing parenthesis, because otherwise the string becomes invalid (think why). So what we do is when sp == q-1, we set sp = -1 and q = 0. Then, in the end, range of sp is $[-q,q-2]$. If sp == -q, i.e., all question marks must be ), there is a unique way. We claim that in the end, sp cannot be equal to -q+1, because then the input is invalid (think why). Note that if q = 0, this must hold, otherwise the input is invalid. Otherwise sp != -q and we have maintained the invariant that sp has been at most q-2 after q last became 1. Also, since sp cannot be equal to -q+1 in the end, sp is at least -q+2. Which essentially means that we can change any of these question mark to either ( or ), while maintaining the invariant all along that sp <= q, keeping the string valid, so there are at least two ways. (I believe that there is a more elegant argument involving an invariant using parity of sp - q. If anyone knows, please let me know!)
•  » » 3 weeks ago, # ^ |   +3 Every "(" gives you a credit and every ")" costs you a credit. Because a bracket sequence is valid iff you don't go out of credits when iterating through, you want to get the credits as early as possible and lose them as late a possible. Therefore the solution that always works is if you replace the first x "?" with "(" and the rest with ")", x denoting the number of missing "(". In the same greedy logic, if there is another possible solution, it will be the one with the last "(" you inserted swapped with the first ")" you inserted (second optimal solution for getting the credits as early as possible and losing as late as possible). I just constructed it and checked if it's valid.
 » 3 weeks ago, # |   0 Can anyone tell me what is wrong with my D solution 165201502 ?
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 you should return -1 ( or anything below zero ) in max fuction instead of 0 ( when l > r )
•  » » » 3 weeks ago, # ^ |   0 thank you very much) You realy helped me)
 » 3 weeks ago, # |   0 So, can you tell me where the solution is?
 » 3 weeks ago, # |   0 What is wrong with my solution? My Approach:- i made an array of maps and for i==0 inserted {1,1} and for i>=1to i
 » 3 weeks ago, # |   0 when will be the rating get updated
•  » » 3 weeks ago, # ^ |   0 After the system testing is done.
•  » » » 3 weeks ago, # ^ |   +3 How much longer will it take
•  » » » » 3 weeks ago, # ^ |   +4 Edu rounds usually take 24 hours for rating updates
•  » » » » » 3 weeks ago, # ^ |   +1 Oh!Thank you for your answer
 » 3 weeks ago, # |   0 Thanks for interseting C&E, I learn a lot. But D is too obvious(maybe).
 » 3 weeks ago, # |   +10 Editorial when?
 » 3 weeks ago, # |   0 I'm just stuck on 1300s since a year. Sometimes it feels to give up but I'm not like that, I don't want to give this up. I was a lot better when I first started, keep getting worse after each contest.
•  » » 3 weeks ago, # ^ |   0 look at my profile after I reached my max, I dropped down till newbie then got back. just don't give up and don't take long rest periods. finally.. keep practicing, up solving, and learning new data structures.
•  » » » 3 weeks ago, # ^ |   +1 Thanks for the motivation. I will try my best.
 » 3 weeks ago, # |   0 What's the idea to solve F?
 » 3 weeks ago, # | ← Rev. 2 →   0 I liked the contest
 » 3 weeks ago, # |   0 What is test 2 in C？ I WA in 452nd
•  » » 3 weeks ago, # ^ |   0 You may want to use https://cfstress.com/
•  » » 3 weeks ago, # ^ |   0 Take a look at Ticket 15901 from CF Stress for a counter example.
 » 3 weeks ago, # |   0 This comment is regarding the solution 165164219 for the problem 1709B which significantly coincides with the solution ForPracticeDude/165161762 (which is actually a temporary ID of mine for practice purpose) during the contest Educational Codeforces Round 132 (Rated for Div. 2). I unintentionally submitted the solution from that ID because it was logged-in in another browser of my PC. It was totally unintentional and I solved both of the problems A & B on my own and I am still trying to reach PUPIL very honestly and I have no intention of CHEATING. But due to this incident both of my solutions are marked SKIPPED.I can provide the Authorities with the ID and PASSWORD of both the IDs if they are willing to look into this. And I kindly request the Authorities to please Rate me in the contest Educational Codeforces Round 132 (Rated for Div. 2). As what happened was really unintentional and both of the solutions were mine.
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 You solved A first on that account then proceed to solve B on the other one, not solve A and B both on the practice account. Its unlikely to be accidental, that means you logged out after solving A, logged in to the other one to solve B, once its solved, transfer the answer back. You tested the solution with a fake account which is obviously cheating since its unfair for everyone else
•  » » » 3 weeks ago, # ^ |   0 I said in the above comment that 2 of my browsers were open simultaneously, I know it was my mistake to submit the solution on the other browser but I was not trying to CHEAT. I know I have to bear because of this mistake. I only want that if possible codeforces please revert my RATING to what it was before this contest.
•  » » 3 weeks ago, # ^ |   0 It doesn't work like this you need to share the password of both the accounts too.
 » 3 weeks ago, # |   0 How to understand question C？
•  » » 3 weeks ago, # ^ |   0 Let's look on sequence $s = (??)$ First of all, we know that there exist right sequence. Let's find it, $s = (())$.Two sequence $s$ and $t$ are different if there is a different $i$-th symbol, or $s[i] \neq t[i]$. Now let's try change some symbol from $s$. Try think this way.
 » 3 weeks ago, # |   0 Finally Specialist :)
 » 3 weeks ago, # |   0 can anyone help me find what's wrong in this? submission D
 » 3 weeks ago, # | ← Rev. 2 →   0 I'm not very good at using this feature and mistakenly sent this message the message I really want to send is below sorry please ignore this message
•  » » 3 weeks ago, # ^ |   +3 always remember to add these lines. int __FAST_IO__ = []() { std::ios::sync_with_stdio(0); std::cin.tie(0); std::cout.tie(0); return 0; }();