### dannyboy20031204's blog

By dannyboy20031204, history, 2 years ago,

1635A - Min Or Sum

Tutorial
Solution

1635B - Avoid Local Maximums

Tutorial
Solution

1635C - Differential Sorting

Tutorial
Solution

1635D - Infinite Set

Tutorial
Solution

1635E - Cars

Tutorial
Solution

1635F - Closest Pair

Tutorial
Solution
• +257

| Write comment?
 » 2 years ago, # |   +4 Thanks for your interesting round.
•  » » 2 years ago, # ^ |   +7 Wow, ratings updated super quick.
 » 2 years ago, # |   +22 Thanks for the fast editorial. D was the most interesting problem for me.
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 Its a broken problem something feels off about it Observation was thrown forcefully into problem Anyway broken problems are always intresting I think this problem belongs to category where one needs to think what was question expecting and what could be possibily be used rather than searching for observations. I mean one knows what question is expecting there is literally no observation/blockers when one tries to solve problem ? The whole problem relies on single fact that you took a right direction
 » 2 years ago, # |   0 LIGHTNING EDITORIALTHANK YOU SO MUCH FOR PROVIDING THE ROUND!
 » 2 years ago, # |   0 thanks for good problems and fast editorial !
 » 2 years ago, # |   +1 can anyone please tell me why this is wrong?problem -C
•  » » 2 years ago, # ^ |   -6 if the last element is negative then the answer must be -1.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   +1 yup, I am checking that here if(posi==-1||posi==i+1){ cout<<-1<
•  » » » » 2 years ago, # ^ |   -8 ll posi=-1; if(vc[n-2]>0)posi=n-2; if(vc[n-1]>0)posi=n-1; if second last element is nonnegative and the last element is negative then the answer still remains -1 if the array is not already sorted but your code does not seem to be able to handle that.
•  » » » » » 2 years ago, # ^ |   0 I am also handling that case here if(vc[n-1]
•  » » » » » » 2 years ago, # ^ | ← Rev. 2 →   +5 I ran your code for this test case. 1 5 5 0 0 0 0 Your code gave -1 as output but this array can be made non decreasing with 1,2,3 as x,y,z ll posi=-1; if(vc[n-2]>0)posi=n-2; if(vc[n-1]>0)posi=n-1; Here you are checking as strictly more than 0 but you should be doing >= 0. I changed this part and submitted your code it gives AC.
•  » » » » » » » 2 years ago, # ^ |   0 Thanks a lot for your efforts.
 » 2 years ago, # |   +9 Was A harder than normal for a lot of people?
•  » » 2 years ago, # ^ |   0 Maybe yes, for some people. But A is easy for usually people.
 » 2 years ago, # | ← Rev. 2 →   +5 where $g(i)$ = number of $j$ satisfying $f(a_j) = i$ What is the intuition behind this and why it can helps the new dp value?(Problem D editorial)
•  » » 2 years ago, # ^ | ← Rev. 2 →   +1 Example array $a$ has 9, but 4 isn't belong $S$ you need count 9 and $2^3 <= 8 < 2^4$ so 9 counts in $dp[4]$.
•  » » 2 years ago, # ^ |   -8 +1It feels like there's no way of coming up with the editorial solution. It uses some arbitrarily defined function that somehow happens to be ans to the problem. I feel there's some other intuitive solution that I'm missing but if this is the expected solution then that's pretty terrible problem.
•  » » » 2 years ago, # ^ |   +35 I thought of it this way,Multiplying by 4 means adding "00" to the end of binary representation of $x$ and doing $2x+1$ is adding "1" to the binary representation of $x$. So now you have some strings and you can either append two zeroes or a single one to them. The number of such strings is $fibonacci(p-size(x))$, where $size(x)$ is the number of digits in binary representation of $x$. With this approach, we can also see how some other element is a "parent" of $x$.
•  » » » » 2 years ago, # ^ |   0 The number of such strings is fibonacci(p — size(x)). What is "p" over here and can you elaborate a little more on how the count is fibonacci(p — size(x)) ? Thank you
•  » » » » » 2 years ago, # ^ |   0 Suppose you want to find number of strings of size $n$, then you can either add "00" to the end of all strings of size $n-2$ or add a "1" to all strings of size $n-1$. This shows that $f(n) = f(n-1) + f(n-2)$
•  » » » » » 2 years ago, # ^ |   +1 $p$ is given in problem statement
•  » » » » 2 years ago, # ^ |   0 That's a very interesting way to think of it.
•  » » 2 years ago, # ^ |   +39 I think the tutorial is trying to explain things in a concise way but somehow also loses intuitiveness. Here's how I solved the problem.Observation I: Make the number binary. Then the problem will be like given a bunch of number, how much number under $p$ can be reached by adding a 1 or 00 at the back of those given numbers.Observation II: If a number $a$ can be reached from another number $b$, than a is useless because all number that a can reach can also be reached by $b$. Thus, we only take $b$ into consider.Observation III: If $a$ and $b$ cannot reach each other, than any number can only be reached by at most one of them.So, after we deleted all the 'useless' values, it's just solve for every number ad add the result together. And that's some simple DP from there.Hope this helps.
•  » » » 2 years ago, # ^ |   0 Can you prove the observation III. Thanks
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   +20 If we look at the binary representation of $a$ and $b$, $a$ can reach $b$ iff $a$ is a prefix of $b$. So if $c$ is reachable by $a$ and $b$, $a$ and $b$ must both be suffixes of $c$, since $a \neq b$, one must be a suffix of another.Co-authored by 8e7.
 » 2 years ago, # |   +1 Could anyone help with my problem D submission? SubmissionI basically used the fact that if one number can't directly be reached by another, all their children will be distinct. Submission passes the given pretests.
•  » » 2 years ago, # ^ |   +3 My implementation is quite the same with yours and I also get wrong answer on the same testBut so far haven't found the explanation why
•  » » 2 years ago, # ^ |   +7 try 2 33 4the possible numbers are 3, 4 and 7(3*2+1) but your solution says it is 2, which is wrong
•  » » 2 years ago, # ^ |   +2 Thanks to The-Winner for giving small counterexample.I messed up when it comes to considering which numbers are useless or not. What I was doing was finding the 'root' of each number where the root was the smallest number which could create it in the set S. Then I said that if some numbers have the same root, we take the minimum of these and the others are all useless. This is sadly not true, I would have to find all useless numbers in the same way as the tutorial.
 » 2 years ago, # |   0 My algorithm for C was the exact same, but instead of using the last 2 elements and the current element, I used the last element, the current minimum, and the current element. Why does this not work?
•  » » 2 years ago, # ^ |   0 I also used last element, current minimum and current element. I could pass all tests after contest ended. Submission
•  » » 2 years ago, # ^ |   0 same solution, same wrong on test 2, Why does this not work?
•  » » » 2 years ago, # ^ |   0 I think you might have forgotten an important equals sign.
 » 2 years ago, # |   0 in the editorial of the problem A Since, a1|a2|⋯|an≤a1+a2+⋯+an, the sum of the array has a lower bound of m why this statement is true and how did they arrive at this result
•  » » 2 years ago, # ^ |   0 If you have two numbers, taking their sum will make bits that are the same 'carry', but taking their bitwise OR won't. For example if you have $10_2$ and $10_2$, the sum will be $100_2$, but the OR will still be $10_2$. I'm sure there's a rigorous proof somewhere but this is how I came up with the observation.
 » 2 years ago, # |   +1 Are the recent contests tough or I lack practice? I'm clearly having a hard time solving questions nowadays.
•  » » 2 years ago, # ^ |   +10 I think as time progresses, people tend to become bored of older problems, which start becoming 'standard' problems. So in order to make the problem 'interesting', the authors tend to add some ad-hoc observations. Sometimes, these observations are cool to think about (I find the problems that can be converted to some graph problems interesting), while some become just arbitrary 'meh, cool whatever' (binary string problems for me). So have the problems become harder? Yes somewhat since many times you have to also think about what the author is trying to make u do, and which you can't do all the time.
•  » » 2 years ago, # ^ |   +11 Recent problems (like last ~10 contests) are more mathematically and more observation based than before.
•  » » » 2 years ago, # ^ |   +83 I have seen people saying this for last 2 years
•  » » » 2 years ago, # ^ | ← Rev. 2 →   +35 For me it feels like the opposite. Recent contests are more implemenatation heavy and less idea-oriented than a bit older ones(like autumn and older)
 » 2 years ago, # |   +6 Can someone explain the proof of A like I am 5 ?
 » 2 years ago, # | ← Rev. 6 →   -10 I don't think the $|a_x|$ in pC can reach $10^{18}$, it should grow in $O(n)$. Although I cannot give strict proof, I can say that the testers fear it happened. By asking them, as a friend...Update, I'm wrong, abc864197532 does have code to hack it. \abcorz/The operation is like (-2b) (-b) (a - b) a b
 » 2 years ago, # |   +3 for problem B ..but the optimal way is to set ai+1 to max(ai+1,ai+2).. i think it should be ..but the optimal way is to set ai+1 to max(ai,ai+2)..
•  » » 2 years ago, # ^ |   +2 Sorry, we will fix it later.
 » 2 years ago, # |   0 how would you rate c problem?
•  » » 2 years ago, # ^ |   0 I think <=1300
 » 2 years ago, # |   0 can anyone tell why it says array not sorted after all operations in this -https://codeforces.com/contest/1635/submission/147096553
•  » » 2 years ago, # ^ | ← Rev. 3 →   0 You can click on the link there to see which test case failed: In the link you provided, there is a line at the end which says "Click to see test details".
 » 2 years ago, # | ← Rev. 3 →   -16 Thanks to codeforces for this round
 » 2 years ago, # |   +3 Problem D can be approached by considering all numbers to be binary strings. We can see that the two operations then look something like this: 2x+1 is equivalent to appending 1 to the binary string, 4x is equivalent to appending 00 to the binary string. Its still important to ignore the useless numbers from the array, useless means those who can be generated by elements already present in the array. One we have an element (a[i]) from the array which is usefull we need to append some bits and make it a string of no more than p characters, so we can subtract length of a[i] from p and that will give us the free places to work on. We can append string of length 0, 1, 2.... p-len to the end and that will give us new numbers everytime. So we can count the number of strings of length 0, 1, 2, 3...p made up of 00 and 1 and then add all possible strings of length atmost p-len, Prefix sum can optimize this operation.Here is my code for the same, hope it helps someone: 147075092
•  » » 2 years ago, # ^ |   0 can u explain this line "2x+1 is equivalent to appending 1 to the binary string, 4x is equivalent to appending 00 to the binary string".
•  » » » 2 years ago, # ^ |   +4 2x+1 = x<<1+1 4x = x<<2<< Is binary left shift operatorTake any random x say x=22 (10110) 2x+1 = 45 (101101) 4x = 88 (1011000)
•  » » » » 2 years ago, # ^ |   +1 thanks bro
•  » » 2 years ago, # ^ |   0 Thanks! This is helpful!
•  » » 2 years ago, # ^ | ← Rev. 5 →   0 anandsaurabh46 can you please explain your below code ->for(ll i=2; i<=p; i++) { dp[i] = (dp[i-1]+dp[i-2])%mod; } for(ll i=1; i<=p; i++) { dp[i] = (dp[i-1]+dp[i])%mod; }And also why dp[0] = 1, as in fibonacci fib[0] = 0 and why you have written dp function two times?? Can you explain it clearly Will be very helpful.
•  » » » 2 years ago, # ^ |   0 The recurrence relation here is same as in fibonacci, but this problem has got to do nothing with fibonacci series. The reason dp[0] = 1 is that, for a string of length 0, we have 1 possible option that is empty string. for(ll i=2; i<=p; i++) { dp[i] = (dp[i-1]+dp[i-2])%mod; }This code is for prefix sum, because we want the count of all possible strings of length atmost x, so we will sum dp[0]+dp[1]+dp[2]....dp[x], so to optimize this operation, we can take dp[x] to be sum of all dp values from 0 to x.
•  » » » » 2 years ago, # ^ |   +3 anandsaurabh46 Ok now I understood, Thank you very much for your explanation and blazing fast reply. It actually really helps to understand things more clearly .
•  » » » » 2 years ago, # ^ |   0 Hi anandsaurabh46, the below code, adding dp[i-1] second time: for(ll i=1; i<=p; i++) { dp[i] = (dp[i-1]+dp[i])%mod; } We already added dp[i-1] once: dp[i] = (dp[i-1]+dp[i-2])%mod could you please tell why dp[i-1] is being added twice? Thanks!
•  » » » » » 2 years ago, # ^ |   0 Got it, first DP loop is computing possible string permutations for just ith length, the second loop is for counting all possible string permutations from 0th to ith length... Anyway thanks for the different solution approach!
•  » » » » » » 2 years ago, # ^ |   0 Exactly!
 » 2 years ago, # |   0 I've solved only one problem during contest, but my overall rating got lower, why ?
•  » » 2 years ago, # ^ |   -7 Well, I guess you answered your own question, you solved only one problem.
•  » » » 2 years ago, # ^ |   0 But I've been thinking that for the 1st problem I must get from 260 to 500 scores. for the 2nd 1000, etc, depending on time and attempts.
•  » » » » 2 years ago, # ^ |   -8 As far as I know your new rating is a function of overall standings, not the scores you obtain on a problem. The higher number of problems solved facilitates that but can not ensure it if many people are able to solve it before you.
•  » » » » » 2 years ago, # ^ |   0 OK. My rating before contest was 1089, after the contest it become 1004 (-89). What should I do or how many problems I must solve during contest to make rating go up ?What does the scores of the problems determine ? I've solved the first problem and got 438scores. But it gave -89.
•  » » » » » » 2 years ago, # ^ |   0 There's a nice chrome extension cf-predictor. It tells you in real-time what your rating would be if your current standing is your final standing. You can use that. The score you obtain on a problem adds to your total score and your total score determines your rank which further determines your rating change. There is no hard rule of rating change on solving a certain number of problems, it's all relative scoring. For more info refer this blog
•  » » » » » » 2 years ago, # ^ |   0 Your rating change will be calculated based on your postion in the standings table, your rating and the rating of the other partitipants. Actually each rating point one looses is a won rating point for somebody else.
•  » » » » » » 2 years ago, # ^ |   0 The contest score doesn't directly determine your rating. The scores are used to rank you with other participants. Based on previous rating you'll be given an expected rank. If your actual rank is better than expected rank your rating goes up otherwise it goes down.
 » 2 years ago, # |   +1 Hey, in editorial of B, ceil value should be used and not floor.
•  » » 2 years ago, # ^ |   0 Thanks, we'll fix it.
 » 2 years ago, # |   0 What rating range should problems B and C be?
•  » » 2 years ago, # ^ |   0 B = 800-1000 C = 1100-1300
 » 2 years ago, # |   0 A very well balanced contest,, Loved it..
 » 2 years ago, # | ← Rev. 3 →   +65 Problem D with $p \le 10^9$ is also solvable.For each "useful number" $u$, if $2^{k-1} \le u < 2^k$, we can generate $F_1+F_2+\dots+F_{p-k+1}$ elements ($F_i$ is $i$-th Fibonacci Number, begin with $F_1=1,F_2=1,F_3=2,...$) from $u$.It is satisfied that $F_1+F_2+...+F_r = (F_3-F_2)+(F_4-F_3)+...+(F_{r+2}-F_{r+1}) = F_{r+2}-1$ , so we can just sum up it.Time Complexity: $+N \log p$ instead of $+p$ in the editorialcode: 147068110
•  » » 2 years ago, # ^ | ← Rev. 2 →   +10 How do you calculate F_(r+2) in log r?
•  » » » 2 years ago, # ^ |   +16 Matrix exponentiation is a common way, maybe this video is useful?
•  » » » » 2 years ago, # ^ |   0 I'll watch it. Thank you!
•  » » 2 years ago, # ^ |   +33 When I suggested this problem to dannyboy20031204, the limit for $p$ was $10^9$. However, it was judged that matrix multiplication was too difficult for a div2 D problem :v I think that in the end, the value of $p$ doesn't really matter because the observations are all somewhere else.
 » 2 years ago, # |   0 My solution to A seems to be a little different. I used the observation that for two integers x and y, to make sum as small as possible and at the same time not changing x OR y, you need to remove a 1 bit for every position that the bit is 1 in both x and y. This is equivalent to removing x AND yDo this for all pairs and the answer is the total sum: Submission
 » 2 years ago, # |   0 Good Round
 » 2 years ago, # |   +42 The solution of F is so wise!I like the problem F!
•  » » 2 years ago, # ^ |   +10 Thanks! <3
 » 2 years ago, # |   0 147064757 any one please tell me why this puts("0") doesn't work...
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 I don't understand why. what I've written is the same as you. but I got AC:147131885
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 Checker comment wrong answer Integer parameter [name=k] equals to 5, violates the range [1, 4] (test case 4)Edit: Commenting out "IOS" will work though.
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 Cannot use:  ios::sync_with_stdio(0); cin.tie(0); when mixing C and C++ I/O.
•  » » » 2 years ago, # ^ |   0 thanks a lot!!!
 » 2 years ago, # | ← Rev. 3 →   +18 I have a different approach for problem $D$.Consider a value $x$. We have a set of possible values $< 2^p$ which we must include if we include $x$. For example, we must include $2x + 1$ and $4x$. Call these set of values $S(x)$. Using this notation, the problem wants us to find $\cup_i S(a_i)$.How can we examine $S(x)$? It's much easier if you consider it in binary — consider a binary string $s$ which represents some value $x$ in base $2$. $2x + 1$ appends a $1$ and $4x$ appends two zeroes. Therefore, if we start at some string $s$, we have to include anything that can be reached by adding "1" and "00" some number of times. For example, if we have some string $5$ or $101$ and $p = 6$, then we can have $101\mathbf{001}, 101\mathbf{111}, 101\mathbf{100}$.Notice that the size of $S(x)$ is $F[p - \lfloor \log_2 (x) \rfloor] - 1$, where $F$ is the Fibonacci numbers. The reason we have that floor log2 expression is because some prefix of our string is fixed (in the previous example, our string length is $3$). How the heck did Fibonacci get here?Task: Count the number of strings of size $n$ which are compositions of "00" and "1". Result: Answer if $F[n]$, easy to prove. (Convince yourself via recurrence relation)Task: $\sum_{i = 0}^n F_i = F_{n + 1} - 1$. Proof: Easy. Just use induction.But why isn't our answer the sum of sizes of $S(x)$? The answer is simple — we could have overlaps. Consider $100$ and $1\mathbf{00}$ for instance. In particular, we have overlap between binary strings $s_1$ and $s_2$ iff there is a way to reach each other via adding only "00" and "1". On naive approach is to brute force $\mathcal{O}(N^2)$ for each pair of binary strings and check if they can be reached from each other.But there's a better way. Notice that two strings can only be reached via each other iff one of them is the prefix of the other (say $s_1$ is a prefix of $s_2$). Since we know that the numbers are small (at most $25$ bits), $|s_2| \le 25$, so we can iterate over all prefixes of $s_2$ and check if they have some match in the array. Only if they do, check if they can be reached via some sequence of moves.How to check if they can be reached via some sequence of moves? One simple way is to ensure that each contiguous block of zeroes has even length. There are other ways too, like with a stack.147131385Note: Some constant factor optimizations can be made to my solution, but it still generously runs within the time limit.Cheers!
•  » » 2 years ago, # ^ |   0 thanks, it helps me a lot.
•  » » 2 years ago, # ^ |   0 How did you come up with this solution during the contest ? i'm finding it easier to understand than the dp one but more complex to come up with
 » 2 years ago, # |   0 In problem D why is dp[0] initialized to 1 ?
•  » » 2 years ago, # ^ |   0 For the initial term, when you haven't applied any operation.
•  » » 2 years ago, # ^ |   0 First of all, let's discuss the problem where $n=1$ and $a_1=1$.
 » 2 years ago, # |   0 Getting WA on TC 5 in Problem D 147139694 Can anyone please point out my mistake?
•  » » 2 years ago, # ^ | ← Rev. 2 →   +1 You are making an error while checking whether a[i] can reach some previous array value. You are independently doing the operations num/4 and (num-1)/2. However these 2 operations can be combined.For example, consider the array {3,25}.3*4 -> 12, 12 -> 2*12+1 = 25. However, your code doesn't take this case into account.
•  » » » 2 years ago, # ^ |   0 Thank you!
•  » » 2 years ago, # ^ | ← Rev. 3 →   +2 The bug is here. while(num > 0 && num % 4 == 0){ num /= 4; if(st.count(num)) ok = true; } num = a[i]; while(num > 1 && num % 2){ num = (num - 1)/2; if(st.count(num)) ok = true; } You are checking separately for condition 2x+1 and 4x. Here is my AC approach.  bool flag=true; for(int x=ar[i]&3, y=ar[i]; x!=2 ; x=y&3){ y >>= (2-(x&1)); if( y < *st.begin())break; if(st.count(y)) { flag=false; break; } } 
 » 2 years ago, # |   +1 First time giving a competition.Could not solve any one of the problems.I am Slowly working through editorials.
 » 2 years ago, # |   0 ProblemA, Sample TestCase : 5. Can anyone please provide a way to achieve 7 for 3 5 6?
•  » » 2 years ago, # ^ |   0 3 5 6We replace 3 5 whose or is 7 with 7 0 whose or is also seven Now we have 7 0 6 We replace 7 6 with 7 0 because both or are 7 We have now 7 0 0 The sum is 7 Sorry for the poor English
 » 2 years ago, # |   +8 I made video Solutions (for A-E) in case someone is interested.
 » 2 years ago, # | ← Rev. 2 →   0 What can be the cause of getting WA 9 in E? 147171369
•  » » 2 years ago, # ^ |   +1 Failing testcase: Ticket-462
 » 2 years ago, # | ← Rev. 2 →   0 How to solve Problem C if we need to minimize the number of operations
 » 2 years ago, # |   0 Can someone explain This is actually a classic problem, which could be solved by sweep line trick + any data structure able to maintain prefix-minimum with single point updates, like BIT or segment tree. I am not able to understand the implementation in the solution as well.Is this some standard algorithm?
•  » » 2 years ago, # ^ | ← Rev. 3 →   +20 The sweep line trick is an offline method. We'll sort the segments in the decreasing order of their left endpoints, and add them one by one to your data structure. After adding all segments whose left endpoints are not less than $i$, we can find the answer for those query $j$ with $l_j = i$, which is equalvance to the minimum segment whose right endpoint are smaller than $r_j$ currently. Btw, the data structure you need is segment tree or sth.
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 I think the solution is actually maintaining a suffix minimum, and his BIT implementation is just the opposite of the prefix one that I know.
•  » » » 2 years ago, # ^ |   0 Well, that is because in my implementation, I sort the segments in the increasing order of their right endpoints. This way I'll need to maintain the suffix minimum. It doesn't matter a lot since the basic idea is still sweep line.
•  » » » » 2 years ago, # ^ |   0 The solution is amazing! I didn’t know that BIT can maintain suffix lol
 » 2 years ago, # |   0 Hi, can a programming god help me figure out why my D is getting WA on test case 5? I basically eliminate the useless numbers, and then do some fib dp to find the answer. https://pastebin.com/ARt4ESMf
•  » » 2 years ago, # ^ |   0 Input1 2 2  Expected Output1  Your OutputRuntime Error
•  » » » 2 years ago, # ^ |   0 Hey! Thanks for the response. I've changed the code to account for that test case, but the answer is still wrong. https://pastebin.com/caQFEtC1
•  » » » » 2 years ago, # ^ |   0 Input3 2 1 2 9  Expected Output3  Your OutputRuntime Error
•  » » » » » 2 years ago, # ^ |   0 Hey, for that input, my code actually gets the expected output.
•  » » » » » » 2 years ago, # ^ |   0 My bad, I actually meant to type this testcase: Input3 3 1 4 7  Expected Output4  Your Output5
•  » » » » » » » 2 years ago, # ^ | ← Rev. 2 →   0 Thank you, it worked! How do you think of these test cases so quickly? I spent forever debugging yesterday.
•  » » » » » » » » 2 years ago, # ^ |   +10 Well, I cheated. And the secret is, CF Stress :)I have not yet added Java support in the deployed version, but I do have Java support locally, with some workarounds. Hence I was able to come up with a counter example in less than a minute.
 » 2 years ago, # | ← Rev. 2 →   0 I have a question about the solution of problem d, regarding control flow  if (x & 1) { x >>= 1; } else if (x & 3) { break; } else { x >>= 2; } Doesn't x & 3 imply x & 1? Or should x & 3 be replaced with x % 3? I don't understand why x is not useful if x & 3. Could someone explain it for me?Thank you so much in advance
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 If the last two bit of the binary representation of x is 00, we need to continue finding possible parents. But if the last two bit is 10, we need to stop finding since the operation is * 4 and there are no parents that can generate it.So in my implementation, I use x & 3 to check whether the second last bit is 1 or not. It can be replaced with x % 4 or x & 2. The latter is because I have checked the last bit is 0.
 » 2 years ago, # |   0 if I do arr[i+1] = max(arr) in 1635B — Avoid Local Maximums, why it would not pass pretest2 ?
•  » » 2 years ago, # ^ |   0 Here is the hack test: 1 5 1 3 2 3 4 Your solution will modify two numbers, but it's optimal to replace the third number with 3.
 » 2 years ago, # | ← Rev. 2 →   0 I think there is an important point to notice for Problem D: in dp[i] = dp[i - 1] + dp[i - 2], what if dp[i - 1] and dp[i - 2] contribute to duplicate numbers in dp[i]? Fortunately, this will not happen because dp[i - 1] only generate odd numbers in dp[i], and dp[i - 2] only generate even numbers in dp[i].
 » 7 weeks ago, # |   0 For problem D, how are we so sure that two numbers that are not related (i.e., one is not a parent of another) cannot generate the same number some steps later?