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)
• +93

 » 3 months ago, # |   +26 high quality problemset
 » 3 months ago, # |   0 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 →   +1 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...
•  » » » 3 months ago, # ^ |   +1 Thanks, my BS was wrongly implemented
•  » » 3 months ago, # ^ |   0 What kind of BS you used. Looks like just iterate over [L, R].
•  » » » 3 months ago, # ^ |   0 ah I see now it is just iterating over [L,mid] or [mid,R]
•  » » » 3 months ago, # ^ |   0 https://codeforces.com/contest/1796/submission/195474428it got accepted now. Thank you!
•  » » » 3 months ago, # ^ |   +12 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)
•  » » » » 3 months ago, # ^ |   0 LMAO! Came down to comment the exact same thing.
 » 3 months ago, # |   +6
 » 3 months ago, # |   -22 PROBLEM B : ASTERISK MINOR TEMPLATE VIDEO EDITORIAL SOLUTION LINK : https://youtu.be/BfuaPc6ErQUHAPPY CODING
 » 3 months ago, # |   0 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
•  » » 3 months ago, # ^ |   0 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
•  » » » 3 months ago, # ^ |   0 thank you so much i moved the break to the outer loop and it just got accepted.
 » 3 months ago, # | ← Rev. 2 →   0 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
•  » » 3 months ago, # ^ |   0 Спойлер'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.
 » 3 months ago, # |   +21 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.
•  » » 3 months ago, # ^ |   0 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.
 » 3 months ago, # |   +1 You: The guy she tells you not to worry about:
 » 3 months ago, # |   0 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?
•  » » 2 months ago, # ^ |   0 Did you find the answer?
•  » » » 2 months ago, # ^ |   0 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.
 » 3 months ago, # |   0 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)$
•  » » 3 months ago, # ^ |   0 Can you explain your approach? Thanks in Advance
 » 3 months ago, # |   +1 I was so close with C but didnt realise that these powerful restrictions on di take place, very cool
 » 3 months ago, # | ← Rev. 2 →   0 problem D can be solved with k<=10^5 in O(nlogn).check my submission: https://codeforces.com/contest/1796/submission/195344685
•  » » 3 months ago, # ^ |   +6 it can be solved in O(n).
•  » » » 3 months ago, # ^ |   0 should be O(d*n)
•  » » » 3 months ago, # ^ |   0 how it can be done in O(n)?
•  » » » » 3 months ago, # ^ | ← Rev. 5 →   +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
•  » » 3 months ago, # ^ |   0 Can you explain your segment tree approach ?
•  » » » 3 months ago, # ^ |   +3 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
 » 3 months ago, # |   0 For problem C can someone help me why I got wrong answer ? I thought I was very close to the answer,Submission here:195398117
 » 3 months ago, # |   +1 on question C why there is no mod in solution code but it still gets accepted?
•  » » 3 months ago, # ^ |   0 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.
•  » » 3 months ago, # ^ |   0 the numbers never go over 998244353
 » 3 months ago, # | ← Rev. 2 →   0 [deleted]
 » 3 months ago, # |   0 What is the greedy method for D task?
 » 3 months ago, # |   +1 For problem E, I don't think it is necessary to save all the length, just the top three, which is O (n)
•  » » 3 months ago, # ^ |   0 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.
 » 3 months ago, # |   0 why my solution is giving TLE on test on problem D my submission link :195537978 i used multiset for implementation and used greedy logic.
 » 3 months ago, # |   -19 居然没中文
•  » » 3 months ago, # ^ |   +8 Please use English. This is Codeforces, not Luogu.
•  » » » 3 months ago, # ^ |   -16 I am sorry .I will use English!!!!!!!
 » 3 months ago, # | ← Rev. 2 →   0 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 →   +1 Found out the reason, integer overflow.GNU C11 doesn't have 64 bit ints and GNU C++20 (64) has.
•  » » » 3 months ago, # ^ |   0 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 →   0 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)<
•  » » » » » 3 months ago, # ^ |   +3 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.
•  » » » » » » 3 months ago, # ^ |   0 Hey you are correct, I was wrong.Thanks you for both your replies.
•  » » » » » » » 3 months ago, # ^ |   0 No problem
 » 3 months ago, # | ← Rev. 2 →   0 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.
 » 3 months ago, # |   +5 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  » 3 months ago, # | 0 In problem B, I need help with the failed test case. 195438093 •  » » 3 months ago, # ^ | 0 String A and B's size need not be same. You mistakenly assumed them of the same length.  » 3 months ago, # | 0 can anyone help me understand the solution of problem f?, the "unique solution to the previous module equation" part •  » » 3 months ago, # ^ | 0 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| •  » » 3 months ago, # ^ | 0 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|}}$. •  » » » 3 months ago, # ^ | 0 Thank you!  » 3 months ago, # | 0 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? •  » » 3 months ago, # ^ | 0 Also g can't equal to ⌊10^|b|b′⌋ I think, consider the case 10^|b| is divisible by b' •  » » » 3 months ago, # ^ | 0 Thanks, fixed  » 3 months ago, # | 0 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  » 3 months ago, # | 0 Can somone pls explain what is wrong with my code for problem B 196139115  » 3 months ago, # | ← Rev. 2 → +34 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
 » 3 months ago, # |   0 who is 54Michael top 1 ? he wrote only 1 round and already top 1he also only one who solved task F
 » 3 months ago, # |   0 In problem D, Does anyone have greedy solution, if you have Could you explain me?
•  » » 3 months ago, # ^ |   0
•  » » » 3 months ago, # ^ |   0 Thanks
 » 3 months ago, # | ← Rev. 2 →   0 My clean O(n*k) dp approach for problem D not involving any casework for positive and negative x. Link
•  » » 3 months ago, # ^ |   0 Thanks a lot for this.
•  » » 2 weeks ago, # ^ |   0 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??
 » 3 months ago, # |   0 Can anyone let me know where this code is failing it is failing on test case 1661https://codeforces.com/contest/1796/submission/198624493PROBLEM B
 » 2 months ago, # |   0 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
 » 2 months ago, # |   +3 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 →   0 jh