_kun_'s blog

By _kun_, history, 5 months ago, In English,

The round has finished. I hope you liked it!

Credits to the round authors and developers:

1110A - Parity. Authored by aitch and simonlindholm.

1110B - Tape. Authored by aitch and simonlindholm, development: _kun_

1110C - Meaningless Operations. Authored by GreenGrape

1110D - Jongmah. Authored by aitch and simonlindholm, development: KAN and MikeMirzayanov

1110E - Magic Stones. Authored by aitch and simonlindholm, developed by GreenGrape

1110F - Nearest Leaf. Authored by grphil, developed by gritukan

1110G - Tree-Tac-Toe . Authored by _kun_ and KAN

1110H - Modest Substrings. Authored by aitch and simonlindholm, development: Nebuchadnezzar

And now, the editorial:

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
 
 
 
 
  • Vote: I like it
  • +155
  • Vote: I do not like it

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

In C, If we precalculate answers for all a=2^x−1 up to m=2^23−1. Shouldn't it be 2^25-1?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +37 Vote: I do not like it

    Corrected thanks!

    We indeed increased constraints slightly before the contest.

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

Probably one of the most well written editorial i have ever seen!

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

Can someone please explain the solution of B in more detail?

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

    same here

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

    If we do not consider the constrain of maximum number of pieces that we can use than we can do it by putting 1cm piece on each and that will be the minimum So we initially start with putting 1cm piece on all..now we join some pieces to one piece so that we can decrease the number of pieces that we have add extra than the limit. and it is clear that we want to join only those which have least gap.

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

    Suppose, We have a stick with 100 cm length and 8 broken points,

    .........10.12.... .....30....35..... .......80.....86......93.........100...

    Since, there are 8 broken points and each point takes 1cm, at the very least we need 8cm tape to fix them. But with the constraint of number of tapes, we will have to cover a segment instead of a point. In the process, we will end up covering some unbroken points. So, total covered points will be the broken points + the points which fall under those segments that we picked to cover due to the constraint.

    Consider the following cases -

    Case 1: k = 8

    We have 8 tapes to use. So, there is no point wasting tape on unbroken points. Just cut 8 tapes of 1 cm, and fix the broken points. So, we are only using 8 cm of tape, no tape wasted. Cool!

    Case 2: k = 7

    We have 7 tapes to use. Now, we are 1 piece short. So, we will fix a segment with one tape (instead of just a point) and for rest of the broken points we can just put 1cm pieces.

    So, how do we choose that special segment? The goal is to waste as little as possible tape. Looking at the pipe above, we would like to cover 10.12, just wasting a 1cm tape. This will make us to cover point 11 which is not broken. But there is no better way.

    So, how much tape we are using now? 8 broken, 1cm points + 1 extra 1cm point = 9cm

    Case 3: k = 6

    We have 6 tapes to use. Using the same approach on Case 2, we have to pick another segment. 30....35 is our next best option, because we are justing wasting 4cm tape in the middle.

    Thus 8cm legit broken points + 1cm in the middle of 10.12 and 4cm in the middle of 30....35 = 13 cm

    So, we will be needing to cover up the short amount of tape, and we will choose the segments which come with little waste of tape. To find those segments, we need to list all b[i+1] — b[i] — 1, meaning the lengths of non-broken segments. Now, we will just cover the smallest (n-k) of the segments we need to.

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

Thanks for fast tutorials

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

can someone explain tape (2 question) in better way

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

    hey I will explain it with help of one example; let n=10, n=35, k=5; b[i]={1 2 5 6 9 11 13 15 23 27} broken segments; 1_2__5_6___9__11__13__15________23___27_ (where you have to repair I have put that integer no.)
    if you have value of k more than n (k>n), then you can easily cut the 10 segment of 1cm so it will very less tap require(only total 10cm tap required=10cm(1cm+1cm+1cm+1cm+1cm+1cm+1cm+1cm+1cm+1cm). But here the value of k is 5 so you have to cut 5 segment such that all broken part should cover.
    1_2__5_6___9__11__13__15________23___27_ (where you have to repair I have put that integer no.)
    now if you cut 1cm of 10 segment tap it is less tap required but you can cut only 5 tap segment because k value is 5.
    so you will cut 5 segment such that segment cover max length with small tap. now a[i]=b[i+1]-b[i] So a[i]={1,3,1,3,2,2,2,8,4} so by sorting it a[i]={1,1,2,2,2,3,3,4,8} So you will repair first all that segment which are very near means 1 and 2, 5 and 6, and so on.. you can cut the tap at most five times(k value), so your target is with this five segment you have to repair the stick.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      could u please explain the last point ?how should we repair,consider the test case 2 example of question which is given ?plsss

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        you will repair as follow value of k is 3 so youc can cut only three segment of tap in such a way the sum of segment will minimum. 1_2_4____________________________________60______________87___________________ you have cut 4cm segment so it covers 1 2 3 and 4 you have to cut 1cm it will repair 60 you cut to 1cm to repair 87 so total 1cm+1cm+4cm=6cm;

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

Now consider the case when a=2x−1. This implies (a⊕b)+(a&b)=a, hence it's sufficient to find the largest proper divisor of a — it will be the desired answer.

Why is that implied in this case?

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

    When a=2^x-1,it's binary will have all bits as 1.So, a&b equals b and (a xor b) equals a-b.

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

      Thanks for quick response!

      Why is the largest proper divisor the answer? Does it relate to the Extended Euclidean algorithm?

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

        can you explain me B part

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        Notice that when b is divisor of a,a-b will also be the divisor of a. So,maximum possible gcd(a-b,b)=largest divisor of a.

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

          I think you meant that, when b is a divisor of a, a - b will be divisible by b, didn't you?

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

    gcd(a-b, b) eqaul to b when b is factor of a.

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

I expected more than on G. Since it is just working with cases. The idea is obvious.

  • »
    »
    5 months ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    Well, yes, but there are several cute ideas along the way (that the degrees are small and and the idea about reducing the problem to uncolored vertices only, which is not mandatory to get AC, but helps greatly)

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it -9 Vote: I do not like it

      can you explain part B

      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it +30 Vote: I do not like it

        But there is an editorial written already...

        Ask some concrete question at least.

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

          What I want to know is, why have people stored the differences as b[i] — b[i — 1] — 1 and added n to the answer?

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

            Looks fine to me, basically you need to spend tape to cover the broken segments themselves ( + n in the end) and then you only care about which gapes between segments are "collapsed" into single tape part and which are not.

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

Anybody solved D with greedy?

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

In D, Can you please explain the statement — So we can assume that there are at most 2 triples of type [x,x+1,x+2] for each x.

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

    It means that given some x, it isn't necessary to try choosing the triplet [x, x+1, x+2] more than 2 times. Because for k > 2 (assume km = k mod 3), k[x, x+1, x+2] is equivalent to km[x, x+1, x+2] + [x, x, x] + [x+1, x+1, x+1] + [x+2, x+2, x+2].

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

      what do you mean by it doesn't make sense ? what will happen if we choose triplet (say) 3 times ?

      And how dp state is formulated ? can you describe a little bit.

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

        As k[x, x+1, x+2] is equivalent to km[x, x+1, x+2] + (k-km)[x] + (k-km)[x+1] + (k-km)[x+2], you can use this observation to apply simple dp that tries to take a triplet [x, x+1, x+2] at most only 2 times, and gives you the same optimal answer.

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

          so , in the optimal answer there will be no triplet like [x,x,x] ?

          do we have to form triplets only using [x,x+1,x+2] . only it will give optimal answer ?

          • »
            »
            »
            »
            »
            »
            5 months ago, # ^ |
            Rev. 2   Vote: I like it +4 Vote: I do not like it

            In the dp when you consider element x, you make 3 trials. In the jth trial (j ranges from 0 to 2), you try to take the triplet [x, x+1, x+2] j times (if minimum(count(x), count(x+1), count(x+2)) >= j), and you add to the jth trial's result. So basically, what is left from x in the jth trial is just consumed in the form of triplets [x, x, x].

            • »
              »
              »
              »
              »
              »
              »
              4 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              can you explain by writitng the recurrence relation for dp ?

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

                One possible way:

                Let dp[i][j][k] be the maximum count of triplets that can be formed if you start at value i, j occurrences of value i and k occurrences of value i + 1 are consumed in the form of triplets [x, x + 1, x + 2] where x < i. And let co[i] be the initial count of value i occurrences.

                For 0 ≤ l ≤ 2, if min(co[i] - j - l, co[i + 1] - k - l, co[i + 2] - l) ≥ 0, (where dp[i][j][k] is initially 0). The answer is dp[1][0][0] (Loop order: i = m → i = 1).

            • »
              »
              »
              »
              »
              »
              »
              4 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Sir, why are you adding floor((count(x) — j)/3) to the jth trial?

              • »
                »
                »
                »
                »
                »
                »
                »
                4 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Because you consumed j occurrences of x in form of triplets [x, x + 1, x + 2]. So you want to consume what is left from x in form of triplets [x, x, x] (and if 2 or 1 occurrences of x are left at the end, you will not use them). This is equivalent to taking .

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

                  Got it now, thanks !!

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  And Sir what will be the range of j and k in dp[i][j][k] and how?

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

Can anyone explain me the dp part of problem d ? its quite squeezed up.

suppose take the example of sample 1 :

10 6 2 3 3 3 4 4 4 5 5 6

**** what to do now ?

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

Fast editorial.Great!

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

Thanks for a clear and fast tutorial!

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

Hi everybody,

In case anybody needs practice with B, AtCoder Beginner Contest 117 had a very similar problem here.

Here is my editorial for Problem C. I believe it is easier to understand than the editorial provided here. Let me know if you have any doubts. :)

Here is my editorial for E.

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

In C, if a=2^x . Then as per "Denote the highest bit of a as x (that is largest number x, such that 2^x≤a) and consider b=(2^x−1)⊕a. It's easy to see that if a≠2^x−1 then 0<b<a holds." b=2^(x+1)-1. which does not hold in between 0 and a.

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

Has anyone solved "D" using greedy approach? If yes, can you please share!

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

how to dp in AC automaton? how to calculate the answer of all the current suffixes? Could you explain in details. thanks _kun_

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

In meaningless operations problem C, for those who find the first two lines very cryptic, they are saying take b as the complement of a (only from the MSB(a) to bit 0), so, a & complement(a) = 0 and a ^ complement(a) = 2^MSB — 1 (full 1's)

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

Thank You for a great tutorial. Can somebody explain part c tutorial? specifically, the part when a = 2^x-1. In that how is a xor b = 2^x-1-b and similarly the and part? Can somebody please explain using an example? Thank You very much!

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

In C, we denote x as 2^x <= a, but then the explanation states the following: "consider the case when a=(2^x)-1". Could someone explain what they exactly mean here?

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

    It should read "consider the case when a=2^(x+1)-1". I was also confused by that. Basically, a is a string of 1s in binary.

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

Can anyone explain The above D solution statement more clearly??

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

can someone tall the c++ codes for 2nd and 3rd question, maybe with comments and steps will be more helpful

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can view the submissions of other contestants. Just go to the "standings" page of the contest and double-click the cell along the row of the name of the contestant and the column of the problem you are interested in.

»
4 months ago, # |
  Vote: I like it +2 Vote: I do not like it

I think in C editorial, meaning of x should be the smallest number such that 2x > a.

»
4 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Thanks for the editorial. I didn't realize the editorial was already out, cause I didn't see the "Recent actions" so much. Adding a link to the original announcement blog post ( http://codeforces.com/blog/entry/65059 ) would be helpful :)

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

first problem can be made difficult if we increase the constraints of the problem i.e 1 < a,b,k< 2^32 — 1

»
4 months ago, # |
  Vote: I like it -11 Vote: I do not like it

In fact, we can use a simple way to solve the problem C.
Although this way is not very good.

#include<bits/stdc++.h>
using namespace std;
int wyj[25] = {3,7,15,31,63,127,255,511,1023,2047,4095,8191,16383,32767,65535,131071,262143,524287,1048575,2097151,4194303,8388607,16777215,33554431,67108863};
int qwq[25] = {1,1,5,1,21,1,85,73,341,89,1365,1,5461,4681,21845,1,87381,1,349525,299593,1398101,178481,5592405,1082401,22369621};
bool check[67108869];
int ans(int x)
{
    if(x == 1)  return 0;
    if(x == 2)  return 3;
    if(check[x])
    {
        for(int i = 0; i < 25; i++)
            if(wyj[i] == x)
                return qwq[i]; 
    }
    else
        for(int i = 0; i < 25; i++)
            if(x <= wyj[i])
                return wyj[i];
    return -1;
}
int main()
{
    for(int i = 0; i < 25 ; i++)
        check[wyj[i]] = 1;
    int q, tby;
    scanf("%d",&q);
    for(int i = 1; i <= q; i++)
    {
        scanf("%d",&tby);
        printf("%d\n",ans(tby));
    }
    return 0;
}
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain me the intuition behind the process in problem E ? Its hard to come up with such an idea

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

    This comment and read the editorial to the problem: http://codeforces.com/blog/entry/65059?#comment-490669

    It's not obvious to me how to come up with such idea, it just seems like its a tricky known technique :S

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you. Just saw the AtCoder editorial of the similar problem. Well, tough to solve such problems untill you are aware of the technique. Anyways thanks for the clarification :)

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

could somebody explain the tape problem considering n=5 k=3 broken segments=[1 2 4 60 87]??pleaseee

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

Please correct me if I'm wrong but it seems that in C the given editorial solution leads to wrong answer. For eg. if a=11 then given solution would give b=12. Instead it should have been b=4 (which we get by complimenting binary rep of a=11, considering significant bits).

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

Can anyone please explain the solution to D in more detail? (Like the exact dp equation and its initial values) My mind got a bit mixed up...

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

Could someone explain how to come up with such a dp state in problem D?I'm curious because I can't figure it out.

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

Can someone elaborate more on E? I can't quite understand why this equations proves that you need to check array difference.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hello!You can try some more complicate examples to find that it's obvious that the array difference with the first and the last number determines the result.By the way, there is a conclusion:if you can exchange any two neighbor elements in a array, you can obtain any permutation of this array.I help this helps:)

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

I don't know but I feel that for every question if they had attached an easily understandable code according to the logic explained then that would be very much helpful for us(at least for me )

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

please someone elaborate more on F

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

I was trying to solve problem 1110F - Nearest Leaf offline, using centroid decomposition but is giving me TLE 49838550, any ideas? I know it might sound as an overkill but still it's complexity is something about O(NlgNlgN + QLgNlgN). thanks

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

In Problem B, we will calculate the differences between every two adjacent broken points and store them in a sort array of size n-1. Now lets assume that we need to cover all the broken points with one piece of tape. For this the answer will be [difference of first and last element of the given array + 1] . Now we will optimize the answer as we have the chance to us at most k pieces of tape. We will subtract [x-1] form the answer for each of the last [k-1] elements of sorted array (where x is an element of the sorted array).

Code Snippet

    int n,k;
    long long m;
    cin>>n>>m>>k;
    long long arr[n];
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    long long brr[n-1];

    for(int i=0;i<n-1;i++){
        brr[i]=arr[i+1]-arr[i];
    }

    sort(brr,brr+n-1);
    long long ans=arr[n-1]-arr[0]+1;

    for(int i=n-2;i>n-k-1;i--){
        ans-=brr[i]-1;
    }
    cout<<ans;
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In question 1110A-Parity , can someone explain what is the error in my code :

  long double b;
    long long int i,j,k,n=0;
    cin>>b>>k;
    long double a[k+5];
    for(i=0;i<k;i++)
        cin>>a[i];
    for(i=k-1,j=0;i>=0 || j<k;i--,j++)
    {
        n+=(a[i]*pow(b,j));
    }
    if(n%2==0)
        cout<<"even";
    else
        cout<<"odd";

It is giving wrong answer in one of the test cases.

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

    For the sake of precision, don't use pow() with integers, ever.

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

Problem D.

Why does my solution in java fails in memory if it uses just MAX*5*3 of integers? https://codeforces.com/contest/1110/submission/51139125

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

GreenGrape For the Meaningless Operator problem there is a need for some edit, when $$$a=2^x-1$$$ and $$$a$$$ is prime, the output is 1, which is not a non-trivial divisor. You need to mention that separately.