### null_awe's blog

By null_awe, 6 days ago,

Thank you for participating! We put a lot of effort into this contest. Special thanks to TheScrasse for contributing to these problems.

Rating Predictions

Also, check out this video editorial for problems A through C2 by one of our testers! https://www.youtube.com/watch?v=hS8Z3k57f6Q

#### Solutions

##### 1984A - Strange Splitting

Problem Credits: buffering
Analysis: buffering

Hint 1
Hint 2
Solution
Code (C++)
##### 1984B - Large Addition

Problem Credits: flamestorm
Analysis: null_awe

Solution 1

Hint 1
Hint 2
Hint 3
Solution
Code (C++)
##### 1984C1 - Magnitude (Easy Version) and 1984C2 - Magnitude (Hard Version)

Problem Credits: buffering
Analysis: null_awe

Hint 1
Hint 2
Solution (Easy Version)
Solution (Hard Version)
Code (C++)

#### 1984D - ''a'' String Problem

Problem Credits: le0n
Analysis: null_awe

Hint 1
Solution
Code (C++)

#### 1984E - Shuffle

Problem Credits: null_awe, thanks to wavelets for helping with brainstorming
Analysis: null_awe

Solution
Code (C++)

#### 1984F - Reconstruction

Problem Credits: buffering
Analysis: buffering

Hint 1
Hint 2
Hint 3
Hint 4
Solution
Code (C++)

#### 1984G - Magic Trick II

Problem Credits: null_awe
Analysis: null_awe

Hint 1
Hint 2
Solution
Code (C++)

#### 1984H - Tower Capturing

Problem Credits: flamestorm
Analysis: flamestorm

Hint 1
Hint 2
Solution
Code (C++)
• +278

 » 5 days ago, # |   +20 Judge solutions are currently being posted. Please enjoy the analyses in the meantime.
•  » » 5 days ago, # ^ |   +3 .ComplaintFrame { display: inline-block; position: absolute; top: 0; right: -1.4em; } .ComplaintFrame a { text-decoration: none; color: #ff8c00; opacity: 0.5; } .ComplaintFrame a:hover { opacity: 1; } ._ComplaintFrame_popup p, ._ComplaintFrame_popup button { margin-top: 1rem; } ._ComplaintFrame_popup input[type=submit] { padding: 0.25rem 2rem; } ._ComplaintFrame_popup ul { margin-top: 1em !important; margin-bottom: 1em !important; } Thanks for the fast editorial and challenging contest!!
•  » » 5 days ago, # ^ |   +1 All judge solutions have been posted.
 » 5 days ago, # |   +4 What's MIS?
•  » » 5 days ago, # ^ |   +19 I was gonna ask the same question!
•  » » 5 days ago, # ^ |   +28 Maximum Independent Set ?
•  » » 5 days ago, # ^ | ← Rev. 2 →   +3 Maximum independent set (a set containing the maximal amount of vertices where no two are adjacent). The abbreviation is explained in the editorial now.
•  » » » 5 days ago, # ^ |   0 you are right
 » 5 days ago, # |   0 Why the codes not presented?
 » 5 days ago, # |   +10 E is nice
 » 5 days ago, # |   -20 very fast editorial! problems are also really interesting, thank you for the round
 » 5 days ago, # |   0 super fast editorial with super fast system testing !!
 » 5 days ago, # | ← Rev. 3 →   +93 F can be solved in $O(n \log n)$ time: consider the same DP, and sweep the sum over all possible values. All that changes when the sum changes are transitions PS (valid when B[i] + B[i+1] == sum) and transitions SP (valid when sum - 2*M <= B[i] + B[i+1] <= sum + 2*M). Thus, you can store the transition matrices of the DP in a segment tree and do a sliding window sweep over the sum.H can also be solved in $O(n \log n)$ time using fast Farthest-Point-Delaunay-Triangulation: the triangles we're allowed to pick are exactly those in the FP-Delaunay Triangulation. There are algorithms for this in linear-time after computing the convex hull.
 » 5 days ago, # | ← Rev. 2 →   +34 H is doable in $O(n \log n)$. It's a fun problem to solve in that time, but takes more effort for sure (but still definitely doable from scratch within contest time)
•  » » 4 days ago, # ^ |   0 Can you tell more details about the $O(n\log n)$ solution? I'm very curious about that.Thx
•  » » » 4 days ago, # ^ |   +10 I do not know where to find any description of FP triangulation, but it indeed relies on the correspondence between them. I want to find the partition of the plane into regions such that every region has one of the input points (which I assume form a convex polygon) as the furthest point (as points where three such regions meet are points determining a triangle whose circumcircle contains everything else). All of these regions are infinite and the only two infinite rays for regions $R_i$ are bisectors between consecutive pairs of points $(P_{i-1}, P_i)$ and $(P_i, P_{i+1})$. It is a good start to understand when a region consists of these two rays only — if I'm not mistaken, that's just a local check for intersections of these two and two neighboring bisectors. When you find such a pair then you can remove both of these bisectors from the set of "active bisectors" kept on a cyclic set and insert bisector between $(P_{i-1}, P_{i+1})$ and continue in a similar manner
•  » » » » 2 days ago, # ^ |   +14 Omg, I get it. It's so magical. Thank you.I think it works as this :We use a priority queue to maintain a set of radii of circumcircles formed by every set of three adjacent points. Each time we take out the one with the largest radius, it can be proven that this circle definitely covers all the points.I have come up with a way to prove it, and the general idea is as follows:First, we prove a lemma: The circumcircle with the largest radius can always be taken at three consecutive points on the convex hull.After proving this, we prove that the circumcircle with the largest radius definitely contains all points, which can be done using proof by contradiction.I apologize for my poor English; the above text was translated by AI.
•  » » » » 32 hours ago, # ^ |   0 265618123I make a submition. It's accepted.I think it's completily correct! Thank you!
•  » » » » » 32 hours ago, # ^ |   0 Nice, glad to hear that and congrats :)! I am actually not 100% sure about my own claim about local check for when I can commit a triple, but looking at it your way with the radius of the circumcircle certainly sounds convincing :)
•  » » 4 days ago, # ^ |   +10 Oh , I see it(Farthest-Point-Delaunay-Triangulation) in another comment. Thank you.
 » 5 days ago, # |   +8 What was problem E asking for. Was it saying you recursively are doing the step 1 and 2 until you can't anymore and that is considered as doing the shuffle exactly once. I know I'm not understanding because I don't know how they get 6 for example 4 in the sample test cases.
•  » » 5 days ago, # ^ |   +3 Same. I solved without doing it recursively and it was wrong, so I solved the sample case by drawing it then guessed the solution from it.
•  » » » 4 days ago, # ^ |   0 That's impressive
•  » » 5 days ago, # ^ | ← Rev. 2 →   +11 My understanding for example 4 in E:Choose 5 as root, change (5,8) to (5,1)change (1,8) to (1,7)change (1,10) to (1,6)and you have 6 leaves now (includes 5)
•  » » 4 days ago, # ^ | ← Rev. 2 →   0 Edit: Nvm!! I made a blunderI couldn't even get test case 2.My approach:Let's choose 5th node: 1->2->3->4(root 1),5(root 5)Then choose 4th node: 1->2->3(root 1), 4(root 4), 5(root 5)Then choose 3rd node: 1->2(root 1), 3(root 3), 4(root4), 5(root 5)Then choose 2nd node: ... Let's connect backroot 2 is connected to 1: 1->2root 3 is connected to 1: 1->2,1->3root 4 is connected to 1: 1->2,1->3,1->4root 5 is connected to 1: 1->2,1->3,1->4,1->5ans: 4correct me if I am wrong.
 » 5 days ago, # |   0 super fast editorial, thanks but i sleep now. Farewell!
 » 5 days ago, # |   +4 I solved D without Z-algo or hashing, with time complexity of $O(m \cdot sqrt(m))$ by only brute force. Don't know it is legal or not but it passed the system testing anyway with 93ms (pretty surprised).
•  » » 5 days ago, # ^ |   +4 Can you link your submission, so I can try to hack it?
•  » » » 5 days ago, # ^ |   0 Here is it: 264957961 (That account of mine has been locked commenting for 48 hours, that's why I use this account to comment. I know using multiple account is considered bad, but I didn't join any contest from this account for a long time to avoid this bad behaviour). If it is legal, I hope you could explain why this time complexity could pass.
•  » » » » 5 days ago, # ^ |   0 Can u explain ur approach ?
•  » » » » » 5 days ago, # ^ | ← Rev. 6 →   +2 Store all indices such that $s_i \neq 'a'$. Let the number of such indices be $m$ and the vector store those is $a$. Now, if $m$ is $0$, then the answer is $n - 1$, you can see it in the sample case $1$. If $m$ is not $0$, then there will be at least $1$ character $\neq 'a'$ in $s$. The problem makes us to partition the vector $a$ such that indices of each part in $a$ forms equal substrings in $s$.For example, consider $s = abcadaaabcadaa$. Then we can take $bcad$ or $bcadaaabcad$ as a valid string $t$. It can be easily seen that each partition need to be the same size, so we iterate all the divisors $i$ of $m$, and check if we can divide $a$ into $\frac{m}{i}$ equal substring. The checking part could be done by brute force (corresponding indices must be the same character, and the gap between character of each partition must be the same). After checking that the current partition is valid, we need to pad some character $'a'$ to the left and right of the substring we found then add it to the answer.
•  » » » » » » 4 days ago, # ^ |   0 i am sorry but can you explain a bit why $a$ has to be partitioned into equal sized parts.
•  » » » 5 days ago, # ^ |   0 https://codeforces.com/contest/1984/submission/264965359I have also done in the (O(n.sqrt(n))) passed in 62ms
•  » » 5 days ago, # ^ |   +7 This was our original intended solution. It is supposed to pass.
•  » » » 5 days ago, # ^ |   +1 But this one doesn't use any algorithm. I just used "brute force" to check if the substring is good or not.
•  » » » » 5 days ago, # ^ |   +1 $n$ has much less than $\sqrt{n}$ divisors for $n \approx 10^5$.
•  » » » » » 5 days ago, # ^ |   0 is $log_2{n}$ a good approximation? it's a while I'm trying to find a good upper bound for it
•  » » » » » » 5 days ago, # ^ |   +4 the most common approximation i've seen is $n^{1/3}$ for the number of divisors
•  » » » » » » 5 days ago, # ^ |   +1 There is an asymptotic bound but it's useless for competitive programming. You can just use $n^{1/3}$.
•  » » » » » 5 days ago, # ^ |   0 But this problem is like $2*10^5$, and when I estimate the runtime, it is about 700ms. I tried to google and see this: https://codeforces.com/blog/entry/19170. I was pretty nervous before trying to implement it as I don't know it is legal or not.
•  » » » » 5 days ago, # ^ |   +3 What is basically a brute force solution passing for D was a very pleasant surprise.
•  » » » 5 days ago, # ^ |   0 u can refer to this https://oeis.org/search?q=1344+maximal+divisors
•  » » 5 days ago, # ^ | ← Rev. 2 →   0 It would be really helpful if you could explain your appraoch a bit
 » 5 days ago, # |   0 C1 detailed video editorialhttps://youtu.be/5bWLd6AkHzs?feature=shared
•  » » 3 days ago, # ^ |   +1 nice
 » 5 days ago, # |   0 Super fast editorial.
 » 5 days ago, # |   0 can anyone explain why i can't hack? there is no button
•  » » 5 days ago, # ^ | ← Rev. 2 →   +6 You can't hack after contest in normal Div. 1 and/or Div. 2 rounds (except for Educational rounds). There's a thing called uphacking, but it's available only for Candidate Masters and above.
•  » » » 5 days ago, # ^ |   0 Thanks for explaining
 » 5 days ago, # |   0 Wow, the solution to C turned out to be clever, I have a more general solution that doesn't use the fact we only need to use op2 once, rather it's just brute force + dp: SolutionLet's think about operation 2, when we have to use it. when $a[i] + c$ is negative, and when op 1? when $a[i] + c$ is positive.Let's solve the problem with dp,let $dp_{0,i}$ be: for the first $i$ elements what's the maximum value of Cand $dp_{1, i}$ be: for the first $i$ elements what's the minimum value of CThe transactions are straight forward JK,$dp_{0, i+1} = max(dp_{0, i} + c, |dp_{1, i} + c|, |dp_{0, i} + c|)$ and$dp_{1, i+1} = min(dp_{1, i} + c, |dp_{0, i} + c|, |dp_{1, i} + c|)$The answer is obviously $dp_{0, n}$The solution for C2 is the exact same, maintain $cnt_{2, n}$ array where $cnt_{i, j}$ is the number of ways to get to $dp_{i, j}$, the rest is just case handling to check which one took the place of the current dp and updating the $cnt$ accordingly
•  » » 5 days ago, # ^ |   0 plz share your solution of c2.
•  » » » 5 days ago, # ^ |   +1 check my comment, I'll be glad to help you:)dp solutions for C1 && C2 (tap)
•  » » » » 5 days ago, # ^ |   0 I read that already. I got what you said but was not able to understand your code.
•  » » » 5 days ago, # ^ |   0 I haven't coded it but I can try to explain it.Assume that $dp_{0, i+1}$ was equal to $|dp_{1, i} + c|$(the max of those values is this). then the N.O.W you can reach the state $(0, i+1)$ get's increased by the N.O.W you can get to $(1, i)$ meaning: $cnt_{0, i+1} += cnt_{1, i}$
•  » » » » 5 days ago, # ^ |   0 What is N.O.W?
•  » » » » » 4 days ago, # ^ |   0 Number of ways
•  » » 5 days ago, # ^ |   0 u can just do dp[0][i] = dp[0][i-1] + c bcz it s obvious that others both are greater than it https://codeforces.com/contest/1984/submission/264912921
•  » » » 4 days ago, # ^ |   0 I don't think so, maybe abs(dp[1][i-1] + c) be greater
•  » » » » 4 days ago, # ^ |   0 i mean dp[1][i] for smallest one not the biggest one
•  » » » » » 4 days ago, # ^ |   0 dp[i][1] is min
•  » » 4 days ago, # ^ |   0 dp1,i+1=min(dp1,i +c,|dp0,i +c|,|dp1,i +c|), why we need |dp1,i +c| for minimum? As |dp1,i +c| >= dp1,i +c. I think this is not needed
•  » » » 4 days ago, # ^ |   0 we only need dp[1][i] = dp[1][i-1] + c for minimum
•  » » » 4 days ago, # ^ |   0 tbh I just copied the dp[0] one and edited it, yes correct
 » 5 days ago, # |   +10 DP solutions for C1 and C2:C1: let dp[i][0] be minimum score when we made i operations, dp[i][1] — maximum scoreC2: let dp[i][j] be amount of times we can get score j after i operations. as we can look only at max and min values, let's clear useless conditions after every step, then there will be only O(1) new values every time, so total complexity is O(n) if u use hash table, O(nlog(n)) — if BST (for e.g. std::map)C1 code: 264967072C2 code: 264965726
•  » » 5 days ago, # ^ |   0 You don't need a set/map or hashtable for coding c2, use IF brother, but this made the implementation way more clear
•  » » » 5 days ago, # ^ |   0 of course, u are right, but such structures were made to make our lifes easier) the simpler the code, the fewer errors=)
•  » » » » 5 days ago, # ^ | ← Rev. 2 →   0 actually no need u can update dp based on just i-1. Here are my submissions C1:264932150 C2:264949789 Overall complexity is O(n), and the code stays simple
•  » » » » » 22 hours ago, # ^ |   0 liked your code it's similar to what I was thinking but you made it so much shorter
•  » » 5 days ago, # ^ |   +1 Thank you. Really neat code!
•  » » 5 days ago, # ^ |   0 How did you come up with keeping only minimum and maximum did not get that
•  » » » 5 days ago, # ^ |   0 To achieve the final maxima, there are two ways: either keep making the value a positive integer as large as possible, or keep making it a negative integer as small as possible (then apply absolute operation to it at the end). Hence their intuition to keeping only min+max.
•  » » 4 days ago, # ^ |   0 can u explain more c2 bro ?
•  » » » 4 days ago, # ^ |   +1 of course, I'll tryhave you got my c1 solution?since we can keep only max and min score on every step(you can find prove by AkiLotus upper), let's do it on every step of our DP. we have 2 conditions and from every condition we can chose 1 of to 2 different actions, which means there will be not more than 2 * 2 = 4 new different scores. let's count each of them. but as we said earlier, we don't need to save all of them — we just need to save max and min score. okay, now let's count amount of times we can reach score we saved. initially, dp[steps = 0][score = 0] = 1, because we starts from score = 0. further we can go from score to score + a[i] or to abs(score + a[i]).for e.g.: cur_max = max(dp[cur_step]), mx_times = dp[cur_step][cur_mx] then dp[cur_step + 1][cur_mx + a[cur_step + 1]] += mx_times and dp[cur_step + 1][abs(cur_mx + a[cur_step + 1]) += max_times, for minimum score we do it in same wayif yours dp is vector>, then u can write it as I did it higher. but y also can use dp as vector, but IMO my variant is simpler
•  » » » » 4 days ago, # ^ |   0 correct me if m wrong , u are calculating for each index the 4 possiibles values ( in the next dp ) ( and count the ways to achieve them ) and u are only storing the maximum and minimum of them in ( in curr dp ) and so on ?
•  » » » » » 4 days ago, # ^ |   0 yep, I calculate no more than 4 new values and store no more than 2 of them(sometimes min == max, so we have to store only 1 value)
•  » » » » » » 4 days ago, # ^ |   +3 thanks sir
•  » » » » » » » 4 days ago, # ^ |   0 u are welcome)
•  » » » » 4 days ago, # ^ |   +4 great approach. I was finding the dp approach. Thanks
•  » » 4 days ago, # ^ |   0 I scrolled into the comments looking for a $dp$ solution just like this! Thank you.
 » 5 days ago, # |   +1 can sm1 tell me what are the 3 strings that match in this tc , problem D , abbaaaabbb output : 3
•  » » 5 days ago, # ^ | ← Rev. 3 →   +2 1- abbaaaabbb (whole string)2- bbaaaabbb (whole string except first character)3- b [ it's clear :) ]
•  » » 5 days ago, # ^ |   0 nvm got it : { b , full string , bbaaaabbb }
 » 5 days ago, # |   0 Wow these editorials were fast. Thanks!
 » 5 days ago, # | ← Rev. 2 →   0 First solve for H was from rainboy.
•  » » 4 days ago, # ^ |   +1 Rainboy is the real Orz.
 » 5 days ago, # |   0 Anyone solved C using dp,it was kind of more obvious for Easy version then u just add another state to dp for num_ways to make a value,nice contest, i really like the C1 and C2
•  » » 5 days ago, # ^ |   0 can you please explain c2 ?
•  » » » 5 days ago, # ^ |   0 i think coin change on cses is very similar to c2 .c1 was very similar to knapsack
•  » » » » 5 days ago, # ^ |   0 yeah, it is knapsack dp cause u are kind of fillinf container,adding based on just the previous state,i still that was nice problem, we really need such high quality tasks in codeforces rounds.
•  » » » 4 days ago, # ^ |   0 first i assume u understood how C1 is done using dp,now lets call dp[i][0] minimum value of c up to index i element and dp[i][1] maximum value,first we compute it using smae formula of C1,now count number of ways to do it,now at every step we have four choices either use the minimum value of i-1 or max value of i-1,both with or without abs value,we just update number of ways,however we need to be careful as if minimum value equals max value for index i-1 we only consider two choices with or without abs value(as the two others are same and we would be double counting),u can check my submission for implementation details.
•  » » » » 4 days ago, # ^ |   0 can you please elaborate on the last point, I couldnt understand
•  » » » » » 4 days ago, # ^ | ← Rev. 2 →   0 I wrote clean code based on his idea and it AC's. Hope it helps ll n; cin>>n; vectorarr(n+1); for(ll i=1;i<=n;++i){ cin>>arr[i]; } vectormaxVal(n+1),minVal(n+1); maxVal[0]=0; minVal[0]=0; for(ll i=1;i<=n;++i){ maxVal[i]=max(maxVal[i-1]+arr[i],abs(minVal[i-1]+arr[i])); minVal[i]=minVal[i-1]+arr[i]; } ll res = maxVal[n]; vectormaxValWays(n+1); vectorminValWays(n+1); maxValWays[0]=minValWays[0]=1; ll mod = 998244353; for(ll i=1;i<=n;++i){ if(maxVal[i-1]==minVal[i-1]){ // use only one - maxVal if(maxVal[i-1]+arr[i]==maxVal[i]){ maxValWays[i]+=maxValWays[i-1]; } if(abs(maxVal[i-1]+arr[i])==maxVal[i]){ maxValWays[i]+=maxValWays[i-1]; } if(maxVal[i-1]+arr[i]==minVal[i]){ minValWays[i]+=maxValWays[i-1]; } if(abs(maxVal[i-1]+arr[i])==minVal[i]){ minValWays[i]+=maxValWays[i-1]; } } else{ // use max val if(maxVal[i-1]+arr[i]==maxVal[i]){ maxValWays[i]+=maxValWays[i-1]; } if(abs(maxVal[i-1]+arr[i])==maxVal[i]){ maxValWays[i]+=maxValWays[i-1]; } if(maxVal[i-1]+arr[i]==minVal[i]){ minValWays[i]+=maxValWays[i-1]; } if(abs(maxVal[i-1]+arr[i])==minVal[i]){ minValWays[i]+=maxValWays[i-1]; } // use min val if(minVal[i-1]+arr[i]==maxVal[i]){ maxValWays[i]+=minValWays[i-1]; } if(abs(minVal[i-1]+arr[i])==maxVal[i]){ maxValWays[i]+=minValWays[i-1]; } if(minVal[i-1]+arr[i]==minVal[i]){ minValWays[i]+=minValWays[i-1]; } if(abs(minVal[i-1]+arr[i])==minVal[i]){ minValWays[i]+=minValWays[i-1]; } } maxValWays[i]%=mod; minValWays[i]%=mod; } ll ans = maxValWays[n]; ans%=mod; cout<
•  » » » » » » 4 days ago, # ^ |   0 thanks I got it.
 » 5 days ago, # |   +3 in E MIS was a big hint, is MIS very standard in many problems? when I heard MIS problem became relatively very easy, proving MIS (excluding root) is the answer was also not difficult, but how would someone think that MIS could be the answer, is it just more problem-solving of a similar type?
•  » » 5 days ago, # ^ |   0 what is mis
•  » » » 5 days ago, # ^ |   0 maximum independent set, just google it, its very simple.
•  » » » » 5 days ago, # ^ |   0 thanks
•  » » 4 days ago, # ^ | ← Rev. 3 →   +25 I got there by exploring specific cases. Like, first, I noticed that you can make the answer $\frac{n}{2}$ on a bamboo, but $n - 1$ on a star. Then I wondered if I could make at least $\frac{n}{2}$ on any graph. The two specific types made me think of bipartiteness, since the vertices that become leaves belong to one part in them. So I tried to show that you can take the larger part and make these vertices leaves. Got the construction and figured it's actually only necessary for any two chosen vertices to not be adjacent, which is exactly a MIS problem.
•  » » » 4 days ago, # ^ |   +13 okay, you tried many things narrowing down the answer which is no two chosen vertices are adjacent. basically not even knowing what is MIS one could have solved this, thanks!! i think i just did not try hard enough!
•  » » 4 days ago, # ^ | ← Rev. 2 →   0 I got there by naturally considering when a node can become a leaf.Well, either it already was a leaf and got chosen in the first operation. Or, it got chosen as a root after all its neighbours. The second condition obviously gives rise to MIS
•  » » » 4 days ago, # ^ |   0 Proving that these 2 conditions are sufficient is not hard. If the set of leaves we want is an independent set, then we are guaranteed to find a node we do not want to become a leaf in any tree of size >= 2, thus just choose it and recur till we are left with trees of size 1.
•  » » » » 3 days ago, # ^ |   0 Can you plz explain the problem E's implementation?? Like what is the dp states and how are transition happening?
 » 5 days ago, # |   -23 The sample for F is such a garbage.
 » 5 days ago, # |   +10 G is similar to this problem
 » 5 days ago, # |   0 why c2 : Thus, we have the choice of using option 2 or option 1 at any index j
 » 5 days ago, # |   0 Can someone help me explain this solution for C2? I just guessed a conclusion during the contestmy submission
•  » » 5 days ago, # ^ |   0 Bruh Genius you !
 » 5 days ago, # |   0 Both C1 and C2 are akin to the knapsack problem in dynamic programming, correct?
 » 4 days ago, # |   0 Hey, in problem 2 can anyone help me that what is the problem in this logic it's throwing wrong answer on 392nd token test 2https://codeforces.com/problemset/submission/1984/265022174
 » 4 days ago, # |   0 Hi, I got tle for C1 (easy). I tried dp (memorisation using maps)https://codeforces.com/contest/1984/submission/264928809Would be great if someone could give me insights on this and share a dp solution that got accepted for C. Thank you!
•  » » 4 days ago, # ^ |   0
•  » » 4 days ago, # ^ | ← Rev. 2 →   0 I used the same approach as yours in contest and got tle, this is actually an O(n^2logn) solution You can see this solution https://codeforces.com/contest/1984/submission/264938764 It is kinda greedy/dp with tc O(n)
 » 4 days ago, # |   0 we are told constantly in our college not to use global and static variables, is it a good a practice?
 » 4 days ago, # | ← Rev. 5 →   0 Hey Guys I solved C1 (not in the contest) using dynamic programming using two dp dp_max: the max sum we could create till i taking ith dp_min: the min sum we could create till i taking ith Transitions: if(arr[i] < 0){ dp_max[i] = max(dp_max[i-1] + arr[i], abs(dp_min[i-1] + arr[i])); dp_min[i] = dp_min[i-1] + arr[i]; } else{ dp_max[i] = abs(dp_max[i-1] + arr[i]); dp_min[i] = dp_min[i-1] + arr[i]; } with base case dp_max[0] = 0, dp_min[0] = 0 (---1 based indexing)This solution got accepted now can anyone tell me how will I use these transitions to build the count array which will count all possible ways to acheive this maximum ?Ps I guess it should be solved using the same way we find all the LIS, or All the min paths in Dijkstra algo. Pls help
•  » » 4 days ago, # ^ |   0 checkout this comment for the code and its parent comments for the idea.
 » 4 days ago, # |   0 In Problem C2, I am using below code to calculate power of 2, but this is giving stack overflow error. Any idea why? using ll = long long; long long power2(int n) { if (n == 1) { return 2; } long long p = power2(n/2); if (n & 1) { return p * p * 2; } else { return p * p; } } 
•  » » 4 days ago, # ^ | ← Rev. 2 →   0 overflow. you need to use mod. Also, too many recursive calls will give stack overflow.
•  » » » 4 days ago, # ^ |   0 Where?
•  » » » » 4 days ago, # ^ | ← Rev. 2 →   0 Using Modlong long power2(int n,ll mod) { if (n == 1) { return 2; } long long p = power2(n/2)%mod; if (n & 1) { return ((p%mod) * (p%mod) * (2%mod))%mod; } else { return ((p%mod) * (p%mod))%mod; } } Also, note that if you are calling this function multiple times for large values of n and are not caching the results, it will give stack overflow error.This is because very large number of function calls will be made. So, its better to cache the results. Using cachevectorcache(200009,-1); long long power2(int n,ll mod) { if (n == 1) { return cache[n]=2; } if(cache[n]!=-1){ return cache[n]; } long long p = power2(n/2)%mod; if (n & 1) { return cache[n] = ((p%mod) * (p%mod) * (2%mod))%mod; } else { return cache[n] = ((p%mod) * (p%mod))%mod; } } 
 » 4 days ago, # | ← Rev. 2 →   0 jiangly must be tired of getting second place to tourist. Anyways, their consistency is insane.
 » 4 days ago, # | ← Rev. 5 →   +7 Another approach for B problem: As all the digits are large, the sum is bound to increase by 1 digit, so if $x$ is large and has $n$ digits, then $a$ and $b$ must have $n-1$ digits. What is the largest large number with $n-1$ digits? AnswerYep, it will be $999... n-1$ times After that, I subtracted the largest "large" number of $n-1$ digits from $x$, resulting in a number say $y$.Now, we have to ensure two conditions: $y$ has a length of $n-1$. $y$ doesn't contain any digit as $0$ (why?) ProofThe 1st condition is pretty obvious from the problem statement itself. To prove the second statement, consider $y = y_1y_2...y_{n-1}$ and a = $9999...n-1$ times, where each $y_i \in$ {$0,1,2,...,9$}Necessary part If $y_i = 0$ for some $i$, then at max we can "give" $y_i = 5$, and $a_i = 4$ or vice versa, thus making one of these numbers not "large".Sufficient partClaim: Any of the other digits work ,i.e., $y_i \in$ {$1,2,\dots , 9$}.Proof: It is similar to the earlier proof, we can see $10 \le a_i+y_i \le 18$, which can always be "distributed" such that $5 \le a_i \le 9$ and $5 \le y_i \le 9$, which is exactly the range of a "large" number! $\square$Example: $a_i = 9$ and $y_i = 1$ can be redistributed as $a_i = 5$ and $y_i = 5$, making them both large.Hopefully, this is easy to implement and you can see my submission here: 264891168Please let me know, if there is some fault in the solution, or any other clarification is required?
•  » » 4 days ago, # ^ | ← Rev. 2 →   0 I think I have a far simpler answer that does require any integer conversions and works purely with strings, thus it can be used for very very large numbers:Basically, for any number to be right, 4 conditions must be met: Number must not be a single digit. The first digit must be a '1'. The last digit must not be a '9'. All remaining digits must not be a '0'. Please let me know if there's any holes in my logic.
•  » » » 4 days ago, # ^ |   +3 Yeah, its precisely the same :) I just wanted to write a formal proof ><
 » 4 days ago, # |   -8 I am struggling with a testcase right now on Problem B, the judge is saying that it expected an answer of YES on the number 793, which I believe should be a no.265101056
•  » » 4 days ago, # ^ |   +3 You might have read it wrong. 793 was the 17th testcase. You got a WA at the testcase on the number 1460 instead.
•  » » » 3 days ago, # ^ |   0 Thank you very much! That indeed helps, although I found out that my approach was flawed :D.
 » 4 days ago, # |   0 Ok
 » 3 days ago, # |   0 In C problem, Why we need to choose second operation only once. Can anyone give any testcase ?
 » 3 days ago, # | ← Rev. 10 →   0 How can I fix the memory limit exceed for my solution for C2 ? 265166920
•  » » 3 days ago, # ^ |   0 The way you utilized the queue was actually a bruteforce, which will not work. Take this test for example: 1 40 -1 -2 -3 -4 -5 -6 -7 -8 -9 -10 -11 -12 -13 -14 -15 -16 -17 -18 -19 -20 -21 -22 -23 -24 -25 -26 -27 -28 -29 -30 -31 -32 -33 -34 -35 -36 -37 -38 -39 -40 Answer is just $1$, but due to constant doubling, you'll quickly MLE/TLE yourself.
•  » » » 3 days ago, # ^ |   0 Ohh,I get it. Is there anyway I can optimise it ? Or should I scrape it think of something else ?
•  » » » » 3 days ago, # ^ |   0 I can only advise you to read the tutorial. Your current solution is practically an exhaustive search, and there are a lot more corners to prune with some mathematical intuitions.
•  » » » » » 3 days ago, # ^ |   0 Ok thanks a bunch mate :)
 » 3 days ago, # |   +1 Can someone elaborate on how implementation works for E ? Proving the MIS lemma is easy, but I can't figure out how to implement the dynamic computation. Like what is the dp formula ? I've been trying with rerooting and dp on edges as well
•  » » 2 days ago, # ^ |   0 Okay I figured something out, the implementation was harder than what I expected at first. Still, this problem is lovely, I don't regret wasting 2 hours on it instead of solving D during the contest !Basically my idea was to implement is to root the tree at a none-leaf node (exists if n > 2). Then I compute the MIS for going up and down the tree, starting at a given node (with dp). For going down, it's easy dp, it only depends on doing down for subvertices that are lower. But I need to store the state that I chose for each child when going down, that I will use for going up.Indeed, when going up from node i, whose parent is p, I need to add the value of going up with p, plus the value of going down with p (maybe minus one if p is set to be in the MIS), minus the value of going down with i, whose state is set by what I chose when going down with p.It would be clearer with maths formulae but I wanted to keep my comment short since idk if anyone will require my hindsight.
 » 3 days ago, # |   0 Can anyone help me with the problem C2? i am getting WA on test 2. I could not really think of where i am wrong. Thank You here is my submission
 » 24 hours ago, # |   0 For A, if the array isn't [1, 1, 3, 3] also impossible? Hint #1 and the solution code show that it is impossible only if all elements are equal.
•  » » 20 hours ago, # ^ |   0 Try to color the first 3 elements red and the last one blue.
 » 21 hour(s) ago, # | ← Rev. 2 →   0 My code for problem D is failing for test case no.83 , can anyone please explain if double or multiple hashing is the only way to avoid this 265689130? i used first time polynomial hashing with mod 1e9+9 and prime 31 only 28 test cases passed , then later using 1e9+9 and prime as 53 it passeD 83 test cases. Is it possible that there exists a more better prime for this to pass with single hashing ? le0n null_awe
•  » » 20 hours ago, # ^ |   0 Not actually sure — I don't remember ever using string hashing, so I don't have experience with hacks and string hashing. I think I've heard people say to randomize primes so nobody can reverse engineer hack test cases (if you want to stay single hashing).Again, I don't know string hashing very well, so not sure if this is a robust solution.
•  » » » 15 hours ago, # ^ |   0 i see okay thanks