dannyboy20031204's blog

By dannyboy20031204, history, 3 years ago, In English

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
  • Vote: I like it
  • +257
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Thanks for your interesting round.

»
3 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Thanks for the fast editorial. D was the most interesting problem for me.

  • »
    »
    11 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

LIGHTNING EDITORIAL

THANK YOU SO MUCH FOR PROVIDING THE ROUND!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks for good problems and fast editorial !

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

can anyone please tell me why this is wrong?problem -C

  • »
    »
    3 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    if the last element is negative then the answer must be -1.

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      yup, I am checking that here

      if(posi==-1||posi==i+1){
           cout<<-1<<endl;
           return;
      }
      

      because it is also possible that the array is already sorted

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it -8 Vote: I do not like it
        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.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I am also handling that case here

          if(vc[n-1]<vc[n-2]){
               cout<<-1<<endl;
               return;
          }
          
          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
            Rev. 2   Vote: I like it +5 Vote: I do not like it

            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.

»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Was A harder than normal for a lot of people?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Maybe yes, for some people. But A is easy for usually people.

»
3 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

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)

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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]$$$.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    +1

    It 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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +35 Vote: I do not like it

      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$$$.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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)$$$

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          $$$p$$$ is given in problem statement

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        That's a very interesting way to think of it.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +39 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you prove the observation III. Thanks

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 2   Vote: I like it +20 Vote: I do not like it

        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.

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Could anyone help with my problem D submission? Submission

I 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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    My implementation is quite the same with yours and I also get wrong answer on the same test

    But so far haven't found the explanation why

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    try

    2 3

    3 4

    the possible numbers are 3, 4 and 7(3*2+1) but your solution says it is 2, which is wrong

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I also used last element, current minimum and current element. I could pass all tests after contest ended. Submission

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    same solution, same wrong on test 2, Why does this not work?

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think you might have forgotten an important equals sign.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Are the recent contests tough or I lack practice? I'm clearly having a hard time solving questions nowadays.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Recent problems (like last ~10 contests) are more mathematically and more observation based than before.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +83 Vote: I do not like it

      I have seen people saying this for last 2 years

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it +35 Vote: I do not like it

      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)

»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Can someone explain the proof of A like I am 5 ?

»
3 years ago, # |
Rev. 6   Vote: I like it -10 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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)..

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how would you rate c problem?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone tell why it says array not sorted after all operations in this -https://mirror.codeforces.com/contest/1635/submission/147096553

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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".

»
3 years ago, # |
Rev. 3   Vote: I like it -16 Vote: I do not like it

Thanks to codeforces for this round

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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".

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      2x+1 = x<<1+1 4x = x<<2

      << Is binary left shift operator

      Take any random x say x=22 (10110) 2x+1 = 45 (101101) 4x = 88 (1011000)

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks! This is helpful!

  • »
    »
    3 years ago, # ^ |
    Rev. 5   Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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 .

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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!

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I've solved only one problem during contest, but my overall rating got lower, why ?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    Well, I guess you answered your own question, you solved only one problem.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it -8 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Hey, in editorial of B, ceil value should be used and not floor.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What rating range should problems B and C be?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

A very well balanced contest,, Loved it..

»
3 years ago, # |
Rev. 3   Vote: I like it +65 Vote: I do not like it

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 editorial
code: 147068110

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

    How do you calculate F_(r+2) in log r?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

    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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 y

Do this for all pairs and the answer is the total sum: Submission

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good Round

»
3 years ago, # |
  Vote: I like it +42 Vote: I do not like it

The solution of F is so wise!

I like the problem F!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

147064757 any one please tell me why this puts("0") doesn't work...

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I don't understand why. what I've written is the same as you. but I got AC:147131885

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Cannot use:

    	ios::sync_with_stdio(0);                                      
    	cin.tie(0);
    

    when mixing C and C++ I/O.

»
3 years ago, # |
Rev. 3   Vote: I like it +18 Vote: I do not like it

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?

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.

147131385

Note: Some constant factor optimizations can be made to my solution, but it still generously runs within the time limit.

Cheers!

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thanks, it helps me a lot.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D why is dp[0] initialized to 1 ?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For the initial term, when you haven't applied any operation.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    First of all, let's discuss the problem where $$$n=1$$$ and $$$a_1=1$$$.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Getting WA on TC 5 in Problem D 147139694 Can anyone please point out my mistake?

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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.

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it +2 Vote: I do not like it

    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;
            }
       }
    
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

First time giving a competition.Could not solve any one of the problems.I am Slowly working through editorials.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

ProblemA, Sample TestCase : 5.

Can anyone please provide a way to achieve 7 for 3 5 6?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    3 5 6
    We 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

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I made video Solutions (for A-E) in case someone is interested.

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

What can be the cause of getting WA 9 in E? 147171369

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

How to solve Problem C if we need to minimize the number of operations

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    3 years ago, # ^ |
    Rev. 3   Vote: I like it +20 Vote: I do not like it

    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.

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The solution is amazing! I didn’t know that BIT can maintain suffix lol

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Input
    Expected Output
    Your Output
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Input
        Expected Output
        Your Output
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Hey, for that input, my code actually gets the expected output.

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            My bad, I actually meant to type this testcase:

            Input
            Expected Output
            Your Output
            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
              Rev. 2   Vote: I like it 0 Vote: I do not like it

              Thank you, it worked! How do you think of these test cases so quickly? I spent forever debugging yesterday.

              • »
                »
                »
                »
                »
                »
                »
                »
                3 years ago, # ^ |
                  Vote: I like it +10 Vote: I do not like it

                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.

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

if I do arr[i+1] = max(arr) in 1635B — Avoid Local Maximums, why it would not pass pretest2 ?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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].

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Could anyone for [Problem C] [My solution is](https://mirror.codeforces.com/contest/1635/submission/263651690)explain why my solution is wrong ??