Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### liouzhou_101's blog

By liouzhou_101, history, 7 months ago,

1480A - Yet Another String Game

Tutorial
Solution

1480B - The Great Hero

Tutorial
Solution

1479A - Searching Local Minimum

Tutorial
Solution

1479B1 - Painting the Array I

Tutorial
Solution

1479B2 - Painting the Array II

Tutorial
Solution

1479C - Continuous City

Tutorial
Solution

1479D - Odd Mineral Resource

Tutorial
Solution

1479E - School Clubs

Tutorial
Solution

• +185

 » 7 months ago, # | ← Rev. 2 →   -15 Thank you for high quality problems! Got suck on Div2 problem C and now found that it was only a binary search.
 » 7 months ago, # | ← Rev. 2 →   -64 Will this round be unrated?
•  » » 7 months ago, # ^ |   +17 The problem A is same as find-local-minima-array. The problem B2 is similar to CF802A.
•  » » » 7 months ago, # ^ |   0 seems like GFG have been headache for problem setters.
 » 7 months ago, # | ← Rev. 2 →   -176 Problem C is noice!
•  » » 7 months ago, # ^ |   +36 Huh? The contest has exactly one constructive problem.
•  » » 7 months ago, # ^ |   +12 why do people downvote?
•  » » » 7 months ago, # ^ |   +22 Look at the first revision of the comment
•  » » » » 7 months ago, # ^ |   +19 Thanks
 » 7 months ago, # |   -18 Div 1A/2C was a nice use of binary search!
•  » » 7 months ago, # ^ |   +25 but was available on gfg
•  » » » 7 months ago, # ^ |   -6 this makes me even more sad :((
•  » » 7 months ago, # ^ | ← Rev. 2 →   -25 .
•  » » 7 months ago, # ^ |   +7 Very nice pretests, also!!!
 » 7 months ago, # |   +107 Thank you for the original problems and strong pretests.
•  » » 7 months ago, # ^ |   +9 Now I understood the hidden meaning of this line.. xD
•  » » » 7 months ago, # ^ |   +4 I guess he should have rejected 1-2 more problems. :)
•  » » 7 months ago, # ^ | ← Rev. 2 →   -28 Sad Reality!
•  » » » 7 months ago, # ^ |   +4 apparently somebody doesn't understand sarcasm
•  » » 7 months ago, # ^ |   -18 contest was good but the pretests were useless .
 » 7 months ago, # |   0 Thank you for the speedy and high-quality editorial with elaborate proofs :) . Keep up the good work!
 » 7 months ago, # | ← Rev. 2 →   +61 For problem D, you don't need to consider an xor of 4 paths; we just have $f(u, v, l, r) = f(1, u, l, r) \oplus f(1, v, l, r) \oplus \mathbf{1}_{A_{lca(u,v)}}$; then you can special case $A_{lca(u,v)}$ and the rest just needs to find one unequal index, which doesn't require any special mod 2 properties of XOR.
•  » » 7 months ago, # ^ |   -88 have the same doubt. I think div2 B and div1 D both wrong questions or no proof they have for correctness. so MikeMirzayanov u gonnna re test all submissions with test case Spoiler1 1 1000000000 10 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000or no? tell fast. even many top rankers have different answer for the test case. tell me
•  » » » 7 months ago, # ^ |   +48 I don't think we're talking about the same thing, I'm giving a simplification to the solution of Div 1 D.
 » 7 months ago, # | ← Rev. 2 →   0 Hello.What is the answer for this test (Div.2 B) :1 1 101000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 10000000001000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
•  » » 7 months ago, # ^ |   0 "NO" Since Hero will die on attacking monster 1
 » 7 months ago, # | ← Rev. 2 →   -11 Can anyone tell me why my solution for Div2B is wrong? (https://codeforces.com/contest/1480/submission/106778511)Edit 1: It's fixed now. This solution gave WA during the contest but they rejudged it later and it's now AC.Apparently the problem-setter's code didn't correct for the possible long long overflow which occurs when taking a sum of all the damage the Hero is going to take.
 » 7 months ago, # |   -10 The problem Div 1A/2C , could be many local minimals ?
•  » » 7 months ago, # ^ |   +3 Yes, you need to print any one of them
 » 7 months ago, # |   0 Div1 B caught me completely off guard.
 » 7 months ago, # |   -8 good problems but weak pretests
 » 7 months ago, # |   +54 If you like videos, here's one that happens to have all the div. 2 solutions
 » 7 months ago, # |   +61 Nice Div1 B1 editorial
 » 7 months ago, # |   0 Man my Div2 C/Div1 A Binary Search solution with 5*Log2(n) gave TLE on test 11 this is not right man. can anyone tell me the reason for TLE in this solution https://codeforces.com/contest/1480/submission/106790379
 » 7 months ago, # |   0 Was anyone able to figure out why TC 11 of problem C gives FST?
•  » » 7 months ago, # ^ |   0 I think mine failed on 1-based index.
•  » » 7 months ago, # ^ |   0 You are not storing the values after the query. This results in repeated queries. I did the same thing. :(
•  » » » 7 months ago, # ^ |   0 Yeah but I'm using only 3 queries at max. each time before reducing binary search range,which happens 18 times(worst case). That is still less than 60 queries.
•  » » » » 7 months ago, # ^ |   0 That's exactly what I thought. But the accepted solutions I have seen differ from mine in just this one aspect. Well the sys tests are almost over. Let's see what was the reason.
•  » » » » » 7 months ago, # ^ |   0 the test case is 1
 » 7 months ago, # |   0 Thank you very much it will help us
 » 7 months ago, # |   0 What's the proof of div2C why is binary search working here
•  » » 7 months ago, # ^ |   +10 Imagine it as hills. If you are at a valley, you don't need to move. If you are at a peak, you can go in either direction. If you are at a slope, just go down the slope until you get to a valley.
•  » » » 7 months ago, # ^ | ← Rev. 3 →   0 for n=7, if the array is — 3 4 5 6 7 1 2 ,then the only local minima is element 1 at index 6.but firstly the mid is element 6 ,which is greater than the previous element 5,so,according to gfg solution i have to go to the left portion doing high=mid-1,but there is no local minima in the left. Can you explain this?
•  » » » » 7 months ago, # ^ |   +3 3 is also a minimum since the ends are +inf (in the question).
•  » » » 7 months ago, # ^ |   0 but will the solution work if the numbers are not distinct?
•  » » » » 7 months ago, # ^ |   0 Idts there will be cases of flatland and you wouldn't know if it is a plateau or a basin. It also depends on the way you define local minimum. Since 3 points at same height can be considered local minimum then this idea should work.
 » 7 months ago, # |   +18 Can hos.lyric and maroonrk explain their solutions to Div1E? It seems that they used different solutions from the one in the editorial (which uses very advanced generating function techniques).(I know maroonrk's solution got TLE, but the fact that it only failed on test 76 indicates that it is probably a correct solution with a high constant factor.)
•  » » 7 months ago, # ^ |   +28 My solution is light $O\left(\sum_{i=1}^m a_i + m \log \mathit{MOD}\right)$.The calculation of the potential function is the same as the editorial. After that (using the notation of the editorial) we keep track of $g(0) + \cdots + g(a)$ as a fraction with denominator $(n - 1) \cdots (n - a)$ so that we can compute the numerator and the denominator without division modulo $998244353$. We only conduct divisions only when $f(a_i)$ or $f(n)$ is actually needed. The bottleneck is $3 n$ multiplications modulo $998244353$, which I hoped to pass.
•  » » 7 months ago, # ^ | ← Rev. 3 →   +21 There's a simple form for $f(a)$. Define $prod(r,l)=l\cdot (l+1)\cdots r$. From the editorial, $f(a)=0$ and $g(a)=f(a+1)-f(a)=-2\cdot \frac{prod(2n-1,2n-a)}{prod(n-1,n-a)}.$You can verify that $f(a)=-2\cdot \frac{n}{n-1}\cdot \left(\frac{prod(2n-1,2n-a)}{prod(n,n-a+1)}-1\right).$Looks like maroonrk precomputed some factorials to evaluate $prod(r,l)$ quickly, but as noted above, this is not necessary to pass.https://codeforces.com/contest/1479/submission/106861209
• »
»
7 months ago, # ^ |
Rev. 5   +55

I think the editorial is a little long winded; here's my high level summary.

### Section 1 of the editorial: finding a closed form

First, it's not too hard to convince yourself that the expected stopping time from any state is of the form $f_n(n) - \sum f_n(a_i)$ for some function $f_n$. We can write out a system of linear equations using the transition probabilities, and explicitly solve it to get a solution $f_n(0) = 0$ and $f_n(k) - f_n(k-1) = \prod_{i=0}^{k-1} \frac{2n-i}{n-i}$. (Note that there are actually many solutions, $f'_n(k) = f_n(k) + ak$ is a valid solution for any $a$, and we can even pick it so that $f'_n(n) = 0$ so that the stopping time is just $\sum -f'_n(a_i)$. This is the simplest form though.)

### Section 2 of the editorial: evaluation

All that remains is to evaluate $f_n(\cdot)$ efficiently. The submissions you're referring to all just evaluate $f_n$ in $O(n)$ time using the formulas given above; if you take some care to avoid doing modular divisions, you can just squeeze it through. That's why these submissions look so much shorter than the editorial; they are using the exact same closed form though.

The editorial describes ways to evaluate everything in $\tilde{O}(\sqrt{n})$ time. These are very similar to the techniques to compute large factorials quickly; essentially, you expand the product of $\prod_{i=0}^{\sqrt{n}} (x+i)$ as a polynomial in $x$, and then use multipoint polynomial evaluation with FFT to evaluate it for $x = \sqrt{n}, 2\sqrt{n}, \ldots, n$. The formulas in this version are slightly more complicated, but the techniques are pretty much the same.

 » 7 months ago, # | ← Rev. 2 →   +3 I haven't seen anyone else fail for test 55 for problem C, could someone point me in the right direction/test case as to why my solution is wrong? I can't see the test for it as of yet.submission:I've considered the case for n == 1 & 2. I'm not using an array to store the values which apparently could lead to repeated queries, but people seem to be getting a TLE in an earlier test case for this.Perhaps my binary search implementation is skipping over an element for the minimum. As always, apologies for the god awful formatting, it's my first time solving an interactive problem.
•  » » 7 months ago, # ^ |   0 You're querying for out of bound indices. When mid = 1, you'd query for index 0 as well.
•  » » » 7 months ago, # ^ | ← Rev. 2 →   0 Ah, I see. I completely forgot to consider that the 1 indexing for the problem could lead to out of bound situations. Appreciate the quick response :)EDIT: Now that i think about it, the reason I did not consider for this condition was to (lazily) check for the minimum and maximum cases at the first step itself, to prevent thinking about it in the actual implementation.
 » 7 months ago, # |   +27 Solution of Div1 B1 is so... big.
 » 7 months ago, # |   -8 Any idea why my code fails for Test Case 55?
 » 7 months ago, # | ← Rev. 4 →   +26 Did somebody order a heartbreak?
•  » » 7 months ago, # ^ |   +3 B passed on rejudging! ily liouzhou_101.
•  » » » 7 months ago, # ^ |   +21 liouzhou_101 I feel my submission is wrong. And there are many submissions like mine. The mistake I did is I checked if the hero's health before giving the final blow is >= 0 instead of > 0 (i.e. totalAttack — max(a) <= B instead of < B).Please rejudge (I know I'll lose my rating but a mistake is a mistake :))
•  » » » » 7 months ago, # ^ |   +4 Ah yes, I did the same mistake but got AC in B. I guess they trimmed the test cases in a hurry. Should rejudge or just revert the ratings. Latter would be easier I guess.
•  » » » » » 7 months ago, # ^ | ← Rev. 2 →   0 can anyone please tell me what is wrong in this logic for div2 B. the last monster to kill will be the one which gives max damage to the hero. therefore health just before fighting that last monster be hr. if(ceil(hr/Ek)>=ceil(Hk/A)) hero wins. ceil(Hk/A) means the number of turns to kill the kth (the last one) monster. hr/Ek means the number of turns to kill hero. we check this over all last possible monsters(i.e. the one giving the max damage to hero) submission
 » 7 months ago, # | ← Rev. 2 →   -10 Strongest TestCase ever (for Div2 B)...xD
 » 7 months ago, # |   -10 can someone prove div2b editorial solution?
 » 7 months ago, # |   -9 My incorrect solution passes for D1.. Weak main tests as well :/
 » 7 months ago, # |   0 Could anyone please help me understand why I got a WA? 106825850. I can see that my fundamental understanding of binary search is wrong, but I'm not able to understand why there's a problem when taking the range as [l m-1] instead of [l m]
•  » » 7 months ago, # ^ |   0 When you update the range to [l m-1] instead of [l m] in the case a_m < a_m+1, you disregard the possibility that a_m might be a local minima itself(it's already lower than a_m+1, it could be lower than a_m-1 making it a local minima) and exclude it from your range.
•  » » » 7 months ago, # ^ |   0 Ah, got it now, thanks!!
 » 7 months ago, # |   +39 liouzhou_101 I don't think changing the constraint after the contest makes sense, as we solved for the given constraints only and overflow wasn't handled then I think the author should rejudge with correct answers instead of changing constraints after the contest.
•  » » 7 months ago, # ^ |   +12 I think authors would rather change constraints and keep the round rated than get 90% (according to Anton) of solutions FST and a massive outrage.
•  » » » 7 months ago, # ^ | ← Rev. 2 →   +3 But how is that fair to remaining 10%. Also, the reason for massive outrage wouldn't be 90% FST but the weak pretest leading to such outcome.Anyway please avoid such solutions in future.
•  » » » » 7 months ago, # ^ |   0 I can see your point, and I understand why you would be upset about the changing of the constraints. However you also have to look at it from the authors' perspective. They really only have three options: Make the round unrated Keep the constraints and cause 90% of all solutions to FST Change the constraints so unintended overflows are no longer an issue What would you do?
•  » » » » » 7 months ago, # ^ |   -16 1 or 2
 » 7 months ago, # | ← Rev. 3 →   +62 Alternate solution for Div1B/Div2D, works for both versions of the problem:Consider painting the array one element at a time, from left to right. After painting $a_i$ either white or black, one of the two subsequences $a^{(0)}$ or $a^{(1)}$ must have $a_i$ at its back. Since the only relevant properties of the subsequence are their last elements and total number of groups so far, we can almost solve the problem with a DP, where $dp[i][x]$ is the largest (smallest for B2) number of groups that can be achieved after coloring $a_1, \ldots, a_i$ such that the two elements at the end of the subsequences are $a_i$ and $x$. The DP transitions are not hard to figure out, but are a bit messy. This isn't quite enough to solve either problem, though, because the bounds are too large for an $O(n^2)$ DP to pass directly. But for all values of $i > 0$ and $x \neq a_{i-1}$, $dp[i][x] = dp[i-1][x] + \left\{\begin{array}{cl} 0 & \text{, if } a_{i-1} = a_i \\ 1 & \text{, if } a_{i-1} \neq a_i \end{array}\right\},$...and by keeping only the most recent row of $dp$, and storing it as a segment tree, all $n$ transitions of this type for a given value of $i$ can be performed in $O(\log n)$ with a single lazy range-increment. The value of $dp[i][a_{i-1}]$ can be calculated using a few range-max queries (range-min in B2), also in $O(\log n)$ time. This leads to a total time complexity of $O(n \log n)$.For ugly nearly-identical implementations, compare 106829611 with 106850293.
•  » » 7 months ago, # ^ | ← Rev. 2 →   +43 I do solved Div1B1 also using DP but with a little trick.106809164My DP was $O(N^3)$ dp[i][last value painted white][last value painted black]. Which is TLE/MLE obviously.I had to reduce it so I renumerate the array a with numbers 1,2,3,4.If an element is different from the last three I renumerate it with a value not in the set of new values of the last three elements.Else I renumerate it with the same new value of the one that match it in the last three.Then I run my O(N*4*4) DP and get the answer .I don't know if my idea is correct or the system test are weak. But I passed system test (^_^). Anyway my delta is -13 and I get back to expert(-_-).
•  » » » 7 months ago, # ^ |   +8 Any idea why your solution does not work for B2? BTW, I really liked your solution. Mine was...........quite nasty.
•  » » » » 7 months ago, # ^ |   +3 check this testcase-n = 11array a = 2 3 10 3 3 8 9 2 11 10 3array b would now be = 1 2 3 2 2 1 3 4 2 1 3so when we perform dp on this new array for example the 1 at index 5 can get merged with 1 at index 0 which is not originally possible for array a and the result will be less than original answer
•  » » 7 months ago, # ^ | ← Rev. 2 →   +5 Also, this idea can be implemented in $O(n)$ without a segment tree, consider the changes to dp array, you will add 1 to each but one element, or change only one element, so you'll need a variable that stores a lazy value, the dp array, and the minimum dp (or maximum), see my D1B2 code for further understanding.
•  » » » 7 months ago, # ^ |   0 Can you please elaborate your solution and approach?
•  » » » » 7 months ago, # ^ |   +3 As i said, my idea is the same as the one explained here, for the implementation I used the Venice Technique, you can find more information about this in this tutorial.
•  » » » » » 7 months ago, # ^ |   0 Hey! Thank you for providing the tutorial for the technique.In the original solution it is mentioned "The value of dp[i][ai−1] can be calculated using a few range-max queries"?I understand the transition of dp[i][x], can you explain how are we calculating dp[i][ai-1] perhaps?
•  » » 4 months ago, # ^ |   0 Could you please explain what you meant by storing the dp array as segment tree? I am new qto this approach, it'll be great help. Thanks
 » 7 months ago, # |   0 Posted editorial so fast.. WOW!!!
 » 7 months ago, # |   0 I don't know why the solution of Div 2 C works, can anyone explains it to me?
 » 7 months ago, # |   0 Can anyone give a test-case for which my code fails (Div2 B)?
•  » » 7 months ago, # ^ |   +5 "In each fight, the hero can select an arbitrary living monster and fight with it." You can check this. 10 10 2 11 5 5 5 The Answer will be "YES" if he fight with the second monster first and then the first monster.
•  » » » 7 months ago, # ^ |   0 Thats what i was looking for, without that i got wrong answer on pretest 2, sob sob..
 » 7 months ago, # |   0 I liked the problemsetEspecially div2 C, it increased my understanding of binary search.I loved solving div2 C.
•  » » 7 months ago, # ^ |   0 Hi, could you please help me with this
•  » » » 7 months ago, # ^ |   0 Your program stops for all cases where the array is a[i]=i (1-based) without outputting any "! x" prompt. You need to output variable "hi" after the binary search if you are unlucky enough.
•  » » » » 7 months ago, # ^ |   0 Ahh, I got it now, thank you!! In general though, I'm not able to understand why sometimes, the range is fixed as [l mid] [mid r] or at other times like: [l mid] [mid+1 r] or like how I'd mentioned earlier (I've tried variants earlier and realised they either get a WA or TLE). Are there are generalisations to binary search? Could you also clarify that/ suggest any resources where they've explained this?
•  » » » » » 7 months ago, # ^ |   0 It depends if you round down or up when getting the "mid" value. If you round down, you need to have [l mid][mid+1 r] (For example range [2,3] and you round down to mid=2, [2,2] and [3,3]) but if you do [l mid-1][mid r] you either get a case where r
•  » » » » » » 7 months ago, # ^ |   0 Ahh! All the while I was only thinking that we take the range as [l, mid-1] because we don't require the mid value (if eg, mid > x) and likewise for eliminating the unnecessary mid value in the higher end, the range is made [mid + 1, r]. I now understand that it's also about maintaining proper values in the boundary. How exactly to round down though? Or is it recommended to round up? One more query... how to find when to round up/down.
•  » » » » » » » 7 months ago, # ^ |   0 C++ automatically rounds down when there is a decimal if the data type is int. There is no difference to round up or down in time complexity or ability to find the target, you just need to change the ranges. Therefore, you can choose to round up or down in any case
•  » » » » » » » » 7 months ago, # ^ | ← Rev. 3 →   0 Thanks again! UPD: For others who still didn't get the logic about rounding down/up, I'd recommend giving this a read
•  » » » » 7 months ago, # ^ | ← Rev. 2 →   0 Please help me to find bug in my code it's failing at test case 21div2 C106868099UPDATE: GOT IT, I was printing '?' instead of '!' at one place
 » 7 months ago, # | ← Rev. 2 →   0 I'm unable to ask question in the contest problems section, it doesn't let me do so, when I click "send" button nothing happens, can anyone please help me with this. I want to ask a question as the solution that I submitted for 2B problem got tle on test#12, but when I resubmitted it (after modification of constraints), it got accepted so I want coordinators to please look into it.TLE submission: 106816040Accepted one(with exact same code): 106847496
 » 7 months ago, # |   0 106841211 why does my submission for div2 D1/div1 B1 fail ?
 » 7 months ago, # | ← Rev. 3 →   0 I am not asking if my binary search is correct because I sort of just believed the pretest would sort it out for me. But I think its impossible my loop breaks without having found the answer. It said my answer was wrong instead of query limit exceeded. So it must have broke but it wasnt the answer?https://codeforces.com/contest/1480/submission/106784965
•  » » 7 months ago, # ^ |   0 You are comparing the query responses as strings rather than as ints.
•  » » » 7 months ago, # ^ |   0 ooh. Thanks!
 » 7 months ago, # |   +18 I know a solution for div1D that is not randomised. I know that it's correct but I can't make it fit the TL a little bit. It works 6.1 seconds on codeforces. Let cnt[i][j] = s(v, 0, j) mod 2. This array takes O(n^2) memory so we have to make it smaller. We can do this using persistent segment trees and dfs. Now we can calculate cnt in O(n log n) time and memory. How to answer queries using cnt? The answer is any non zero number in (cnt[u] ^ cnt[v] ^ [1 if k == a[lca(u, v)] else 0 for k in range(n)])[l..r] Let's change a[lca(u, v)]th bit in cnt[u], then we need to find any different bits in 2 isomorphic segment trees from l to r. That can easily be done using perfect hashing on subtrees of segment trees. Sorry for my English. If you have any questions feel free to ask.
•  » » 7 months ago, # ^ |   +10 not randomisedhashing Choose one.
•  » » » 7 months ago, # ^ |   +20 You can do non-randomized perfect hashing on binary trees. Suppose that we have only 0 and 1 as values at leafs. This values will be leaf vertices’ hash. Every other vertex has two subtrees. If you don’t know the hash of some tree you calculate hash of left subtree, then of right subtree, then look up at some map: hash[{left_hash, right_hash}]. If the map has no such key you set it’s value to counter++, which is set to 2 in the beginning. Otherwise, you already know the hash. So my solution is still not randomized.
•  » » » » 7 months ago, # ^ | ← Rev. 2 →   +13 Hey, I also have a deterministic $O((N+Q)\cdot \sqrt{N})$ solution, it passes in 3 seconds on codeforces. For the queries on a path, you can use Mo's algorithm on trees. Then when we do Mo's algorithm, we keep track of the evenness/oddness (0/1) of all the minerals. On top of that we keep for each block of $\sqrt{N}$ minerals the sum of the minerals' oddness values. We can update this structure in $O(1)$ and check if there is an odd mineral in a range in $O(\sqrt{N})$. We update many times, but we query only Q times. This makes the above time complexity.Edit: I just saw that mohammedehab2002 had exactly the same idea...
•  » » » » 7 months ago, # ^ |   +3 So you either use an unordered_map which is randomized, or usual map, which adds extra log, so good luck fitting that into TL.
•  » » » » » 7 months ago, # ^ |   +36 Even though unordered_map is randomized, it still has some merit as "better randomized" because it turns the algorithm from Monte Carlo (could be wrong) to Las Vegas (only runtime is randomized). Also, I think the existence of a deterministic dictionary is still open, so we can hold out hope.
•  » » » » » » 7 months ago, # ^ |   -20 Only runtime is randomised, so it's not $O((N+Q) \log)$.
•  » » 7 months ago, # ^ |   +8 Optimized AC solution: 106873608. The lesson here is probably not to use std::unordered_map for anything, ever (except maybe strings), because holy crap it's slow. Use __gnu_pbds::gp_hash_table or __gnu_pbds::cc_hash_table instead.
•  » » » 7 months ago, # ^ |   0 I had a few problems where I tried to use gp_hash_table to speed up my solution but it didn't help at all. It only slowed it down. Also strings are not hashable by default so you can't use unordered_map for them.
•  » » » » 7 months ago, # ^ |   0 Also strings are not hashable by default so you can't use unordered_map for them. The following seems to be working for me (for example): ... unordered_map occ; occ["abcd"] = 1; ... So I don't understand what you mean by that statement; maybe you were referring to something else?
•  » » » » » 7 months ago, # ^ |   0 Oh, I thought strings can't be used that way like vectors and pairs. That's pretty cool actually.
 » 7 months ago, # |   0 How to prove Div1A/Div2C mathematically? I mean how can we prove that there exists a local minima in the left side of the array if $a_{mid} < a_{mid + 1}$?
•  » » 7 months ago, # ^ | ← Rev. 6 →   0 Consider the current mid $m$, if $a[m] > a[m-1]$ then the values in the left side (a[m-1] , a[m-2] , ...) must be decreasing untill some index $idx$ then increasing, then it will be guarnteed that a[idx-1] > a[idx] and a[idx] < a[idx+1].You can proof the right side in the same way.
•  » » 7 months ago, # ^ |   0 Apply Rolle's Theorem
 » 7 months ago, # |   +1 In Div2B, my Submission with the condition max(H(k)) >= 0 works. But I believe the correct condition is strictly greater than zero as is mentioned in the editorial. Is this hackable or am I missing something?
•  » » 7 months ago, # ^ |   0 Yes it should be strictly greater than zerotry this case: 1 5 10 1 10 10 output :No
 » 7 months ago, # | ← Rev. 4 →   0 Hello, Can anyone tell me why my solution to Div2 problem B got wrong answer on test 2? I tried alot, but couldn't find the mistake.
•  » » 7 months ago, # ^ |   0 I guess you have a similar mistake that is described in this comment
•  » » » 7 months ago, # ^ |   0 There's a problem with the comment link that you've attached. It shows me "forbidden"
•  » » » » 7 months ago, # ^ |   0 Oh, this is a link on mirror of cf, try that
•  » » » » » 7 months ago, # ^ | ← Rev. 2 →   0 Yes, this's the point Thank you so much
 » 7 months ago, # |   +96 Tester here. I have another solution for 1D using MO's algorithm on trees. If you don't know what this algorithm is about, it flattens a tree so that for each path, there's an interval (or maybe a union of $2$ intervals) in the flattened array such that the nodes in the path occur exactly once in it, and the rest of the nodes occur $0$ or $2$ times. And then you use the normal MO's algorithm on the flattened array. Tbh, I thought this problem was custom made for this algorithm, but apparently I was wrong.So in MO's algorithm, we extend or shrink an interval, and then we update the value on the boundary. Here, we'll flip the parity of the number of occurrences of $c_u$, where $u$ is the node on the boundary, and then we want any color that occurs an odd number of times in an interval. So the problem turns into an update-query problem on a binary array which says: update: flip an index in the array. query: find any $1$ in a range. Now, this is easy with segment trees, but the complexity will be $O(q\sqrt{q}log(q))$. However, notice that the number of updates is way bigger than the number of queries. You do $O(q\sqrt{q})$ updates, but you only do $O(q)$ queries, so we can instead try to do the updates quickly, on the expense of the queries.The idea is to use sqrt decomposition instead. Divide the array into blocks of size $\sqrt{q}$, each maintaining the sum of the elements in its range. Now, you can do the updates in $O(1)$, but the queries will take $O(\sqrt{q})$.Code
 » 7 months ago, # |   0 Can anyone help me? Why are these two solutions different?(first, second). Same idea, but different verdict.
 » 7 months ago, # |   0 Can someone explain the last line in the Greedy Strategy 1 under the intuitive proof of Div2 D1. It says, "Suppose $b$ results in the two subarrays $s′xzs′′$ and $t′yt′′$, while there is indeed another optimal assignment that agrees with our strategy and results in $s′xt′′$ and $t′yzs′′$ ".I don't understand how did our strategy result in $s′xt′′$ and $t′yzs′′$ ", why are $s′′$ and $t′′$ interchanged and why is this also considered optimal?
•  » » 7 months ago, # ^ |   0 have you figured it out? Can you tell me?
•  » » » 7 months ago, # ^ |   0 Lol no I haven't figured it out yet, no one replied, so I'm still in the same doubt.
•  » » » » 7 months ago, # ^ | ← Rev. 2 →   +3 You have to see the difference that it creates. With greedy strategy we have $s'xt"$ $t'yzs"$ let's say answer for greedy strategy is $ans_{greedy}$ And as for optimal sequence $b$ we have $s'xzs"$ $t'yt"$ let's say answer for optimal sequence is $ans_{optimal}$ Now, $t'yzs"$ will have one more contribution in the answer than $s'xzs"$ (x==z). And till now we have $ans_{greedy}$=$ans_{optimal} + 1$ And now in the worst case, $t'yt"$ will have one more contribution than $s'xt"$ (worst case is when $t"=xt_1$ i.e. $t"$ start with $x$). And now for the worst case we can have $ans_{greedy}$=$ans_{optimal}$. So, we have shown that our answer with greedy strategy is not worse than optimal sequence. Tell me if I am wrong
•  » » » » » 7 months ago, # ^ |   0 Yeah I understand what you're saying, but my main doubt still remains, why is the answer for the optimal strategy $s′xzs′′$ and $t′yt′′$? I don't understand what is it in the optimal answer that leads to the exchange of $s′′$ and $t′′$ from the greedy answer. According to me, the answer for the optimal answer should be written in the form $s′xzu$ and $t′yv$ where $u$ and $v$ are arbitrary sequences which are not related in any way to $s′′$ and $t′′$.
•  » » » » » » 6 months ago, # ^ | ← Rev. 2 →   0 Editorial is using exchange arguments here. The point is, you're trying to decide whether some decision ( like, where to place $z$ in case $x=z$ ) is not worse than the optimal one.So, now you say, let's suppose the optimal answer contains criteria other than what our strategy tells us, that is, the optimal answer has form $s'xzs^{"}$ and $t'yt^{"}$, where $x=z$ and $y \neq z$. Now, this is against our strategy, so we show that if we had also placed $z$ according to our strategy, we could have made a possible assignment that would not be worse than the optimal. Our assignment would say $s'x$ and $t'yz$ and then we have to place the remaining elements, but using a generic $u$ and $v$ like you said, you can't compare it to the optimal assignment in question, so we consider 2 assignments specifically ( keeping the internal result of $seg(s^{"})$ and $seg(t^{"})$ constant ). (Assuming first characters of $s^{"},t^{"}$ as $S,T$ respectively ) Assignment 1$s'xs^{"}$ and $t'yzt^{"}$Here, optimal has $[y \neq T]$, whereas our assignment has $[y \neq z] + [z \neq T]$, since we know that $y \neq z$, we have $1 + [z \neq T] \ge [y \neq T]$. Assignment 2$s'xt^{"}$ and $t'yzs^{"}$Here, optimal has $[y \neq T]$, whereas we have $[x \neq T] + [y \neq z] = [z \neq T] + 1 \ge [y \neq T]$So, both assignments show that our strategy is not worse than optimal. Also, the editorial just happens to mention one, but any placement of $s^{"}$ and $t^{"}$ turns out to work.
•  » » » » » » » 6 months ago, # ^ |   0 Yeah now I understand, thank you. They should include this in the editorial that would be really helpful. Now that you explain it, it seems so obvious, dunno what I was thinking. Nevertheless, thanks a lot!
 » 7 months ago, # | ← Rev. 2 →   0 liouzhou_101 doesn't look like the Contest Materials have been updated with the link to this editorial post — just FYI.Thanks for the great contest! Really enjoyed the problems :D
 » 7 months ago, # |   +3 i wasted all my time on problem B div. 2 because in the contest it told me that my solution had not passed the pretests, and now I see that my solution has been accepted, ok ....
 » 7 months ago, # |   +3 I became red in the round and I'm so happy!!!But I have to say I didn't like D very much — its Mo's algorithm on tree solution require not much thinking but the limits were quite tight. My first solution ran for 4960ms and I was afraid that it would fail system tests so I resubmitted after optimizing constant factors (making me rank 70 -> 150) but it turned out that the pretests were just all system tests.
 » 7 months ago, # | ← Rev. 4 →   +1 I have an alternative $O(n)$ greedy solution for Div2D12/Div1B12, which is different from editorial and is pretty short, but I am still trying to prove that.Div2D1/Div1B1: 106865184Div2D2/Div1B2: 106845535The preprocessing is combining the same neighboring elements and store it as {$val, len$} in first problem and {$val$} in second problem. We call this new array as $b$.The basic idea for both questions is that, we want to greedily choose better result when we process current element $b[i]$ (need proof).Besides, when we process $b[i]$, we know $b[i-1] \neq b[i]$ in our preprocessing. $b[i-1]$ is the last element in one color, so for another color we want to see what potential elements we can choose. We will maintain a set $alter$ to record potential available elements. We want to choose a different element in first problem and a same element in second problem.The elements in $alter$ can be placed in same or different color with $b[i-1]$. We can reorder to place any element in $alter$ to the end of another color. For example, if we have $b[i-1]=3$ and $alter=[1, 2, 4]$, then we can make $1$ as last element of one color by reordering two colors like: $[..., 2, ..., 4, ..., 3]$ and $[..., 1]$.For first problem: when $len \geq 2$ for some $b[i]$, then we will distribute it to both colors (need proof). When $len = 1$ for some $b[i]$, we need to decide which color to place it. We know that $b[i-1] \neq b[i]$, so we want to check can we find an element in another color that is different from $b[i]$, so we check $alter$. If so, it means that we can place $b[i]$ in either color, so $b[i-1]$ is in same color or different color with $b[i]$, so we can place $b[i]$ into $alter$. If not, it means that $b[i-1]$ must be placed before $b[i]$, so $b[i-1]$ is fixed.Second problem has the same idea and even simpler. We just need to check whether $b[i]$ in $alter$ and update $alter$.
•  » » 7 months ago, # ^ | ← Rev. 2 →   0 Can you please check my code and tell me the error in my logic for Div2 D1 :/ https://codeforces.com/contest/1480/submission/107013163
 » 7 months ago, # |   0 Whose solution for problem D yesterday did not use long long and WA on pretest #2？Because of this，I waste almost 40min ……
 » 7 months ago, # |   +23 Did anyone else solve div1B2 with min cost max flow?
 » 7 months ago, # |   -7 The data of Div1.D is not strong enough cause my solution with complexity $O(n\sqrt{q})$ can pass.Link of my solution -> https://codeforces.com/contest/1479/submission/106839336
•  » » 7 months ago, # ^ |   0 Why "not enough"? With 5s I think sqrt is one of the expected solutions. For example: https://codeforces.com/contest/1479/submission/106913527 this is mohammedehab2002's code with the same complexity and it's barely slower than 2s.
 » 7 months ago, # | ← Rev. 2 →   0 Hello, could anyone help me with my Div2.C? I used the ideas from gfg after contest but I still get the wrong answer on test 11.Thank you!My submission-> https://codeforces.com/contest/1479/submission/106868187
 » 7 months ago, # |   +3 thanks for all. But editorial could be better. You could explain better.
 » 7 months ago, # |   0 Can anyone point out the error in this Div 2C sol ? LINK
•  » » 7 months ago, # ^ |   0 if(val_l < val && val > val_r) { cout << "! " << m << '\n'; break; }Your condition is wrong it asked for minima.
•  » » » 7 months ago, # ^ |   0 Thanks!
 » 7 months ago, # |   0 This contest should be fairly unrated, many have lost interest in giving CF contest after all this, How can someone change the constrains after contest clear violation of rules, if that problem was hacked during contest, that guy might have wasted a lot of time in finding the solution. If so,Also change the constrains of other problems as well so that it becomes fair for other people. Better please make a form, make rated for only those who want. It's totally unfair.
 » 7 months ago, # |   0 Hey, Can anyone tell me where I am going wrong with problem B(div-2)? I believe that I have applied the same logic as in the editorial. I have created a map with ascending order of attack of monsters. Then each time I check if the hero is alive before the last encounter with that monster, If yes then I increase the count of the number of monsters killed. Here's my submission- https://codeforces.com/contest/1480/submission/106872975 I would be grateful for any help.
•  » » 7 months ago, # ^ |   0 i guess we should be checking for each i if that happens to be the last encounter would the hero be alive
•  » » » 7 months ago, # ^ |   0 Well, that's what I did in the code but can't figure out why it still doesn't work. Thanks anyway!
•  » » » » 7 months ago, # ^ |   0 what if monsters have the same attacking power. both of them will get stored to the same key and therefore ur algo wont account for it
•  » » » » » 7 months ago, # ^ |   0 I see, thanks a lot!
 » 7 months ago, # |   0 can somebody tell why my solution fail for problem 1479B1?https://codeforces.com/contest/1480/submission/106875875
•  » » 7 months ago, # ^ |   0 in case:62 2 1 3 2 2The answer is 6 but your output is 5
 » 7 months ago, # |   0 Can anyone find out the error in my submission in DIV2D2 ? https://codeforces.com/problemset/submission/1479/106881116 THANK YOU!
•  » » 7 months ago, # ^ |   0 I have already understand my error in the problem D2,When we use the vector or other data sturctures to solve this problem,We should update the Nxt[i](It's that the next a[i]'s position) when we push or merge to number ,such as this:[1,1],when we make them both are color 0,we should update the Nxt[color0[color0.size()-1]].If you have this error,you will be Wrong Answer in test 6.
 » 7 months ago, # |   0 Problem (A + B) Video tutorial : https://www.youtube.com/watch?v=haTHbtcWYKM
 » 7 months ago, # |   0 Why my solution for questions 2 is wrong? https://codeforces.com/contest/1480/submission/106885213
 » 7 months ago, # |   0 Div1A/Div2CAfter Learning L02 — Peak Finding, I write this code submission 106878273 but get WA on test 22.Can anyone give me a hand?
•  » » 7 months ago, # ^ | ← Rev. 2 →   +3 Try for: 6 5 4 3 2 1a[n + 1] should be inf.
•  » » » 7 months ago, # ^ | ← Rev. 2 →   0 Oh! This little bug.My mistake a[0] = a[n] = INF, it should be a[0] = a[n + 1] = INF.Thanks a lot.
 » 7 months ago, # | ← Rev. 2 →   +3 For Div2 C, My submission got TLE on 7th pretest. I had the same intuition and implemented as given in tutorial. If someone can find out the mistake, it will be a great help. Thanks in advance.Submission Link : 106890877
•  » » 7 months ago, # ^ |   0 You are not changing the values of left and right for the case when curr > left && curr > right.
•  » » » 7 months ago, # ^ |   +3 Oh Yes! I checked. Just If I had put a simple else it would have got AC. Thanks a lot dude for your time. Really appreciate :)
 » 7 months ago, # |   0 Problem authors please next time google your problem or select testers for it
 » 7 months ago, # |   0 IN the great hero problem , the tutorial provided says that the sum should be from 1 to n in the equation of hk instead it should be 1 to n-1 . Anyone please let me know if I am wrong
 » 7 months ago, # |   0 problem:1479B2I think there is a typo in editorial, in line before lemma 1, f(i) = max (g(j)) should me min if I am not wrong.
 » 7 months ago, # |   +2 Best contest ever!
 » 7 months ago, # |   0 You can watch this https://youtu.be/sUFMuqQlL6M if you are stuck in C
 » 7 months ago, # | ← Rev. 2 →   0 I am facing some problems finding why my program is failing for test case 6 in Painting the Array I (Div2 — D1) problem. If anyone could point out what's going wrong, it would be great. Thanks in advance!!
•  » » 7 months ago, # ^ |   0 change this linereturn upper1 — occurences[num].begin(); ===> return *upper1
•  » » » 7 months ago, # ^ |   0 Oh yes, a careless mistake! Thanks for your help!
•  » » 7 months ago, # ^ |   0 Hi. Thanks for sharing your solution. It is very understandable.
•  » » » 7 months ago, # ^ |   0 No problem. Glad it helped!
 » 7 months ago, # |   0 Can anyone help, in which test-case is my code failing? Thanks. My submission : https://codeforces.com/contest/1480/submission/106783197
 » 7 months ago, # | ← Rev. 4 →   +1 I have another explanation (or solution) for Div1B1/Div2D1. Sorry I'm not very good at English, you can just read my code(106872452).First, let $a^{(0)} = a$(all elements in a) and $a^{(1)} = []$(empty). Let's move some elements from $a^{(0)}$ to $a^{(1)}$. If a segment in $a^{(0)}$ has two or more elements, then we can move one element in this segment to $a^{(1)}$. After that, $\mathit{seg}(a^{(0)})$ will not decrease and $\mathit{seg}(a^{(1)})$ will increase or stay unchanged. For example, If $a^{(0)} = [1,1,2,3,4,4]$, after such operations, $a{(0)}$ became $[1,2,3,4]$ and $a^{(1)}$ became $[1,4]$. Let answer = $\mathit{seg}(a^{(0)})+\mathit{seg}(a^{(1)})$.But that's not enough. Consider a case $a = [1,1,2,3,1,1]$. We can construct $a^{(0)} = [1,2,3,1], a^{(1)} = [1,1]$ using the method above. But we can move $2$ in $a^{(0)}$ to $a^{(1)}$, decreasing $\mathit{seg}(a^{(0)})$ by $1$ and increasing $\mathit{seg}(a^{(1)})$ by $2$. So we should perform another type of operation. If there exists $a_i$ between two segments($seg_x$ and $seg_y$), and all elements in $seg_x$ and $seg_y$ are equal to one value $v$, and $a_i \neq a_{i-1}, a_i \neq a_{i+1}, a_{i-1} \neq a_{i+1}, a_i \neq v$, then we should increase answer by $1$, because we can move $a_i$ from $a^{(0)}$ to $a^{(1)}$. ExamplesCase 1: a = [1, 1, 2, 3, 4, 4] Step 1: a0 = [ 1, 2, 3, 4] a1 = [1, 4 ] ans = 6 Step 2: We cannot perform other operations to increase answer. Case 2: a = [1, 1, 2, 3, 1, 1] Step 1: a0 = [ 1, 2, 3, 1] a1 = [1, 1 ] ans = 5 Step 2: move '2' from a0 to a1 (or move '3' from a0 to a1). a0 = [ 1, 3, 1] a1 = [1, 2, 1 ] Seg0 -= 1, Seg1 += 2, ans += 1 ans = 6 Case 3: a = [1, 1, 2, 1, 2 ,1, 1] Step 1: a0 = [ 1, 2, 1, 2, 1] a1 = [1, 1 ] ans = 6 Step 2: We cannot perform other operations. If we move '2' from a0 to a1, then Seg0 -= 2, Seg1 += 2, ans will not change. 
•  » » 7 months ago, # ^ |   0 Can you explain it again I didn't get that
•  » » » 7 months ago, # ^ |   0 I added some examples to explain it.
•  » » 7 months ago, # ^ |   +3 I used same method but instead of checking this much inequalities,if we have A[i]!=A[i+1] && A[i]!=v&&A[i+1]!=v because if this is true then we can simply break sequence here only. And this condition is enough because only structure of example which don't follow this looks like 1 1 5 1 2 1 2 1 3 1 1, Here we can see no a[i]!=v && a[i+1]!=v simultaneous.(v) is 1 here. In this case answer will increase only by 1 always otherwise always by 2 if we break sequence at i and i+1. For example [1 1] 5 1 2 (4 2) 1 3 [1 1] sequence a can be like 1 5 1 2 4 1and sequence b be like 1 2 1 3 1.
•  » » » 7 months ago, # ^ |   0 My submission link for D1 div2:https://codeforces.com/contest/1480/submission/106939726
 » 7 months ago, # | ← Rev. 2 →   0 1000 1000 4 200 300 500 400 1000 1000 1000 1000 For a testcase like this for problem B, the answer should be "NO" since the hero dies after the 3rd round. However, the solution given in the editorial gives us "YES".This is confusing. Am I missing something?
•  » » 7 months ago, # ^ |   0 The hero can choose the order.
•  » » » 7 months ago, # ^ |   0 Ah I see thanks
 » 7 months ago, # | ← Rev. 2 →   +12 Explain this please Corner case that is inside the new limits removed.. Problem D2B This was Test #23 earlier 1 3 10 1 2 16 liouzhou_101 MikeMirzayanov
•  » » 7 months ago, # ^ |   -26 Many solutions that are now accepted failed on this test case.. I know tagging random users is dumb but you guys are active in the community so tagging you all.-is-this-fft- galen_colin 1-gon AnandOza
 » 7 months ago, # |   +13 In the editorial of D, what does "consistent segment tree" mean? Is it persistent segment tree?
•  » » 7 months ago, # ^ |   0 Yes
 » 7 months ago, # |   0 in Div2 C how come we sure that when l==r that is minimum?
•  » » 7 months ago, # ^ |   0 We are not required to find the global minimum, just a local minimum which is defined as — a[i] < min(a[i-1], a[i+1]) — or equivalently — a[i] < a[i-1] and a[i] < a[i+1]. Notice that before and after every step of binary search the range [l,r] satisfies the condition: — a[l-1] > a[l] and a[r] < a[r+1].Hence when l==r we obtain a local minimum
 » 7 months ago, # |   +8 Div1 C reminds me of this problem on AtCoder.
 » 7 months ago, # |   0 In Div2.D1 I submitted this code and got AC. But in fact it's quite different from the tutorial! Can anyone hack it or prove it right? Thanks!PS: I had run thousands of testcases on my computer with n<=20, and it is always right.Sorry for my bad English :(
 » 7 months ago, # |   +6 Super short solutions for Div1.B:
•  » » 7 months ago, # ^ |   0 can you explain it please?
•  » » » 7 months ago, # ^ | ← Rev. 2 →   +9 I will describe the full solution for B1 that I came up during the contest and simplify it.Let $dp[s][i-1] = (v_{s,i-1}, k)$ be the state of current solution when $a[i-1]$ is added to the sequence $s$ ($s \in \lbrace 0,1 \rbrace$), in which $v_{s,i}$ is the best score ending at $i-1$ and $k$ is the index of the last item of the other sequence $s' = 1-s$ (of course, $k < i-1$ and $k = 0$ when $s'$ is empty as I read the input into an 1-indexed array). Let's focus on $s = 0$. When reaching item at index $i$, we have two options:1.1 Adding $a[i]$ to the sequence $0$: we update $dp[0][i] = (v_{0,i-1} + [a[i] \neq a[i-1]], k)$1.2 Adding $a[i]$ to the sequence $1$: we update $dp[1][i] = (v_{0,i-1} + [a[i] \neq a[k]], i-1)$ as now $a[i]$ is appended to sequence $1$ that is ending with $a[k]$ .Similarly for $s = 1$, we have two updates:2.1 $dp[1][i] = (v_{1,i-1} + [a[i] \neq a[i-1]], k)$2.2 $dp[0][i] = (v_{1,i-1} + [a[i] \neq a[k]], i-1)$ So, $dp[0][i]$ can be updated by one of two ways 1.1 and 2.2. Of course, we choose the one giving the better score, so $dp[0][i] = max((v_{0,i-1} + [a[i] \neq a[i-1]], k), (v_{1,i-1} + [a[i] \neq a[k]], i-1))$ (1)In 1.2, there one important point is that there can be many values $k$ that yield the same best $v_{0,i-1}$. In this case, $a[i] \neq a[k]$ is always true as we are always able to chose one $k$ that $a[i] \neq a[k]$. The trick I did is, as the input array is 1-indexed, and $a[0] = 0$, when updating $dp[0][i]$ by formula (1), if two scores are equal and $k \neq i-1$, I set $k = 0$ , so $a[i] \neq a[k]$ is always true for subsequent steps. SimplificationThere are two simplifications to make the code shorter: As the role of $s = 0$ and $s = 1$ are the same, we can remove the first dimension of $dp$ and only need to handle $dp[i]$. As we only need $dp[i-1]$ and $dp[i]$, $dp$ is reduced to an 2-element array, i.e. $dp[2]$. The idea for B2 is similar.
•  » » » » 7 months ago, # ^ |   0 Thank you!
 » 7 months ago, # |   0 Can someone explain Div2/ D2 problem?
•  » » 7 months ago, # ^ |   0 I solved it the following way. First of all, i merged every contiguous segment of equal elements into one (since every segment of the form $[5, 5, 5, 5]$ will always belong to either $a0$ or $a1$). Then let $dp[i]$ be the minimum total number of segments up to position $i$. For each element $a[i]$, we either append it in the same set of the previous element $a[i-1]$, so we get $dp[i] = dp[i-1] + 1$ or we try to append it to the previous occurrence of this value (if there is any), therefore having : $dp[i] = dp[lst[a[i]+1] + i -lst[a[i]] - 2$ ($lst[a[i]]$ is the index of the last occurrence of this value in our array), because we need to put all elements between two equal numbers in a different set. Finally, the transition for each $i$ is: $dp[i] = min( dp[lst[a[i]+1] + i -lst[a[i]] - 2, dp[i-1] + 1)$.Solution code : https://codeforces.com/contest/1480/submission/106923311.I hope i made myself clear.
•  » » » 7 months ago, # ^ | ← Rev. 2 →   0 Thanks a lot man !!!!
 » 7 months ago, # |   0 Can anyone please explain why I'm getting WA in div2 D2 :( 106923096
 » 7 months ago, # |   0 in problem B div 2 I tried to find the monster that ll deal the maximum damage among all rather than maximum attack. Why is this approach wrong I am not able to figure out? Can anyone please help? SUB: https://codeforces.com/contest/1480/submission/106864190
•  » » 7 months ago, # ^ | ← Rev. 3 →   0 same problem. if you find a solution please share Did you make the monster giving the maximum damage as the last one. if thats the case, it might happen that multiple monsters may give the maximum damage so we have to check them all. for me this didnt work so instead of checking for only those monster giving the maximum damage i checked for all and it worked.i dont understand why. i guess the thinking that in th worst case its the monster giving the max damage that might cause the hero to lose is wrong heres the solution
 » 7 months ago, # | ← Rev. 2 →   0 Can help me to figure out why this code fails in tc 2 ?106927169
•  » » 7 months ago, # ^ | ← Rev. 2 →   0 This is simple to catch. You assumed that the order of monsters doesn't matter. But the order actually matter here. Take case:2 2 21 11 1000
•  » » » 7 months ago, # ^ | ← Rev. 2 →   0 can anyone please tell me what is wrong in this logic for div2 B. the last monster to kill will be the one which gives max damage to the hero. therefore health just before fighting that last monster be hr. if(ceil(hr/Ek)>=ceil(Hk/A)) hero wins. ceil(Hk/A) means the number of turns to kill the kth (the last one) monster. hr/Ek means the number of turns to kill hero. we check this over all last possible monsters(i.e. the one giving the max damage to hero)submission
 » 7 months ago, # |   +23 Could someone explain how you get $\mathcal{O}((n + q) \log n)$ in div 1 D?The way I see it, with the persistent segment tree solution, for a fixed path, you can check in $\mathcal{O}(\log n)$ time whether there is a working value in the range $[l, r]$. Don't you need to binary search for what that value actually is, thus taking $\mathcal{O}(\log^2 n)$ time?
•  » » 7 months ago, # ^ |   0 Additional binary search is not necessary. You can get what the value is through a binary search on segment tree.
 » 7 months ago, # |   0 can anyone please tell me what is wrong in this logic for div2 B. the last monster to kill will be the one which gives max damage to the hero. therefore health just before fighting that last monster be hr. if(ceil(hr/Ek)>=ceil(Hk/A)) hero wins. ceil(Hk/A) means the number of turns to kill the kth (the last one) monster. hr/Ek means the number of turns to kill hero. we check this over all last possible monsters(i.e. the one giving the max damage to hero) submission
 » 7 months ago, # |   0 The 20th input of test #2 for problem '1480B — The Great Hero' reads: 320995 -54033 3 783399 76765 77638 140538 647490 973129 That is, the hero is dead on arrival since B is negative. Yet the answer for the 20th token is YES. How can the hero start fighting when he is already dead? Shouldn't the answer be NO? I am sure I fail to grasp something, but it eludes where I am wrong.
•  » » 7 months ago, # ^ |   0 You got B = -54033 after you changed its value. Move your check to the beginning of program, or localize B variable.
 » 7 months ago, # | ← Rev. 2 →   0 Can anybody help me with this code (Qs2 Division-2)?? https://ide.geeksforgeeks.org/3BuSpr967RIt fails on test case 12
 » 7 months ago, # |   0 Thank you for very clean solution codes and pretty understandable tutorials!
 » 7 months ago, # | ← Rev. 2 →   0 Liked problem C. If anyone wants the reason that solution works - http://www.dsalgo.com/2013/02/index.php.html
 » 7 months ago, # |   0 "O(MO)" — One more alternative approach (or explanation) for Div.2 D1.Step 1. It is obvious that we can remove all excesses of consecutive equal elements from an initial array without influencing the result. The excess is when >2 equal elements come in a row. We then reduce to 2 elements.Now every second element would come to different array except of the pathological pattern (step 2).Step 2. We search for patterns /OO(MO)+O/. Here M stands for "not O" or for . (i.e. any element) because of reduction by step 1. The middle side O(MO)+ gives us one unsqueezable array, and concat('O','O') gives us another which is sqeezable by one (so it reduces an answer by one). Patterns may overlap by 2 elements.Answer is a number of elements in reduced array (after step 1) minus a number of patterns found (in step 2). $O(n)$
 » 7 months ago, # |   +18 Btw, 22 vertices is sufficient in div1C.
 » 7 months ago, # | ← Rev. 2 →   0 Can someone please check my code and tell me the error in my logic for Div2 D1:/ https://codeforces.com/contest/1480/submission/107013163
 » 7 months ago, # | ← Rev. 2 →   0 I wrote the following part to get random numbers. (Div.1 D) srand(time(NULL)); for(int i=1;i<=n;++i) for(int j=0;j<64;++j) X[i]=X[i]<<1|(rand()&1); It failed to pass test 7.After debugging for a really long time, I changed it into the following. srand(time(NULL)); for(int i=1;i<=n;++i) X[i]=1ull*rand()<<60|1ull*rand()<<45|1ull*rand()<<30|1ull*rand()<<15|1ull*rand(); Then it got AC but I haven't known why. Can someone please explain the reason that the first one failed but the second one passed? Thanks in advance.PS: You can have a look at the two submissions here and here.
 » 7 months ago, # |   0 How do you conclude D in $O(n \log n)$ time? I did basically what you have described but my final complexity is $O(n \log^2 n)$ and squeezing it into TL was pretty painful. Each of these values $f(1, u, l, r)$ that you mention I compute in $O(\log n)$ but in order to find desired $c$ I perform binary search on this interval which adds extra log. And tree that you describe is called persistent, not consistent. To be precise, in my tree "time" corresponds to colors, I have a root for every single segment tree corresponding to vertices with colors $\le r$ and in particular I compute $f(1, u, l, r)$ as $f(1, u, 1, r) \oplus f(1, u, 1, l - 1)$
•  » » 7 months ago, # ^ | ← Rev. 2 →   +5 Here's my $O(n \log n)$ solution:First notice $f(u,v,l,r) = f(1,u,l,r) \oplus f(1,v,l,r) \oplus f(lca(u,v),lca(u,v),l,r)$ (note that $f(lca(u,v),lca(u,v),l,r)$ is simply $X_{a_{lca(u,v)}}$ if $l \leq a_{lca(u,v)} \leq r$ and $0$ otherwise).Therefore it's enough to maintain a persistent segment tree for each vertex $u$ which answers queries $f(1,u,l,r)$, I'll denote its root as $ST_u$. We can get $ST_u$ from $ST_{parent(u)}$ by updating position $a_u$ with $X_{a_u}$.To answer a query for path $(u,v)$ of mineral resources in $[l,r]$, we can as usually split this into $O(\log n)$ ranges $[l_1,r_1],\dots,[l_k,r_k]$ which correspond to the segment tree nodes. Then notice that a range $[l_i,r_i]$ will contain the answer iff $f(1,u,l_i,r_i) \oplus f(1,v,l_i,r_i) \oplus f(lca(u,v),lca(u,v),l_i,r_i) \neq 0$. Therefore, while querying, when we're in some range, we can see whether the current range contains an answer without descending further. Then, to retrieve it, we only need to descend one of these $O(\log n)$ ranges (any one for which we know it contains the answer), adding $O(\log n)$ to the complexity (since at each step of the descent we know which subtree will contain the answer), and together it's still $O(\log n)$ per query. Turns out this is very easy to implement, we can always just check if an answer exists in the left subtree, if it does return it, otherwise try finding it in the right subtree of the current segment tree node. All we need for a query is $ST_u$, $ST_v$ and $lca(u,v)$. int query(Node *a,Node *b,int l,int r,int ql,int qr,int lc) { if(ql>qr) return -1; if((a->h^b->h^(l<=val[lc]&&val[lc]<=r?x[val[lc]]:0))==0) return -1; if(l==r) return l; int m=(l+r)/2; int res=query(a->l,b->l,l,m,ql,min(qr,m),lc); if(res!=-1) return res; return query(a->r,b->r,m+1,r,max(ql,m+1),qr,lc); } Full code: 107109427
•  » » » 7 months ago, # ^ |   +10 Oh wow, it makes perfect sense, thanks. The difference between your and mine approach is that I created persistent trees in a line by adding colors from left to right and each tree is over space of preorders, but your persistent trees create original tree since you are adding persistent tree for each vertex of a tree and each tree is over space of colors. I didn't think you could pull off tricks like that
 » 7 months ago, # |   0 In the case 2 of the intuitive proof of the div.2D, how do you guarantee that t1 must be following z when putting z after x according to your greedy strategy? what if next(z) > next(y)?
 » 7 months ago, # |   0 int n=s.nextInt(); int a[]=new int[n]; for(int i=0;i(),a2=new ArrayList<>(); //boolean c=true; for(int i=0;i
 » 7 months ago, # | ← Rev. 2 →   0 Thanks a lot for including such a detailed proofs!
 » 7 months ago, # | ← Rev. 2 →   0 Can you please tell me the meaning of this line in B1: Suppose b results in the two subarrays s′xzs′′t′yt′′, while there is indeed another optimal assignment that agrees with our strategy and results in s′xt′′t′yzs′′. Update: Got it.
 » 7 months ago, # |   0 is someone else also facing issues with test cases of D1
 » 7 months ago, # | ← Rev. 2 →   0 Can anyone explain their solution for Div1 B1/Div2 D1? It will be of great help _/\_ :)
 » 7 months ago, # | ← Rev. 2 →   0 Managed to solve ProblemD deterministically using (MO's on tree + sqrt decomp) to find first odd beteween l and r. Is not very hard solution 108831828. Is it intended to not pass, since it it $(N+M)sqrtN$. However I have to admit I quite like more the author's solution since it has high enough probability and is faster, and probability of success could be increased easily.
 » 5 months ago, # |   0 Help me in 1480B i am getting WA....please tell me where my logic failsthanks in advance//solution link:// bool solve() { int a,b,n,ans=0; cin>>a>>b>>n; int mnsta[n],mnstb[n]; for(int i=0;i>mnsta[i]; } for(int i=0;i>mnstb[i]; } for(int i=0;i0 && mnstb[i]>0) { b-=mnsta[i] ; mnstb[i]-=a ; } if(b<1) { ans=i; break; } ans=i; } return true;}
•  » » 5 months ago, # ^ |   0 i got where i am wrong ...but unable to remove above :(
•  » » » 5 months ago, # ^ |   0 Can you explain where you was wrong ?Here is my code => https://codeforces.com/blog/entry/87598?#comment-780738
»
5 months ago, # |
0

The Great Hero

# include

using namespace std;

int main(){ int t; cin>>t; while(t--){ int A,B,n; cin>>A>>B>>n; int att[n],heal[n]; for(int i=0;i<n;i++){ cin>>att[i]; } for(int i=0;i<n;i++){ cin>>heal[i]; }

for(int i=0;i<n;i++){
while( heal[i]>0 && B>0 ){
B=B-att[i];
heal[i]=heal[i]-A;
}
}

if(B>0){
cout<<"YES"<<endl;
}else{
if(heal[n-1]<=0){
cout<<"YES"<<endl;
}else{
cout<<"NO"<<endl;
}
}

}`

}

Can anyone point out why i am getting wrong ?

•  » » 5 months ago, # ^ | ← Rev. 2 →   0 @dy_123 look bro killing all the monster is important but more important is the order in which hero kills the monster Earlier I was too doing like u, but the catch here is that order matters.example;A:40B:30a1:50 b1:20a2: 25 b2: 20 kindly see why order matters from above example..please reply if u got it or not and upvote thanku.
•  » » » 5 months ago, # ^ |   0 thanks i got it.