### awoo's blog

By awoo, history, 3 months ago, translation, 1796A - Typical Interview Problem

Idea: BledDest

Tutorial
Solution (BledDest)

1796B - Asterisk-Minor Template

Idea: BledDest

Tutorial
Solution (awoo)

1796C - Maximum Set

Idea: BledDest

Tutorial
Solution (BledDest)

1796D - Maximum Subarray

Idea: BledDest

Tutorial
Solution (Neon)

1796E - Colored Subgraphs

Idea: BledDest

Tutorial
Solution (awoo)

1796F - Strange Triples

Tutorial
Solution (Neon)  Comments (76)
 » high quality problemset
 » Can someone check why is it giving TLE on Test Case 3 in C? I used binary search.. https://codeforces.com/contest/1796/submission/195465321
•  » » 3 months ago, # ^ | ← Rev. 4 →   I haven't checked the details of your code, but one common issue with C is that participants don't realize that there is no bound on the total size of $r$ over all test-cases. So you can theoretically have $20000$ test-cases that all have $r$ at or near $10^6$. With this knowledge, you may able to figure out why your approach TLEs. You're basically restricted to logarithmic time or better, i.e., $O(\log r)$ time (maybe a highly optimized sublinear polynomial might pass, but idk)But if you were conscious of this when estimating your time complexity, then the issue is likely something else...
•  » » » Thanks, my BS was wrongly implemented
•  » » What kind of BS you used. Looks like just iterate over [L, R].
•  » » » ah I see now it is just iterating over [L,mid] or [mid,R]
•  » » » https://codeforces.com/contest/1796/submission/195474428it got accepted now. Thank you!
•  » » » It's a different kind of BS that doesn't stand for binary search :P(yash246 please don't be offended, I just couldn't help but make this joke)
•  » » » » LMAO! Came down to comment the exact same thing.
 » » PROBLEM B : ASTERISK MINOR TEMPLATE VIDEO EDITORIAL SOLUTION LINK : https://youtu.be/BfuaPc6ErQUHAPPY CODING
 » Can someone tell me what i did wrong with problem B? Im always getting error on test 2 but i cant figure out what is wrong with my codehttps://codeforces.com/contest/1796/submission/195477231
•  » » you should add a condition if(flag2==false) for outer loop you just added it for inner and if statement only that's why check for this output it will give multiple yes aabaaba babbabb
•  » » » thank you so much i moved the break to the outer loop and it just got accepted.
 » 3 months ago, # | ← Rev. 2 →   For problem D, can someone help me see why my top down solution TLEs but the bottom up solution passes? Top down: 195483749 Bottom up: 195485579
•  » » Спойлер'cause you call for dp(n-1, k, i) and dp(n-1, k-1, i) in the function, so there are too much recursion calls ($C_{n}^{k}$). You can avoid it, if you check, that dparr[n-1][k][i] (and the other one) is not INF, so you don't have to call for this function.
 » For Problem EAfter rooting the tree at vertex 1, I greedily rooted the tree at the leaf of the shortest vertical path. Two iterations were enough to pass the test cases. Maybe someone can give me a counter test? I am not sure of the correctness of this greedy solution. Submission link.
•  » » Huh, this might be correct. I did some stress testing and couldn't find a counter test. Can't quite come up with a proof, though.
 » You: The guy she tells you not to worry about: » Can anyone please help me understand why my code gives TLE?https://codeforces.com/contest/1796/submission/195509093I basically followed the editorial exactly but used memorization instead of bottom-up. In general, is bottom-up faster, or is my implementation just flawed?
•  » » Did you find the answer?
•  » » » I needed to change the line "else if (cache[i][j][t] != 0)" to "else if (cache[i][j][k] != -1)" and default all values in the array to -1. That way you can precompute the answer to states where the answer is 0, which is much faster.
 » For D i didn't read that $k \le 20$ so I ended up with a solution that I think is $O(n \log n)$ (independent of k) rather than $O(k n)$
 » I was so close with C but didnt realise that these powerful restrictions on di take place, very cool
 » 3 months ago, # | ← Rev. 2 →   problem D can be solved with k<=10^5 in O(nlogn).check my submission: https://codeforces.com/contest/1796/submission/195344685
•  » » it can be solved in O(n).
•  » » » should be O(d*n)
•  » » » how it can be done in O(n)?
•  » » » » 3 months ago, # ^ | ← Rev. 5 →   you can separate cases by the length of the subarray you are going to chooselength=k, you can use O(n) sliding window RMQ with deque.this is my orz friend(Pacybwoah)'s code as an example: 195337817
•  » » Can you explain your segment tree approach ?
•  » » » assume that x>0. if the segment [l,r] is our final answer after performing some operations, it's obvious that we should increase the value of k distinct positions lying on the segment [l,r]. so it's always optimal if we increase the value of continous positions.in the case that x<0. we have a new x=-x, new k=n-k
 » For problem C can someone help me why I got wrong answer ? I thought I was very close to the answer,Submission here:195398117
 » on question C why there is no mod in solution code but it still gets accepted?
•  » » I found it too. I had considered the correct solution, but it didn't require any mod, so I missed the chance to get an AC.
•  » » the numbers never go over 998244353
 » 3 months ago, # | ← Rev. 2 →   [deleted]
 » What is the greedy method for D task?
 » For problem E, I don't think it is necessary to save all the length, just the top three, which is O (n)
•  » » Yeah, I mentioned that in the tutorial. You can do that but it is more annoying to code and is not that much faster under the given constraints.
 » why my solution is giving TLE on test on problem D my submission link :195537978 i used multiset for implementation and used greedy logic.
 » 居然没中文
•  » » Please use English. This is Codeforces, not Luogu.
•  » » » I am sorry .I will use English!!!!!!!
 » 3 months ago, # | ← Rev. 2 →   In problem C:For some reason my code written in C doesn't work but same code submitted as C++ code got accepted
•  » » 3 months ago, # ^ | ← Rev. 2 →   Found out the reason, integer overflow.GNU C11 doesn't have 64 bit ints and GNU C++20 (64) has.
•  » » » What do you mean by "GNU C11 doesn't have 64 bit ints"?I don't know why your code doesn't work in C (the only obvious difference I see is the d=1<
•  » » » » 3 months ago, # ^ | ← Rev. 3 →   I should clarify GNU C11 does have 64 bits ints but codeforces one's is only 32 bit same with GNU C++ 14 and GNU C++ 17 and long long int are 32 bit ints with these 3 compilers and d=(1L)<
•  » » » » » Yeah, it's the first reason. See 195959191 and 195959158. The problem is in the line printf("%lld %lld\n", 1, right+1-left);. 1 here is a 32-bit int, but it gets passed as 64-bit. I think you even end up reading from unallocated memory (or memory allocated for something else). The fix is either: printf("%lld %lld\n", 1LL, right+1-left); or printf("%d %lld\n", 1, right+1-left); I can reproduce the erroneous output on my MinGW gcc compiler. Although Code::Blocks outputs the intended output for me (differing from the separately installed MinGW instance, even with the correct/same flags set up). Neither compiler report a warning for this, but I have found an online compiler that does: https://www.onlinegdb.com/online_c++_compiler You can see it by pasting in your code. long long int is at least 64-bit on all mentioned compilers, as per the standard.
•  » » » » » » Hey you are correct, I was wrong.Thanks you for both your replies.
•  » » » » » » » No problem
 » 3 months ago, # | ← Rev. 2 →   Binary search solution for E.https://codeforces.com/contest/1796/submission/195570895Actually it is not a good idea to use binary search because checking an answer is more difficult than solving it directly with greedy.
 » For DI think my solution is O(N) 195675418Consider the subarray we finally chosed i~j(let S[i] be the sum of a[1~i])we can assum x>0 (otherwise we can let k=n-k,x=-x)$j-i>=k$: answer is $max$ { $S[j]-S[i]+ k*x -(j-i-k)*x$} = $max$ { $(S[j]-j*x) - (S[i]-i*x)$} + $2*k*x$ }$j-i  » In problem B, I need help with the failed test case. 195438093 •  » » String A and B's size need not be same. You mistakenly assumed them of the same length.  » can anyone help me understand the solution of problem f?, the "unique solution to the previous module equation" part •  » » It means once you chose d and r, the value of b' is fixed since it is a value between 10^(|b| — 1) and 10^|b| •  » » More accurate: if$b' \equiv - d \cdot r \pmod{10^{|b|}}$then all solutions of$b'$can be represented as$b' = c \cdot 10^{|b|} - d \cdot r$for any integer$c$. But since$1 \le b' < 10^{|b|}$there is only one solution in these bounds: it's when$b' = 10^{|b|} - (d \cdot r) \bmod{10^{|b|}}$. •  » » » Thank you!  » Is there a typo in F's solution? "all divisors k1 of (10|n|−1) for a fixed |n|." should it means "all divisors k2" instead? •  » » Also g can't equal to ⌊10^|b|b′⌋ I think, consider the case 10^|b| is divisible by b' •  » » » Thanks, fixed  » Why does the following greedy solution fail for E: If the tree is a chain then answer is its length. Else, for each degree 1 node find the distance of the closest degree >= 3 node from it and insert {dist, node} into a set. Now pick r to be one of node from the smallest two values of {dist, node}. Thus we erase the smallest two values and insert distance of node1 and node2 into the set as that path is now of same color and the smallest element currently in the set is the ans. Submission link : https://codeforces.com/contest/1796/submission/195404472  » Can somone pls explain what is wrong with my code for problem B 196139115  » 3 months ago, # | ← Rev. 2 → Greedy Approach for D in$O(nlogn)$independent of$k$:Prerequisite: knowing how to solve dynamic subarray sum with$O(logn)$updates to the array.Submission link and link to solutionLets split into two cases,$x\ge 0$and$x<0$First case: Let's assume a subarray$[l,r]$is optimal, the sum of this subarray is always sum of$a_l, a_{l+1},...,a_{r-1},a_r+ min(k, r-l+1) * 2x - (r-l+1)x$. This is because assuming no positions are selected in the subarray, we just get the subarray sum with$x$subtracted from all indexes, however than we assign the most amount of positions as possible for the subarray, when we do this we have to add$2x$to every position selected because we already subtracted$x$from all positions. This means the positions of the selected indexes do not matter as long as they are in the subarray. It is always optimal for all$k$values to be next to each other because compressing the values always makes sure they are in this subarray assuming that the first index is in the subarray, while not compressing the values can leave out values in the subarray. Since we assume that the first index is in the subarray, we can just brute force all$n$first indexes in$O(nlogn)$time with the dynamic subarray sum mentioned above. Second Case: The second case turns into the first case pretty easily. We can just represent$k$as$n-k$and$x$as$-x\$Link to CodeA formal proof or suggestions are appreciated :D
 » who is 54Michael top 1 ? he wrote only 1 round and already top 1he also only one who solved task F
 » In problem D, Does anyone have greedy solution, if you have Could you explain me?
•  » »
•  » » » Thanks
 » 3 months ago, # | ← Rev. 2 →   My clean O(n*k) dp approach for problem D not involving any casework for positive and negative x. Link
•  » » Thanks a lot for this.
•  » » if(n-i+cnt>=k){ //making the remaining k-cnt operations after the ith element. ans=max(ans,dp[i][cnt]); } Hey! can you plz explain this line of your code??
 » Can anyone let me know where this code is failing it is failing on test case 1661https://codeforces.com/contest/1796/submission/198624493PROBLEM B
 » the way of counting in the editorial of problem C (div2) is amazing, I m not that good at math So I binary searched everything! 201596273
 » Problem C: What's the reason of this modulo joking? It's totally creates confusion about second number can't be very large. But a misleading info
 » 3 weeks ago, # | ← Rev. 2 →   jh