By Vladik, 3 months ago, translation,

Hi Codeforces!

I am glad to announce and invite you to Codeforces Round #689 (Div. 2, based on Zed Code Competition), which will be held on Dec/11/2020 17:35 (Moscow time).

We want to offer you to solve 6 problems taken from the Zed Code Competition 2020, which was held as part of the Adapt by Zed conference powered by EPAM Systems.

This round will be rated for the participants with rating lower than 2100.

Thanks a lot for your contribution to the preparation of the round! Good luck with the competition!

UPD: The scoring distribution is 500 — 1000 — 1250 — 1500 — 2250 — 2750.

Congratulations to the winners of div 2:

as well as div 1 winners:

Thank you all for participating! (editorial)

• +328

 » 3 months ago, # |   +171 As a tester, 1 in 7 children does not have enough food to lead a happy and active life, but what does it take to end global hunger? Participate in Codeforces Round #689.
•  » » 3 months ago, # ^ |   -16 Feel Good to you and your friend as a first time tester Sir !!
•  » » » 3 months ago, # ^ |   0 It do feel good to me
•  » » 3 months ago, # ^ |   -20 I really don't get it.
•  » » 3 months ago, # ^ | ← Rev. 2 →   +86 As a tester, my name is not mentioned in the tester's list. ⊙︿⊙Edit — Now I'm on it.
•  » » » 3 months ago, # ^ |   +10 people thought you were lying but in fact, you are not. Now all of us should give you an upvote.
•  » » 3 months ago, # ^ |   -15 GOD.
•  » » 3 months ago, # ^ |   0 Where is score distribution??
•  » » » 3 months ago, # ^ |   0 The scoring distribution is 500 — 1000 — 1250 — 1500 — 2250 — 2750.
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   0 yes, after i write comment scoring distribution, updated :)
•  » » 3 months ago, # ^ | ← Rev. 3 →   -15 Now a days, announcement isn't fulfil without 1-gon's style beging comment.
 » 3 months ago, # |   +50 As a tester, I love Zebras!
•  » » 3 months ago, # ^ |   +23 Same here!! And I can say after the contest everyone will love zebra.
•  » » » 3 months ago, # ^ | ← Rev. 2 →   +15 Zebra themed contest would be nice for loving zebra. Edit: I hate zebras :D
•  » » » » 3 months ago, # ^ |   +2 your profile picture is interesting
•  » » » 3 months ago, # ^ |   +8 Hope it doesn't end up like Pony's contest
•  » » 3 months ago, # ^ |   0 As a contestant, me too :D
•  » » 3 months ago, # ^ |   +3 Who's idea? btw I'm neutral towards zebra but the photos were good and calming to look at. Thanks
 » 3 months ago, # | ← Rev. 2 →   0 Good luck to everyone participating!
 » 3 months ago, # |   0 I think it will be a good contest!Good luck to everyone!
 » 3 months ago, # |   +16 As a tester, wishing you all Happy Rating :)
•  » » 3 months ago, # ^ |   0 Thank you.
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 Isn't rating a zero sum game? Although, I'm not entirely sure what the method to compute rating delta is...
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 No, it's not. It's a negative sum game.
 » 3 months ago, # |   +1 BRCode Will there be 3b1b styled tutorials xD?! Im aware it must be really hard to make but they're really great BTW don't stop making them.
•  » » 3 months ago, # ^ |   +12 Hi, sorry I was just testing this round — there won't be any video editorials for it. However I am making video editorials for a contest later this month, so look out for that :p
•  » » » 3 months ago, # ^ |   -8 Can't wait for it ;)
 » 3 months ago, # | ← Rev. 2 →   -24 [copyright striked by Digon]
•  » » 3 months ago, # ^ |   +38 As a plagiarism hater, stop copying my son's comments every now and then
 » 3 months ago, # |   -16 I will be glad to participate and test my knowledge
 » 3 months ago, # |   0 The unseen bug is the deadliest
•  » » 3 months ago, # ^ |   -7 no meme for this announcement?
•  » » » 3 months ago, # ^ |   0 No memes are meaningless and offensive according to codeforces rule.
•  » » 3 months ago, # ^ |   -21 10x deadlier when combined with weak pretests.
 » 3 months ago, # |   0 I think it will be a good contest!Good luck to everyone!
•  » » 3 months ago, # ^ |   0 good luck ■■■
 » 3 months ago, # |   0 Good luck everyone ❤️
 » 3 months ago, # |   +26 As a tester, I want to wish you good luck and high rating!
•  » » 3 months ago, # ^ |   +6 Unfortunately, I don't see your name in the testers list
•  » » » 3 months ago, # ^ |   +4 Unfortunately, I don't know what were you looking at :)
•  » » » » 3 months ago, # ^ | ← Rev. 3 →   +47 Unfortunately, then there are four possibilities 1.You're from a different world line and you haven't tested this round in this world line (according to the announcement at least) 2.Your name hasn't been added to the list given in the announcement but you tested this round 3.You never tested this round 4.You are an alt account of one of the testers and mistakenly commented from the wrong account :P.
•  » » » » » 3 months ago, # ^ |   +20 Change language to Russian)
•  » » » » » 3 months ago, # ^ |   +30 Yes, I'm sorry, my name is only mentioned in the Russian version.
•  » » » » » » 3 months ago, # ^ |   +32 Alright, I get it, then it's the 2nd possibility, thanks for testing this round :)
•  » » » » » » 3 months ago, # ^ |   +40 sorry, fixed :)
 » 3 months ago, # |   +10 I suspect there's a problem that will require Z-algorithm. ;)
•  » » 3 months ago, # ^ |   +14 If there is I am going to troll them by solving it with KMP.
•  » » 3 months ago, # ^ |   -22 Now even if they planned to have such problem, they will replace it with another problem because of this comment!!!
•  » » » 3 months ago, # ^ |   0 It is five hours left. Are you sure they can replace a task in this time?
•  » » » » 3 months ago, # ^ |   -33 I think they should, but if above is true then it will be either a D or E problem and replacing that would be little difficult. I still think its doable since there are too many questions and rounds already in queue, they can use a similar difficulty problem from future round.PS: After all this comment, if we still see a question on string pattern matching it can help few candidates to gain rating.
•  » » » » » 3 months ago, # ^ |   +69 Oh, man, change a task for that reason?Well, authors, change all the tasks please! I think there will be tasks for 2-sat, binary search, bitmasks, bruteforce, chinese remainder theorem, combinatorics, constructive algorithms, data structures, dfs and similar, divide and conquer, dp, dsu, expression parsing, fft, flows, games, geometry, graph matchings, graphs, greedy, hashing, implementation, interactive, math, matrices, meet-in-the-middle, number theory, probabilities, schedules, shortest paths, sortings, strings suffix structures, strings, ternary search, trees and two pointers.
•  » » » » » » 3 months ago, # ^ |   -37 Lol, Do you really think writing all the data structures is equivalent to the first comment? Let say we actually have a D problem on Z-algorithm in this contest, then you don't think people seeing a substring and string pattern question will first try to relate it to Z-algorithm?Okay if you disagree with all of my above comment, then why contestants are not allowed to comment even on data structure used in a problem during contest?? I must say sometimes knowing which data structure to use makes problem much easier to solve.
•  » » » » » » » 3 months ago, # ^ | ← Rev. 2 →   +5 Main phrase is "during the contest". This statement about Z-function is useless, because participants don't know the tasks and all their guesses are just random.
•  » » » 3 months ago, # ^ |   0 Chill dude. Why so serious?
•  » » 3 months ago, # ^ |   0 What is Z-algorithm?
•  » » » 3 months ago, # ^ |   +10
•  » » » » 3 months ago, # ^ |   0 Is it very advanced one or recommended for div2
•  » » » » » 3 months ago, # ^ | ← Rev. 2 →   0 I think that it is recommended for div.2, also there are some similar themes for div.2, like Prefix function or String hashing.
 » 3 months ago, # |   +6 As a tester the problems were very interesting :)
•  » » 3 months ago, # ^ |   +18 Were the problem statements short, sir?
•  » » » 3 months ago, # ^ |   +60 Why everybody wants to see short statements? It is not so difficult to read legends, if they are not very long, of course.As an author of 672 round I would like to say that some authors love interesting legends in their statements. It is such a pleasure to make tasks about your favourite films, or games, or even about your friends.Of course, I can understand participants. Rounds require speed. But to my mind, one or two minutes spent on the legends are not impotant.Please don't downvote me for the unpopular opinion.
•  » » » » 3 months ago, # ^ |   +57 Sorry. I want to see short statements because I want to see the beauty in the problems instantly. And by beauty I mean algorithmic and mathematical beauty. I don't care about the story, and even while upsolving, I become very happy to see a problem which has a short formal description but very hard to think. Most recently: 986C - AND Graph, I bookmarked this problem even after solving it, I was so happy. Also, my dad peeks into my laptop from time to time, and if he sees me solving a problem related to zebras and cookies and Gildong the dog, he will question my career choices. That is why I always switch to some AtCoder problem (without flavour text) when he is around. :P
•  » » » » » 3 months ago, # ^ | ← Rev. 2 →   +12 How do long statements relate to "algorithmic and mathematical beauty"? Legend is only a story around the mathematical construction.If you don't like stories, you can just skip it and get the formalistic statements."I become very happy to see a problem which has a short formal description but very hard to think." I agree with you, of course, beautiful tasks are very nice. But why this task can suddenly become worse if there was a legend? The task remains the same, the solution remains the same.If it is just aesthetic love to short statements... well, maybe. But I still don't understand it.And yes, your situation with your dad is interesting, but I don't really think that this could be a real argument for other people.However, I appreciate your opinion. "So many men, so many minds".
•  » » » » » 3 months ago, # ^ | ← Rev. 3 →   +33 I don't care about the storyThis might change your mind.
•  » » » » » » 3 months ago, # ^ |   -14 I'm sorry, what's wrong with this task?
•  » » » » » » » 3 months ago, # ^ |   +30 I think the story is very well connected to the problem which makes it interesting.
•  » » » » » » » » 3 months ago, # ^ |   -9 Oh, I thought that you were against this task.Now, I agree with you, this is a beautiful legend that fits the task pretty well. Nice example :)
•  » » » » » 3 months ago, # ^ |   +35 "Gildong the dog"Since when Gildong was a dog?
•  » » » » 3 months ago, # ^ |   +30 But some people like me are bad at English and have to use the Google Translate to read the problems,and long statements are difficult for them to understand >_<
•  » » » » » 3 months ago, # ^ |   +10 There was a really great round 635, where statements have legends, followed by a picture. All that lies above picture is a legend, all that lies below — a statement.This trick solves your problems with English.
•  » » » » » » 3 months ago, # ^ |   +25 Thanks for that.But actually,**few** CF problems with long statements has a short formal description below the legends.I strongly suggested that if the author want to make the statement long,at least he need to add a short formal description.Besides,the long statement may has some confusing words that may lead some competitors with bad ability of understanding(like me) understand the problem in a wrong way,and wastes a lot of time.
•  » » » » » » » 3 months ago, # ^ | ← Rev. 2 →   0 No, I disagree. If I will have a legend and a task apart, it will look like "listen, I have a legend, but nobody cares about it so here is a formal description".Real life tasks most commonly don't have formal statements.
•  » » » » » 3 months ago, # ^ |   +9 What's worse,when we copy the statements to the Google Translate,the Markdown and the $\LaTeX$ would be lost.
•  » » » » 3 months ago, # ^ |   0 I think one issue is some legends don't really add anything to the problem. Legends like having a city connected by roads being described by a graph or two playing a game and determining the winner if both players play optimally seem natural. Legends like someone receiving and array for their birthday and having to calculate some property of it seem a little contrived. Then there are those legends where person A proposes a problem to person B and person B can't solve it for reasons like not having enough time, being too young or being too small and now they ask you to solve it for them. There's also the other situation where person B can solve it and they want to know if you can solve it too. Some of these can be entertaining but also feel a little unnecessary.
•  » » » » » 3 months ago, # ^ |   0 I'm strongly agree with you! Legends like "birthday" or "B can't solve" or "can you solve it too" are so annoying! Honestly, I... well... At least I don't like this types of legends (i don't like it very, very much).However, I was talking about good legends, without this typical words about birthdays or "A wants to solve but can't".
•  » » » » » 3 months ago, # ^ |   0 How did you know that mike recieved an array for his birthday lol.
 » 3 months ago, # |   0 What is the problem score distribution?
 » 3 months ago, # |   +4 I hope Vladik will put me on the tester's list. ⊙︿⊙
•  » » 3 months ago, # ^ | ← Rev. 2 →   +2 I am sure, he will.
•  » » » 3 months ago, # ^ |   0 I think Vladik doesn't like you or maybe he is giving you an opportunity to maximize your rating.
•  » » » » 3 months ago, # ^ |   +3 I guess it's a trap. :)
 » 3 months ago, # |   +1 Wow netman, was once an IGM. I thought Vladik was the highest rated at first. Looking forward to some really good math problems.
 » 3 months ago, # |   0 Hope to learn something new :)
 » 3 months ago, # |   0 I'm trying but not getting better. I hope I will do well in today's contest.
•  » » 3 months ago, # ^ |   +10 Did you try not trying?Taking breaks actually help.
 » 3 months ago, # | ← Rev. 2 →   0 What is the score distribution of problems ?
•  » » 3 months ago, # ^ |   0 *Problems
•  » » 3 months ago, # ^ |   +6 The scoring distribution is 500 — 1000 — 1250 — 1500 — 2250 — 2750.
 » 3 months ago, # |   -12 bad contest.
•  » » 3 months ago, # ^ |   +25 no you
 » 3 months ago, # |   +18 And now I want to ask you: were the problems' statements short enough? :)
•  » » 3 months ago, # ^ |   +3 yes, found them easy enough to interpret
•  » » 3 months ago, # ^ |   -10 sir A's statement is not making sense.
 » 3 months ago, # |   -20 Anyone else found B to be a mere implementation exercise? It took me almost 2 hours, mostly because I kept telling myself that Codeforces either wants a "smart solution" or a super dumb solution. C looked cool, though.
•  » » 3 months ago, # ^ |   0 I tried to give n^3 brute-force solution, not sure what tripped it off .100956182
 » 3 months ago, # |   +6 Great contest! I thought I had registered but apparently, I did not, that cost me 10 minutes of the contest and my mistake ended in an emotional downturn the rest of the time :(
 » 3 months ago, # |   0 I hate Probability.
 » 3 months ago, # | ← Rev. 2 →   +1 How to solve C ?
•  » » 3 months ago, # ^ |   0 Find such maximal position X that for all i > X it is true that a[i] = i.Then just calculate the answer with a well-known formula:ans = 1if (r[i] >= X) ans = ans * (1 — p[i])Answer is 1 — ans.
•  » » 3 months ago, # ^ |   0 Here is how I thought about it : First we find the first index such that the suffix of the array is sorted. Now inorder to make the array not sorted after m operations, the elements at index = (first_index-1 to n) should not be sorted. Then just do 1-x as we have to find winning probability. Idk why it fails on pretest 2. C//Think simple yet elegant. #include using namespace std; #define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define ll long long #define all(v) v.begin(),v.end() #define ff first #define ss second #define pb push_back #define mp make_pair #define pi pair #define REP(i,n) for(int i=0;i> t; while(t--){ cin >> n >> m; double y=1.0; vector a(n+1); for(i=1;i<=n;++i){ cin >> a[i]; } if(is_sorted(all(a))){cout<> v(m+1); for(i=1;i<=m;++i){ cin >> v[i].ff >> v[i].ss; } sort(all(v)); vector suff_sorted(n+1,false); if(a[n]==n) suff_sorted[n]=true; int first_ind=n; for(i=n-1;i>=1;--i){ if(a[i]==i && suff_sorted[i+1]){ suff_sorted[i]=true; first_ind=i; } } double x = 1,init=0; int ind=m+1; if(a[n]!=n) first_ind=n+1; for(i=1;i<=m;i++){ if(v[i].ff>=(first_ind-1)){ ind=i; break; } } //cout<
•  » » » 3 months ago, # ^ |   +1 OMFG i just found out the mistake, I should have initialized ind=m and not m+1 :(
•  » » 3 months ago, # ^ |   0 Well first find the length of the largest suffix of a that is sorted in ascending. Say it has length len. Then let x = n-len. Clearly, if any operation (r, p) has r >= x, the whole array is sorted. Lets say we have opi1, opi2, ... opik where 1 <= i1 < i2 < ... < ik <= m, such that the previous condition is satisfied. picking any combination of these operations to go through to sort the corresponding prefix of array a will suffice to sort the whole of array a. Also an interesting thing is the probability of this occuring is exactly 1 minus the probability of the complement, that is, none of these operations going through. None of the other operations opi matter if it doesn't belong to the previously said list. Now the probability of this compliment, is just the product of (1-pi1)(1-pi2)...(1-pik). As I already said, ans is 1 minust that. One corner case is if array is sorted to begin with, in which case the answer is just 1.0. (As ops don't affect array)
•  » » » 3 months ago, # ^ |   0 I did the same thing, I was a bit confused about the corner case first. So here's a thought : If some prefix of the array is already sorted given that (prefix_index>first_index where suffix is sorted) then we should not count it in finding the winning probability as no matter we include it or not the array will always remain sorted! This logic handles the corner case well and also makes more sense. However we count it's contribution to the final answer, why is that?
•  » » » » 3 months ago, # ^ |   0 Because in the given corner, if we use the same algo logic, we'll be ignoring the case where, even if all those ops with r >= x don't go through, the array remains sorted. Which means, the product that we subtract from 1 normally, isn't valid in this case. That's literally the only difference between the ans of the algo and the way we handle the algo.
 » 3 months ago, # |   0 Could not understand question C. Can anyone help?
•  » » 3 months ago, # ^ | ← Rev. 3 →   +1 Note that once the array is sorted it never gets unsorted, by definition of the problem.Then, if a postfix of len x is sorted, the array can get sorted in each experiment if $r[i]+x>=n$ In this case it stays unsorted with prob $1-p[i]$So we need to multiply all these numbers to get the probabilty that the array is still unsorted after last experiment. Then ans equals 1-prop.
•  » » » 3 months ago, # ^ |   +8 Got it now. Thank you!
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 Give you a permutation.Then give you $m$ operations like $(r_{i},p_{i})$. It means in this operation, It has $p_{i}$ probability to let the first $r_{i}$ numbers in the permutaion be sorted. You task is to find the possibility of permutations to be sorted.
 » 3 months ago, # |   0 What may be test 2 of problem C test 13 of problem E ?
•  » » 3 months ago, # ^ |   +8 test 13 of E is probably some overflows on long long
 » 3 months ago, # |   +1 Can anyone pls explain the solution of problem B...? :(
•  » » 3 months ago, # ^ | ← Rev. 2 →   +3 Since you can easily get the solution later. Here's a hint, try searching for problem "Maximal square in a rectangular matrix having 1" and try to use the same approach. I used same.
 » 3 months ago, # |   +5 How to solve E?
•  » » 3 months ago, # ^ | ← Rev. 2 →   +18 My solution breaks it into two cases, although maybe someone else can provide a more concise solution.I won't detail the exact formulas, but you can see them in my submission.Case 1: $x \geq y$The overall value of $k$ diminishes over time, so we should greedily add $y$ whenever possible to prolong the time the cooler amount stays above $l$. Initially, for some number of days, we won't be able to add $y$ without overflowing past $r$, so our cooler amount decreases by $x$ for each of those days. After a certain point, we will always be able to add $y$ without overflowing, so our cooler amount decreases by $x - y$ for the remaining days. We can calculate all this information in $\mathcal O(1)$ with some math.Case 2: $x < y$Because $y$ is greater, we can always first let the cooler drain at a rate of $x$ for as many days as possible, before adding $y$, then repeating. This is optimal since we're only refilling when absolutely necessary, so we don't risk overflowing $r$. There might be an $\mathcal O(1)$ math formula for this, but I'm not sure. I did $\mathcal O(x)$: whenever we add $y$, it's because we can no longer drain any more $x$, so $0 \leq k - l < x$. We can thus treat this as a graph that cycles through nodes $0 \dots x - 1$, and if we ever encounter a cycle, we know that going through this cycle will sustain the cooler capacity for the entire $t$ days.I know that wasn't the clearest explanation (I found it a bit difficult to put into words), but hopefully the code can clear up any doubts. https://codeforces.com/contest/1461/submission/100945988
•  » » » 3 months ago, # ^ |   +8 Thanks a lot for writing such a detailed explanation Wiz. :)
 » 3 months ago, # |   +3 These error involing precision always frighten me. Solved D,E but could not C even after many attempts. Can anyone help what is wrong with my code? https://codeforces.com/contest/1461/submission/100926909
•  » » 3 months ago, # ^ |   +3 Try using long double
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 Edit: nvm, see comment below
•  » » 3 months ago, # ^ |   0 Actually, you are not reading all the input for a test case and returning early.
 » 3 months ago, # |   0 how to solve E??? Can't even know how to approach...
 » 3 months ago, # |   +1 I was implementing an inclusion-exclusion for c but kept getting tle on pretest 10.
•  » » 3 months ago, # ^ |   +1 Inclusion-Exclusion is O(2^n). For example,| A U B U C| = |A| + |B| + |C| — |A ∩ B| — |B ∩ C| — |C ∩ A| + |A ∩ B ∩ C|
•  » » 3 months ago, # ^ |   +3 Inclusion exclusion wasn't needed. 1-p would be the product of individual (1-pi's) provided the part after position ri is sorted From that p can be computed
•  » » 3 months ago, # ^ |   +1 I have used inclusion-exclusion as well. But I have used dp for calculating it.
 » 3 months ago, # | ← Rev. 2 →   +18 Is it just me or was C too easy? B felt harder to implement.My approach for C, If you know array after idx is sorted, then any operation that operates on idx or above will completely sort the array. So probability of atleast one such operation = 1 — probability no such operations happen.
•  » » 3 months ago, # ^ |   0 with same approach, why my code failshttps://codeforces.com/contest/1461/submission/100926909please help to find error.
•  » » » 3 months ago, # ^ |   +18 I did the same stupid mistake, you terminate the function for maxp == 0 and don't read the remaining input
•  » » » » 3 months ago, # ^ |   0 Ah Yes!! I thought about this explicitly :) Lucky me.
•  » » » 3 months ago, # ^ |   0 You need to sort probabilities by prefix length.
•  » » » » 3 months ago, # ^ |   0 You need to ignore all probabilities which to short prefix length.
 » 3 months ago, # | ← Rev. 2 →   +23 I think D is well-known. upd: Divide and Conquer DP
•  » » 3 months ago, # ^ |   0 what is it, I wrote a strange recursion which might fail if someone hacks
•  » » 3 months ago, # ^ |   0 Can you please provide a reference? Thanks.
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 I solved it with Divide and Conquer too. here is my code if you're interested 100954072
•  » » 3 months ago, # ^ |   0 is it, can you please share the link if possible?
 » 3 months ago, # |   0 What was the logic for problem B
•  » » 3 months ago, # ^ |   0 Just implementation (you can use prefix sums as well).
•  » » » 3 months ago, # ^ |   0 How to do it using the prefix sum?
•  » » » » 3 months ago, # ^ |   0 Well... Just as said: you bruteforce the peak of the tree (the highest *), then just check if there are all elements are * on the lower layers (prefix sums can done it O(1), which is fast). So, in total we have O(N^2*M).
•  » » » » » 3 months ago, # ^ |   +1 100962567 O(N^2*M) gave TLE in B.
•  » » 3 months ago, # ^ | ← Rev. 2 →   +13 Let's define dp[i][j] as a number of spruces where (i, j) is the top. Now you can calculate dp table iterating from bottom to the top in the following way: if s[i][j] == '*': dp[i][j] = min(dp[i+1][j-1], dp[i+1][j], dp[i+1][j+1]) + 1 else: dp[i][j] = 0 The answer to the problem will be the sum of all values in the dp table.
•  » » » 3 months ago, # ^ |   -8 Intersting solution... Do you have a proof for it?
•  » » » » 3 months ago, # ^ |   0 It seems obvious to be to increment the total number of spruce to be one more than the minimum of three components below
•  » » » » 3 months ago, # ^ |   +3 I would like to think of this as: dp[i][j] is the maximum height of the spruce where (i, j) is the top, instead of the number of spruces.It's obvious that, looking at (i, j) alone, if the maximum height is dp[i][j], there are dp[i][j] possible spruces starting from (i, j).Now, to have the tree with height dp[i][j], you need the next layer, which are dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1], to have the same height of dp[i][j] - 1. That's why you take the minimum of them, and add 1.I'm not sure if this helps, but this is my perspective on the solution.
•  » » » » 3 months ago, # ^ | ← Rev. 3 →   +9 This picture is not to scale but can help.Assume there are cells bellow as well.
•  » » » 3 months ago, # ^ |   +6 Amazing solution with better time complexity
 » 3 months ago, # |   +5 Could someone tell why my problem C code was giving TLE .
•  » » 3 months ago, # ^ |   +3 You are not getting whole input correctly
•  » » » 3 months ago, # ^ |   0 thanks , ig fireblaze777 is pointing the same below .
•  » » 3 months ago, # ^ |   0 Did the exact same mistake -_-
 » 3 months ago, # |   +41 Am I the only one who wasted 30 minutes on C and then realizing that I took forced the solution to the next test-case without reading the queries for that problem PS: spookywooky can relate :(
•  » » 3 months ago, # ^ |   +4 that costed me 2 penalties
•  » » » 3 months ago, # ^ |   +4 yeah me too :(
•  » » » » 3 months ago, # ^ |   +3 We are all beginners ;)
•  » » » » » 3 months ago, # ^ |   +3 LGMs left the chat.
 » 3 months ago, # |   0 How to optimize B ?
•  » » 3 months ago, # ^ |   0 Use prefix sums.
 » 3 months ago, # |   0 Some one please debug my code for Q4 100952421
•  » » 3 months ago, # ^ |   0 Just a small hint: to prevent bugs in binary search you can try to use lower_bound() and upper_bound()
•  » » » 3 months ago, # ^ |   0 It fails in pretest7 till then it was all good
•  » » 3 months ago, # ^ |   0 My code was failing too in pretest 7. For me, it was an integer overflow problem and changing int to long long int fixed the code.
 » 3 months ago, # |   0 Is there any other way than dp for B?
•  » » 3 months ago, # ^ |   0 B is not dp
•  » » » 3 months ago, # ^ |   0 B is in my opinion a spin off of a classic dp problem Maximal square If you this problem, I guess coming up with dp solution would be much more easy
•  » » 3 months ago, # ^ |   0 i know a way using manacher algorithm and two pointer in $O(n*m)$ worst case
•  » » » 3 months ago, # ^ |   0 Could you tell me about it please?
•  » » » » 3 months ago, # ^ | ← Rev. 3 →   +3 here , Basically i calculate horizontal radius for each cell, using manacher algorithm for each row, by putting $*$ to $1$ and rest all $.$ to different values >1 , and then i applied column-wise two pointer, so we could get in n * m time.
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 I used a simple algorithm for BBasically, build it from the bottom (after checking for valid indices, etc.) : tree[i][j] = min({tree[i + 1][j - 1], tree[i + 1][j], tree[i + 1][j + 1]}); ReferenceEdit: Perhaps that qualifies as DP (not sure)
 » 3 months ago, # | ← Rev. 2 →   0 My question answered. Have a a nice day
 » 3 months ago, # |   0 Very nice problemset!!! XD
 » 3 months ago, # |   +6 B is very similar to https://codeforces.com/contest/1393/problem/D
•  » » 3 months ago, # ^ |   0 Nah that problem D was 50x more cancer than this problem B :P. On this problem B they were generous enough to let you bash.
•  » » » 3 months ago, # ^ |   +8 If problem D is cancer you did it wrong...
 » 3 months ago, # |   0 How to solve D ?
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 I believe segment tree should do it, just sort the array beforehand. For some reason I could not get the second test in the given pretest right, so I didn't submit. But still it seems relatively simple. Correct me if I'm wrong.The method I thought of is instead of getting the traditional tm = (tl + tr) / 2, we use binary search to find the first index greater than our mid element.And finally, you insert the sum from tree[v] into some set. In the end for each query if you can find it in the set it's possible, otherwise not.
•  » » 3 months ago, # ^ |   +9 Just a simple "merge sort"-like recursion will do it all.
•  » » » 3 months ago, # ^ |   +1 I thought that only , but if we divide the array into two parts , and sum of both left and right is greater than sum required then we have to check in both half . So wouldn't that take O(n) per query ?
•  » » » » 3 months ago, # ^ |   +14 You need to precompute all the possible sums using divide and conquer. Then ,for each query, you just need to check if the required value exists or not (using a Map,for example).
•  » » » » » 3 months ago, # ^ | ← Rev. 2 →   0 Is'nt there a possiblity of exceeding memory limit in case the size of map or set becomes very big?
•  » » » » » » 3 months ago, # ^ |   0 The maximum number of sums that we can get should be in the order of $O(n)$ i think.
•  » » » » » » 3 months ago, # ^ |   0 It can be proved by induction that the number of all possible answers won't exceed n.
•  » » » » » 3 months ago, # ^ |   0 Do you have any similar problems ?
•  » » » » 3 months ago, # ^ |   0 Just calculate sum of both left and right array and store it in set. After this call for next two halves... You can traverse the array for sum calculation or use prefix sum also.. Then for each query check the no. in set and print accordingly...
•  » » » » 3 months ago, # ^ |   0 We devide the array in all possible subarrays, and store the sum for each one somewhere.Then while queries we can "directly" give the answer in log n.
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   +1 No, actually it is much faster than it looks like.It is easy to see that the maximum depth of recursion is $log(n)$ because each time we are splitting the array into two halves.In each level we are doing at most $n$ operations, by summing up each part of the array.So that's a total time complexity of $O(n*log(n))$.Bonus: we can actually do the summing part much faster by calculating the sum of the desired interval from the sums of its two halves, so that's $O(n)$ time for the whole recursion instead of $O(n*log(n))$, but the total time complexity will remain $O(n*log(n))$ because of the sorting we are doing at the beginning.
•  » » » » 3 months ago, # ^ |   0 you can precompute all the possible answers in nlog(n) , then you can answer each query in O(1) time . giving a total complexity of O(nlog(n) + q)
•  » » 3 months ago, # ^ |   0 Do exactly what the question says. I literally had a vector in a queue and pushed left vector and right vector into the queue and continued doing so until vector size is 1.Basically I calculated all sums possible from a given vector, the complexity would only be O(nlogn)
 » 3 months ago, # | ← Rev. 2 →   0 Does N*M*M/2 pass in B?
•  » » 3 months ago, # ^ |   0 N*M*M will also pass .
•  » » » 3 months ago, # ^ |   0 100956092 didn't pass.
•  » » » » 3 months ago, # ^ |   0 Map is not O(1) it's log(n) . So your complexity is $O(n^3log(n))$
•  » » » » » 3 months ago, # ^ |   0 thanks..i missed that :(
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 but it will be 500*500*500 == 125000000 can we ... is it ok ? it little less than 10^9
•  » » » » 3 months ago, # ^ |   +1 It is 10^9/8, and note that it is actually less than 500^3 since at least one dimension get halved... so we end with less than 10^8.
•  » » 3 months ago, # ^ |   0 I think yes, if you have good implementation.
•  » » » 3 months ago, # ^ | ← Rev. 3 →   0 Hey, my submission is plain vector implementation man, didn't pass sys testing man. Might cost me CM rip. O(N*M*min(N,M)).
•  » » » » 3 months ago, # ^ |   0 Use C arrays instead of std::vector where possible.And also there was much more simple solution. As I know, authors have a Python solution in 0.28 s.
•  » » » » » 3 months ago, # ^ |   0 Damn. Time to learn from mistakes.
 » 3 months ago, # |   0 I solved A in 2 min and then struggled with B for the rest of the competition, can somebody tell me CLEARLY how to solve B ? (I know it is just implementation, but how ?)
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 You can solve it with DP. A similar question like B is this , just change the shape Here is my solution : 100928428
•  » » 3 months ago, # ^ |   0 We want to calculate the number of times that each '*' appeared in a tree so to do that we have an array called ans that ans[i][j] is the number of times that s[i][j] appeared in a tree and we start from the bottom of the grid and the number of appearance for each '*' is: min(ans[i + 1][j] , ans[i + 1][j — 1] , ans[i + 1][j + 1]) + 1 So we calculate ans[i][j] for each '*' and the sum of these numbers is the answer. here's my code 100941879
 » 3 months ago, # |   +3 The values of r may not be necessarily distinct in problem C (:
•  » » 3 months ago, # ^ |   0 So which value should we consider?
•  » » » 3 months ago, # ^ |   0 what I meant to say was that you cannot store all of the values and then compute the answer, because at some point you might overwrite the previous values if the same value of r comes more than once in the given operations.
•  » » » » 3 months ago, # ^ |   0 Oh, that's why my solution is failing. Thanks :]
 » 3 months ago, # | ← Rev. 2 →   0 jf
 » 3 months ago, # |   0 How to implement solution of B?
•  » » 3 months ago, # ^ |   0 you can refer mine 100926055.dp[i][j] in my solution denotes largest length of spruce that can be made from the coordinate (i,j).Hope it helps!
•  » » 3 months ago, # ^ |   0 we will use DP! lets call maximum possible k for a tree rooted at (i, j), mem[i][j]. lets call c[i][j] the minimum number of consecutive *'s from left of the cell or from right of it (including the cell). this can be found using partial (prefix) sum and binary search in O(log(N)).Then the maximum possible k for the cell bellow (i, j) ((i+1, j)), is min(c[i+1][j], mem[i][j]+1), because: mem[i][j] needs to be at least k-1 for mem[i][j] to be k. a k tree has 2k + 1 *'s at the base. Then the answer is just sum of all the mem[i][j]s.Submission using this principle.
 » 3 months ago, # |   +50 The system test for E is weak. I hack someone with the following test after the system test:  31 2 48 27 3 2
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 Yes and this solution 100938127 only checked 82 Tests while your hack is 83rd
•  » » 3 months ago, # ^ |   +9 :sob:
 » 3 months ago, # |   +3 Interesting problemset!
 » 3 months ago, # | ← Rev. 2 →   0 weak pretests :/
 » 3 months ago, # |   0 what sould be the time complexity for problem B? will N^3 solution will pass??
•  » » 3 months ago, # ^ |   0 n^3 will pass
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 but it will be 500*500*500 == 125000000 can we ... how is it ok ? its little less than 10^9
•  » » » » 3 months ago, # ^ |   0 If the constant factor is low, it'll pass. for 1 sec the number of operations is generally around 4*1e8 from what i know. My n^3 passed with 234 ms
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   0 there is a lot of cases that the solution will break in the third loop ex: in the worst case the third loop in row 1 will iterate m/2 in the next row it will iterate m/2 -1 and so on and if in any case, you can't make the current spruce tree you will break so this will make the time is much less
•  » » 3 months ago, # ^ |   -9 in most contests, - O(n^3) for n <= 500, - O(n^2) for n <= 3000, - O(n) for n <= 200000, - O(nlogn) for n <= 1000000 will pass.
 » 3 months ago, # | ← Rev. 2 →   0 I am getting WA on test case 20 in problem C (I think it is about precision). Can someone help?My submission
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 I had same issue, changing float to double worked for me. edit: I just ran your code with the change it worked.
•  » » 3 months ago, # ^ |   0 its because you used float . try submitting the same code with double
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 Use setprecision and doubles
•  » » 3 months ago, # ^ |   0 Thanks to all
 » 3 months ago, # |   0 Pictures were almost matched with problems. A new concept. Thanks to the authors.
 » 3 months ago, # | ← Rev. 2 →   0 I liked the pictures in the questions, but for QB, adding a pragma after comp ends up ACing.WHY!!!!??? :(
 » 3 months ago, # |   0 Can someone please point out what is wrong in my solution for problem C. It got fst on testc-case 25
•  » » 3 months ago, # ^ |   0 float has very limited precision.
•  » » » 3 months ago, # ^ |   +3 damn! I thought I was working with long doubles all this time, why in the world did I write#define ld floatafter writing #define ld long double :((((. I am the dumbest person who ever existed on this planet.
 » 3 months ago, # |   +52 I may have found F interesting, only if s was always "+*".
 » 3 months ago, # |   +3 Why does C fail if we use float instead of double? 100933790
•  » » 3 months ago, # ^ |   +5 float cannot keep the precision enoughly, while double can.
•  » » » 3 months ago, # ^ |   0 I see. Thanks!
 » 3 months ago, # |   0 when will be Editorial released
 » 3 months ago, # |   0 what is limit for memory allocation in C++ during runtime?my solution for B failed system test because i was allocating (3*500*500) memory at runtime in worst case scenario.
•  » » 3 months ago, # ^ | ← Rev. 2 →   +1 the runtime is for writing out of the memory.
•  » » » 3 months ago, # ^ |   0 thanks, i didn't account for the null character. :(.
•  » » 3 months ago, # ^ | ← Rev. 2 →   +4 Because you use char s[n][m], you forgot the place for '\0'. Btw, use VLA and put big arrays on the stack is a bad habit and may cause stack overflow.
•  » » » 3 months ago, # ^ |   0 thanks, i understand now that was a shitty mistake and a bad habit.
 » 3 months ago, # |   0 Hey guys, it was my first contribution and I have one question: Why I have different answers in "custom test" and "submit solution" on problem 1461F? language is the same.
 » 3 months ago, # |   +6 I haven't solved E but I know a TestCase where 1 solution fails I know I can't hack it but is there a way to hack now for somebody else or it isn't possible after system testing.
•  » » 3 months ago, # ^ |   0 You need to be in Div.1 (above $1900$) in order to uphack
•  » » 3 months ago, # ^ |   +5 There are 90 TestCases in E but only 82 are being checked for 100938127 I don't know-how is that possible
 » 3 months ago, # | ← Rev. 3 →   +5 100962567 In spite of using 3 loops(O(N*N*M)) in B, my code gave Time Limit Exceeded on main test case 4.
•  » » 3 months ago, # ^ |   0 Same here man, tough luck.
 » 3 months ago, # |   +1 I think the B is bad. I spent 15 minutes thinking about how to improve my $O(500^{3})$ brute-force because 1e8 is dangerous. However, in fact $O(500^{3})$ can pass it easily. So, what's the meaning of the B? Just for testing Brute-force?If so,that is obviously unresonable.
•  » » 3 months ago, # ^ |   0 First Hand candidate who failed B on O(N*M*min(N,M)). You did a good job optimising chill.
 » 3 months ago, # |   +29 Problems B and D were about justifying to yourself why brute force should work :P
 » 3 months ago, # | ← Rev. 2 →   0 x
•  » » 3 months ago, # ^ |   0 may be that's because your code has matched with someone's code or you were using double account during the contest
 » 3 months ago, # | ← Rev. 6 →   +36 List of ideas that solve F: 100956230 Cases of ss (when sorted) is one of {"+", "-", "*", "*+", "*-", "+-", "*+-"} (2**3-1==7 cases) Easy casesFor {"+", "-", "*"} there's only one choice. "+-" is same as "+" (replacing every '-' to '+' doesn't decrease answer) Case *-If there are no zeroes, then answer=a[0]*a[1]*...*a[n-1] If there is a zero (at first position first0), then answer=a[0]*...*a[first0-1]-a_[first0]*...*a_[n-1]. Case first0==0 is "somewhat" special (don't attempt to output leading '-' in -a[0]*a[1]*...*a[n-1]) Cases *+ and *+-Similar to "+-" case, we can replace every — with + and don't decrease answer, so there are only 2 options for each operation: * or +. Handle zeroesif a[idx] == 0, then the answer is in form a[0] op[0] a[1] op[1] ... op[idx-2] a[idx-1] + a[idx] + a[idx+1] op[idx+1] ... a[n-1], so we can solve original task for subarrays of a that don't contain 0 Handle ones on end of subarrayNow we handle some subarray a[L:R], 0<=L 1Then answer is a[L] * ... * a[R]. How many values >= 2 do we need? log2(10**5) ~= 17, lets be safe and take 19. If there are >= 19 i-s, with a[i] > 1, we're done.Now we're left with this situation: a[i]>=1, a[L],a[R]>=1, and at most 18 a[i]>1. Compressing onesNotice that our array doesn't contain much information (many values == 1), so it seems natural to compress long runs of 1 with run-length-encoding: [a[i+0]==1, a[i+1]==1, ..., a[i+(k-1)]==1] === [1] * k. This "compression" works because to attain max value we need to have either " + a[i] + ... + a[i+(k-1)] + " OR " * a[i] * a[i+1] *... *a[i+(k-1)] * " to achieve maximum value.Also note that, that now we have at most 2*18-1==37 different "groups" (each "group" corresponding to either a[i] >=2, or to a subarray of all ones: a[L:R]. Final leapNow we're ready to solve final reformulation of our problem: there are <=37 "groups" of either a[i] >=2 or a[L:R] == [1] * (R-L+1).Note that the answer for our subarray will not exceed 9**18 (which fits in long long).We do this with a dynamic programming: dp[i] is the max value that we get using i first groups. dp[0]=0, and dp[i]=max(j
•  » » 3 months ago, # ^ |   +8 Thank you, I got all these ideas except the last one with dp, now I know what I missed.
•  » » 3 months ago, # ^ |   +15 That's it! SpoilerIn the 10th nested spoiler :woozy_face:
 » 3 months ago, # |   0 Guys, I’ve just received message from System user that my solution for task B has similarities with other solutions, what should I do in such case, should I provide some evidences that I had done it by myself? What’s my next actions?
 » 3 months ago, # |   +9 Thank you very much, I managed to get back to green after almost a year!
 » 3 months ago, # |   0 For problem D, I used the following solution: 1. sort a. 2. compute prefix sum of a for efficient range sum operations 3. for a given sum s, call the helper method check on the entire range of a.In this helper method check, do exactly what a split operation allows us to do: 1. split by middle value midV; 2. do a binary search to find the right most index midIdx such that a[midIdx] <= midV. 3. then check the range sum of [l, midIdx], [midxIdx + 1, r]. If one of them equals sum, return true; if both of them are smaller than sum, return false; if they are bigger than sum, recursively check on that range.The terminating condition of this check method is: 1. l > r, left index is bigger than right index; 2. the range sum of the current range is < sum; 3. the range sum of the current range is > sum, a[l] == a[r], meaning we can not split anymore. 4. if the range sum is sum, simply return true.My submission is 100978064I keep getting the stack overflow error on one of the recursive call but I can't figure out why my terminating condition is incorrect. Can some one help me with this? Thanks!
 » 3 months ago, # |   -8 I made a stupid mistake. In the c problem, when the array was originally ordered, I directly continued, ignoring the following input. I submitted this question for the first time at 00:51 and passed it in the last ten seconds. It is because of this stupid mistake. So I have an idea, can someone sum up some common stupid mistakes and share them so that when the solution fails to pass, we can first check whether they have made these stupid mistakes (if no one does this, maybe I will Do it).
 » 3 months ago, # |   +8 Finally master! Thanks for very interesting problems and i got a little distance from winners!
 » 3 months ago, # |   0 I recieved a system message about my submission for Problem D coincides with other's submission. But I always use the same FastIO module which can be proved by my previous submission. I don't understand why it's considered a violation of the rules this time
 » 3 months ago, # |   0 THANKS learned a lot
 » 3 months ago, # |   0 am i the only one to think B was tough for normal B problem
 » 2 months ago, # |   0 I am able to solve problem A of almost every contest but having difficulty with solving from B onward can anyone please suggest which level of the problem should I practice from PROBLEMSET to boost my skill?