### KAN's blog

By KAN, 19 months ago, translation,

• +182

 » 19 months ago, # |   +26 Good!
•  » » 19 months ago, # ^ |   -6 Why?
 » 19 months ago, # | ← Rev. 2 →   -7 For Div2 B solution. Using Set and iterate all. https://codeforces.com/contest/1457/submission/99918608
•  » » 19 months ago, # ^ |   0 That's cool.
•  » » 18 months ago, # ^ |   0 Thanks Mate
 » 19 months ago, # |   +6 For problem Div2 E, 99886275 is just so cool.
 » 19 months ago, # |   +5 Thank You.Nice Problemset — problems were to the point and good.I really liked it.
 » 19 months ago, # |   +4 I used dictionary tree to passed the div2 D, I can guarantee its correctness, but I can't guarantee its time complexity,can anyone hack my solutions? https://codeforces.com/contest/1457/submission/99900717
 » 19 months ago, # |   0 In Div2D, why is n<=60 if the given condition is true?
•  » » 19 months ago, # ^ |   0 Because if n>60 , We can always find a contiguous triplet (a,b,c) such that a > b^c.
•  » » » 19 months ago, # ^ |   0 Why we can always find that?
•  » » » » 19 months ago, # ^ | ← Rev. 3 →   +9 In case $n > 60$ There will be three numbers $(a, b, c)$ all having the same msb (Most Significant Bit) set to 1. You can do one operation with numbers $b, c$ this will turn off the msb therefore $a > (b \oplus c)$.
•  » » » » » 19 months ago, # ^ |   +5 Thanks
•  » » » » 19 months ago, # ^ | ← Rev. 2 →   +4 Because a_i <= 10^9 ~ 2^30. So of numbers which are k digits long in binary, we can have at most 2 to not get a triplet. And there are only 30 different sizes before we hit the cap of 10^9.edit: I may have answered the wrong question
•  » » » » » 19 months ago, # ^ |   0 Thanks
•  » » » » 19 months ago, # ^ | ← Rev. 2 →   +3 Because these three numbers share the same highest bit $1$. And $1 \oplus 1=0$. Let's consider these three numbers as $a,b,c$ where $a b \oplus c$ holds. Then we can always find that.
•  » » » » » 19 months ago, # ^ |   0 Thanks
•  » » 19 months ago, # ^ |   0 to avoid the case of having 3 or more consecutive numbers with the same heighest set bit equal the array length have to be <=60 because we have 30 bits to represent the numbers and 2 consecutive numbers with the same highest set bit is allowed then 2 * 30 = 60 — max array length now imagine that we have such array and we want insert a new number X be aware that the array has to be in non-decreasing order and we have consecutive segment of the array like the following a, b, c, d "without loss of generaility for the specific heighest set bit"a highest set bit is the 3rd bit b and c both have the same highest set bit which is the 4th bitd highest set bit is the fifth bitX has the the 4th bit as the heighest set bit so X have to be placed before d and after a which mean a, b and x have to be consecutive.
 » 19 months ago, # |   +52 Me when doing normal rounds: So I will try to do problems in order, if I can't do A in 30 minutes then I will consider B...Me when doing russian rounds:
 » 19 months ago, # |   0 For Problem B, n is <=10^5, test cases are <=10^4 and no. of colours are <=100. How is 10^11 (that's what I can interpret) solution works??If some one has any explanation and would like to correct where I am wrong, it will be great :)
•  » » 19 months ago, # ^ |   0 It is guaranteed that the sum of n over all test cases does not exceed 10^5.So when value of n is 10^5 then no. of test cases will definitely be 1. When test cases are 10^4, then value of n in all test cases are such that their sum will be atmost 10^5.
•  » » 19 months ago, # ^ |   0 There is a statement, "Sum of $n$ over all test cases doesn't exeeds $10^5$". That basically means $t*n<=10^5$. So, overall operations doesn't exeed $100*10^5=10^7$ which is acceptable in the given time limit.
•  » » » 19 months ago, # ^ |   0 Oh okay! Thanks. Will take care next time :)
 » 19 months ago, # |   0 I did not see that B had only 100 colors :/
 » 19 months ago, # |   0 I am still confused in Div 2D.
 » 19 months ago, # |   0 plzz anyone can explain div2 D. why n<=60
•  » » 19 months ago, # ^ |   0 For n <= 1e9, There can be atmost two numbers having same most significant bit. Therefore the bound will be atmost twice the number of bits i.e. 2 * log2(1e9) which is 60.
•  » » » 19 months ago, # ^ |   0 thanx bro!
 » 19 months ago, # |   0 Thanks for detailed explanation of Div2E!
 » 19 months ago, # | ← Rev. 2 →   0 My bad
•  » » 19 months ago, # ^ |   0 Jurys anser is 1 1 2 0 1 0 and yours is 1 2 3 0 1 0
 » 19 months ago, # |   0 For Div 2 Problem A, this is my code Code#include using namespace std; typedef long long ll; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); ll t; cin >> t; while(t--) { ll n, m, r, c; cin >> n >> m >> r >> c; ll v1 = abs((r + c) - 2); ll v2 = abs((r + c) - (1 + n)); ll v3 = abs((r + c) - (1 + m)); ll v4 = abs((r + c) - (m + n)); cout << max(max(v1, v2), max(v3, v4)) << '\n'; } return 0; } I have calculated the Manhattan Distance of the cell (r, c) from each of the corner cells, and printed the max distance. My code is giving wrong answer on test 2. Can anyone tell what's wrong in my code?
•  » » 19 months ago, # ^ |   +3 abs(a — b) + abs(c — d) is not equal to abs((a+c) — (b+d)).They both are different.
•  » » » 19 months ago, # ^ |   0 can you give an example case where devamg's logic would fail?
•  » » 19 months ago, # ^ |   0 find abs of (row) and col seperate for all four cornerint ans=Math.max(row-1+col-1, Math.abs(n-row)+Math.abs(m-col));  ans=Math.max(ans, row-1+Math.abs(m-col)); ans=Math.max(ans, col-1+Math.abs(n-row)); 
 » 19 months ago, # | ← Rev. 4 →   +3 for D, I brute forced subarrays of size <= 31, then brute forced again on the "split point". for example, if i have a subarray i...j and a split point of k, we xor the range from i...k and k+1..j. then, we check if the sequence we made decreases at any point. why does this work? I used the claim that there does not exist a construction where we have to make > 29 moves.https://codeforces.com/contest/1457/submission/99871104
 » 19 months ago, # |   +35 Nobody found the $O(N)$ for div1D?
•  » » 19 months ago, # ^ |   0 how to solve div1D in $O(N)$ ?
•  » » » 19 months ago, # ^ |   +5 For each situation where you just took the $i$-th thing, find the set of positions of the clone. For each situation where the clone just took the $i$-th thing, find the set of your positions. In the first case, it's a contiguous range, which means it has to be up to 2 contiguous ranges in the second case. There's a lot of possible transitions from $i$ to $i+1$ but it's a constant number and each takes constant time.
 » 19 months ago, # |   0 Can anybody explain the prefix suffix method used in division 2 in D-problem?
•  » » 6 weeks ago, # ^ |   0 I used dictionary tree after seeing someone's solution above.
 » 19 months ago, # |   0 Is it only me or Div1 E editorial is cryptic."Let call low bits that we don't need to care free bits." — can you maybe give an example. What is A there?
•  » » 19 months ago, # ^ | ← Rev. 3 →   0 For example, assume you have segment $(10, 20)$ and you set your number $011??$, your number will be in the segment whatever you set two lowest bits, then they are free.
 » 19 months ago, # |   0 in div2C,why the answer of 2 2 1 10 11 1 is 11,if i make the 0 to 1,it just take 1 second
•  » » 19 months ago, # ^ |   0 Here x is 11, which is the time required to add a platform.
•  » » » 19 months ago, # ^ |   0 ok,i mixed x and y
•  » » 19 months ago, # ^ |   0 This is your test case:n = 2, p = 2, k = 1; s = "10"; x = 11, y = 1.x is the cost of adding a platform, y is the cost of removing the first cell. In your case, there is only 1 option: that is to add a platform at position 2, giving 11 as your answer.
•  » » » 19 months ago, # ^ |   0 thanks,i have known the ball must first land on the p-th cell
 » 19 months ago, # |   +4 KAN For div2 D, the editorial states the following: Indeed, there are no two integers with the same highest bit set. It is much easier to solve the problem in such constraints.I think it should be stated as: there are at most two integers with the same highest bit set. Right? Because for input [1, 6, 7], the highest set bit of all numbers are different but 6 and 7 have the same highest set bit.
•  » » 19 months ago, # ^ |   0 Ya! Exactly. I too think it's a typo.
•  » » 19 months ago, # ^ |   +2 Thanks, corrected! I missed "more than".
 » 19 months ago, # |   0 How is the space complexity for div2B O(N) ?
•  » » 19 months ago, # ^ |   0 You are essentially keeping a separate index list for each possible color. The total houses is N, so the total entries in all index lists sum up to N.
•  » » 19 months ago, # ^ |   0 yeah, it should not be. I mean we don't require any extra space. https://codeforces.com/contest/1457/submission/99854109
•  » » 19 months ago, # ^ |   0 The only space that is variable with input is the array used to store doors colors. nothing else will change with the input.
 » 19 months ago, # |   +3 It is good tutorial.Kindly do mention the code also. Sometime explanation is not sufficient
 » 19 months ago, # |   0 Could someone please explain the dp approach to div2 C?
•  » » 19 months ago, # ^ | ← Rev. 3 →   +1 https://codeforces.com/blog/entry/85081#comment-727466 SpoilerI will explain more the 4 and 5 hints. - Given that the first cell on which the ball will land is cell i, we know it will visit cell i, i+k, i+2k, ... , i+xk=n) return 0; if (s[i] == '0') return cnt[i+k] + 1; else return cnt[i+k]; } int mem[n] = {}; for (int l=p; l=n) return 0; int &ret = mem[i]; if (~ret) return ret; if (s[i] == '0') return ret = cnt[i+k] + 1; else return ret = cnt[i+k]; } for (int l=p; l
•  » » » 19 months ago, # ^ |   0 Thank you!
•  » » » 18 months ago, # ^ |   0 Thank you so much for this Awesome Explanation.
•  » » » 5 months ago, # ^ |   0 I don't understand why are we iterating the first loop to n, wouldn't be going till cell p+k-1 be enough because from there jumping k cells would be same as jumping k cells from the starting position ( p ) ? I thought this was correct and it would be a O(N) so it would easily pass but it gave me WA :(
 » 19 months ago, # |   0 In div2 A, I misunderstood the problem at first. I thought that result equal sum of the min distance between each cell and the target cell. What is the closed formula to calculate this, if one exists ?
 » 19 months ago, # |   +18 It seems that the standard program to the Div.1 D has something wronghttps://codeforces.ml/contest/1456/hacks
•  » » 19 months ago, # ^ |   +7 Fixed, some testers' solution got hacked too.
 » 19 months ago, # |   0 What would be the difficulty level of XOR gun?
•  » » 19 months ago, # ^ |   0 I bet 1800
 » 19 months ago, # |   +8 Sorry for my stupid, it's a little hard for me to understand Div1E solution, can someone explain it easily? thanks!
 » 19 months ago, # |   0 1415B - Repainting StreetCan somebody explain why test case 3 in test 2 (below) says right answer is 2 days? If we choose any color (e.g. 1), there are only 6 houses, which are not this color. So, with capacity k=6 one day should be enough to paint. Looks I am missing something, but don't get what. 9 6 1 2 3 1 2 3 1 2 3 
•  » » 19 months ago, # ^ |   0 $K$ means a range that must be consecutive.So in the test,you can choose [1,6] or [2,7] or [3,8] or [4,9] to change the color.
•  » » » 19 months ago, # ^ |   0 Thank you Chinaxjh
•  » » 18 months ago, # ^ |   0 bro because we can choose from i to i+k-1 element and we should not choose 1 in them because they r of same colour before itself so 2 days required
•  » » » 18 months ago, # ^ |   0 Thank you man
 » 19 months ago, # |   0 Can anyone explain how to use precomputation of weighted prefix and suffix sums to sped up specifically
 » 19 months ago, # |   -8 Hey guys, here is my video proof for "Genius Greedy" in Problem E using induction hypothesis. Anyone who is interested can take a look
 » 18 months ago, # |   0 Hello guys I am a beginner and my solution shows WA on 5th test case of div2B, I cannot find the mistake can anyone please help? my solution — https://codeforces.com/contest/1457/submission/104735453