300iq's blog

By 300iq, 10 months ago, In English
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
  • +98
  • Vote: I do not like it

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

Great contest! Thank u!)

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

Great contest and great problems ! But weak test cases for problem A div1 ...

»
10 months ago, # |
Rev. 2   Vote: I like it -28 Vote: I do not like it

Deleted

»
10 months ago, # |
Rev. 2   Vote: I like it -25 Vote: I do not like it

It's a good contest! I like these problems! Thank you:-)

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

Really weak pretests for Div2 C.

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

I don't know if i'm too weak or not, but to me this must have been the hardest round that I have participate in

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

Weak test data (pretests) for problem 'C' Div.2 or 'A' Div.1 made a lot of solutions (more than usual) get WA during system tests . I hope next round's test data will be much stronger . Anyway,it was a great round and I hope everyone got what they wanted :)

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

Can someone explain D, please? Can you prove why the claim: "the Young diagram can be partitioned into domino if and only if the number of white cells inside it is equal to the number of black cells inside it." is true? Also, why was the example of a "basic" diagram provided?

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

    We know that every domino occupies one white cell and one black cell. Assume that we can cover all the screen if the number of white cells is not equal to the number of black cells. name the number of whites "a" and the number of blacks "b". Every white domino has a black side so all of the white dominoes have black dominoes ( For the other side of the domino). so we have b-a dominoes that both sides are black and that is a contradiction. Sorry for my poor English :)

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

    Let me give it a shot!

    Well, if you color it this way, you can see that each cell has adjacent cells only of a different color. Also, note that if we place a tile on the diagram, it will always cover 1 white ane 1 black square.

    Now, let's say that the white squares are less than the black ones. We can see that if try an example!

    So, if for example, the white squares are less than the black ones, it makes sense that if you try to connect them to blacks, we'll run out of white ones before blacks. So, intuitively the answer is $$$min(numOfBacks, numOfWhites)$$$!

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

     If we use domino structure as given in image and keep it's both endpoints on the columns containing an odd number of lengths. now both endpoints require even number of the block left to be filled and middle columns are unaffected(on basis of parity).but the length of this structure should be even. this way we can joint at most min(columns with an odd block at odd indexes, columns with an odd block at even indexes) columns. ~~~~~ int tot = 0,odd = 0,even = 0; for(i=1;i<=n;i++) { tot+=a[i]/2; if(a[i]%2) { if(i%2) odd++; else even++; } } ans = tot + min(odd,even) ~~~~~

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

So, i am a newbie to giving contests. This was my 5th contest and i wasn't able to solve any one of them this time too. Is that normal and will i be able to become good at this anytime soon if i practice. I have been practicing a2oj ladders lately. Everyone's feedback and support is appreciated.

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

    My only advice in this respect would be to try and solve most of the questions that you couldn't solve in this contest. If you can solve questions out of the contest, then atleast you will have something to do during the contest.

    You may make simple targets like solving 1 or 2 in order of difficulty which you couldn't solve during the contest. :)

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

    I'm new too and getting crushed in my first 4 contests. I solve mostly problem A in div 2, maybe B and I never have time to attempt C or harder problems.

    If you look at the rating graphs of other users, even the top ones, they often have a dip (falling rating) in the beginning so I think it is normal.

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

    You should participate in maximum contest and try to do questions after contest you couldn't solve and then analyse it why u couldn't solve them in contest.

    As you can see my graph initially i solved 1-2 questions and i gradually improved these things requires patience.

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

For div2D, why doesn't this solution work?

We start from the first column and we move to the right. There are several cases:

  • If our current column has even squares we add it as it is (ie. $$$ans += arr[i] / 2$$$)
  • If it has odd, we do the following: We try to find the next column with odd squares and if in between them there are even columns, we can use all of them and get an optimal answer (ie. $$$ans += (sum-of-all-squares-we-found) / 2$$$). And then we move to the next column! (you can see that if you try an example)
  • Otherwise, if there are odd (or it is the last column that has odd squares), there is no way to use the 1 square left (or am I wrong?), so we do the same as the 1st case (ie. we add ans += $$$arr[i] / 2$$$) and we move forward.

I could not find any test cases that break this greedy. Can you help me? Thanks!

Here is my code: https://codeforces.com/contest/1269/submission/67367653

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

Problem A. I spent half an hour on you. Good round.Thank you 300iq!!!

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

Can someone hack my Div2C / Div1A or is it actually O(n) code?

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

Don't you think that samples in Div2A are a bit too suggestive xD?

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

    Oh... You know, I had other answers in the "tests" test set. But then I copied that to "pretests" and forgot about it...

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

    And right now I can't stop my laugh because I didn't even suspect that I have these answers XD

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

Can we solve Div2D using dp?

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

    I don't think so.

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

    I AC Div2D using a greedy approach, please tell me if it is wrong. Looping over pillars from left to right. For each pillar, try to place as many blocks vertically from top to down. If it have one space empty in the bottom, then we occupy this space greedily by placing a block horizontally. When processing pillars, if (len[i]-horizontal_height)%2==1, then increase horizontal blocks height by one, else decrease by one(it's pretty obvious if you draws it). If the horizontal blocks height is larger than maximum allowed height, then calculate how many space is wasted.

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

Is Div1B Div2D editorial not completed?

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

    No, its completed.

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

      Then, something wrong with it:

      If the Young diagram has two equal rows (or columns) you can delete one domino, and the diagram will still have an equal number of white and black cells.

      First, it may have not equal number of white and black cells from beginning. Second, I think it should be stressed out that after deletion it is still Young diagram.

      so you can find the answer by algorithm described below.

      Where to look at? Should I look into other task editorial? I don't understand.

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

        The algorithm is: find two equal rows or columns and delete domino on the.

        For example, if you have

        7 6 6 5 4 3

        You can delete one domino, to get another young diagram.

        7 5 5 5 4 3

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

          I claim that editorial is incomplete. First quoted by me sentence is simply wrong if you don't say that number of black and white cells were equal.

          Next, if you say "assume that number of black and white cells are equal" then later where you say "So we have a contradiction!" Contradiction with what? With equal number of black and white? Yes. In short: assume we have equal -> no, we don't! This is not connected to anything else.

          You could say following: you can place one domino and unfilled cells would still have equal number of black and white cells. So, lets continue fill cells by domino like this until you can't. This means that there is no two equal rows or columns. Thus, we're left with 'basic' diagram. But in basic diagram number of black and white cells are not equal. Therefore we should fill everything using this algorithm.

          In short, we showed that if we have equal number of black and white cells, then we can fill all cells by domino.

          Now, about not equal:

          Just because if you have more white cells (case with more black case is symmetrical), and there are no equal rows and columns...

          You talk about case when no equal rows and columns. But what about case when there are equal rows and columns? I think you want just do the same algorithm until you have 'basic' diagram. But what if there is filling that is better because it does something different?

          There is simple proof that you can't do better than minimum, but you didn't include it. As someone already noted in comments: no matter how you place domino, you always "use" single black and single white cell. So, you can't place more than $$$min(black, white)$$$. Then, it's easy to see that the same algorithm doesn't reduce this minimum, but in the end you have 'basic' diagram that can be processed as you said.

          If you don't want complete editorial, then alright. I just don't like when missing parts of editorial is placed in comments.

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

            The editorial does not need to have every detail in depth its just the general idea so you can get the details yourself.

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

              At least I would require editorial to be coherent. I mean, it should have narative order.

              But, let me just disagree with you. And I'll also tell why.

              Task solutions should be proven. Otherwise, we can't claim that there is no better output. In other words, task should be correct. Because if solution or checker is wrong, then how can you judge?

              Now. Imagine there is no proof in editorial. Then, all we have to do is: prove it by yourselves, or simply belive that author has correct proof.

              I was looking into editorial, because I was need a proof, and I had problems with mine. And, instead of connected proof I saw puzzle of sentences, and had to figure out what is related to what.

              Yes, I was able to figure out, but only after reply with example what exactly means "remove domino".

              And, in the end: I think, editorial should not have "simply wrong" statements, and also there should be no places where you should guess right meaning of what author wanted to say.

              So, in short: I don't belive that problem is correct unless I have a proof. I don't require proofs of simple facts. But when fact is not simple, I would like to have detailed explanation. Simplicity of fact is based on difficulty to find proof, not by difficulty of fact or difficulty of proof. Fact can be simple, but proof can be hard. Fact and proof can be both simple, but if it's very hard to find a proof — it should be explained.

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

            I find a test that I use author's algorithm is wrong: 16 2 2 1 2 1 2 2 2 2 1 1 1 1 1 2 1 If using author's algorithm, we will have 12 domino, it's mean we have to fill all cells, but how we fill the 15th and 16th col

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

              This test is invalid. Sequence should be non increasing.

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

"Just because if you have more white cells (case with more black case is symmetrical), you can take the first column with more white cells than black cells and delete the last cell of this column" — I think it is not true if you have equal columns since resulting diagram can no longer be Young one. But if you preced that with argument of dealing with equal columns then you will be fine I think.

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

Excuse me, there might be a small problem in the editorial of 1269E:

[After that, let's say that $$$x≤k$$$ is zero, and $$$x>k$$$ is one.]

[Then you need to calculate the smallest number of swaps to make segment $$$1,1,…,1$$$ of length $$$k$$$ appear in the permutation.]

Isn't it segment $$$0,0,...,0$$$ of length $$$k$$$? I'm confused.

UPD: Fixed.

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

Can anyone explain me div2 D

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

can someone exlain me Div2B?

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

    Basically we are first finding all the possible values of x for which elements in the array a can be converted totally into array b, We are doing this by comparing each element in array a with b1

    For example

    let m=5, a={4,2,3,2,1} and b={2,3,3,4,5}

    so first comparing

    a1 with b1 we get x=3,

    a2 with b1 we get x=0,

    a3 with b1 we get x=4,

    a4 with b1 we get x=0,

    a5 with b1 we get x=1,

    then we can add each of these Xs to array a and check if we are getting array b or not, for all valid Xs , we store the minimum X

    I did it using 2 loops(one for getting X and then temporarily increasing array a with x and comparing it with b) with O(n^2) and it passed the testcases

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

      Thanks, how is it guaranteed that the value of X will be from one of these only and not anything else since we didn't consider b2, b3, b4... in this?

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

        Think about it this way.. Suppose you know the correct X, then adding the X to the array A will result in ONE of the element of A to become equal to b1.

        I mean for a correct X, a1 may become b1 or a2 may become b1 and so on.. I mean every element of A has chance to become b1.. So we can just compare all elements of A with b1, store all the values for which elements in A become b1.. For a correct X all elements in A will map to corresponding elements in B.

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

          Perfect, thanks!

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

          can you explain the proof why such x will always exist

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

      https://codeforces.com/contest/1269/submission/82891742

      can u pls look into this, i don't know why i am not getting anything printed in test case 9.

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

in div2 E what is "si"?

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

    I think $$$s_i$$$ here represents the array formed after replacing x<=k by one and x>k by zero.

    Then for $$$s_i$$$ = 0 means that it should not be present in the subsegment so minimum number of swaps required to remove it would be min($$$p_i$$$, k-$$$p_i$$$).

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

What was test case 7 for Div2C?

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

    I believe it was larger version of:

    9 3

    123113133

    Answer should be:

    9

    123123123

    Correct me if i'm wrong

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

      It kind of was...

      actually there was a mistake in the part of code which compares numbers...

      Thanks for helping!!!

      • »
        »
        »
        »
        10 months ago, # ^ |
        Rev. 2   Vote: I like it -8 Vote: I do not like it

        What a coincidence! I made the same error and Maxymilian's test-case illuminated me. I won't forget you when I become a grandmaster. :)

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

Can someone explain div2 B to me , i didn't understand the editorial

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

Pls explain Div 2 B (with code if possible) I'm stuck:(

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

    Hi, In this question, listA is at some distance from listB and author guarantee that there is a solution i,e if you will add some non-negative number X then listA will become listB. Also, this means every number of listA will map out to some number of B after addition of this number X. Now, let's take first element of A (i,e A[0]) and look for it's all possible distances from listB by iterating over elements of listB. One of this distance is definitely guaranteed to be X. So, just iterate over all possible distance and for each distance, calculate new listA (let's call it listA') and compare listA' and listB (by sorting). Finally, output minimum distance for which listA' is equal to listB. Submission Link

    Hope this helps

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

      unable to understand this part

      ll curr_diff = (B[i] - A[0] + m) % m;
      

      why are we adding a +m before dividing by mod m?

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

        To avoid negative difference. Adding modulus M doesn't affect the significance of the current difference. For example, number "-1" and "2" both are same number with respect to modulus 3. Make sense?

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

More explain on Div.2 problem E, please.

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

    May be this will help: https://codeforces.com/blog/entry/72358?#comment-566415 I would like to see proof though, about independency of gathering and inversions.

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

      Could you please explain to me the formula in Endagorion 67338561

      ans += x * L - L * (L - 1) / 2 - ls;
      ans += rs - x * R - R * (R + 1) / 2;
      
      • »
        »
        »
        »
        10 months ago, # ^ |
        Rev. 2   Vote: I like it +3 Vote: I do not like it
        • $$$lh, rh$$$ — sets of positions of left and right parts of sequence.
        • $$$ls, rs$$$ — sums of all elements in corresponding sets.
        • $$$L, R$$$ — count of elements in corresponding sets. Also it is length of arithmetic sequences.
        • In first line $$$ls$$$ is first query in BIT from my explanation in linked comments section. Other stuff from first line is first sum of arithmetic progression: $$$ [x - L + 1, x] $$$
        • In second line $$$rs$$$ is second query in BIT from my explanation. Other stuff in second line is sum of second arithmetic progression: $$$ [x + 1, x + R] $$$
        • »
          »
          »
          »
          »
          10 months ago, # ^ |
          Rev. 3   Vote: I like it +3 Vote: I do not like it

          Thank you, but why do we have L * (L - 1) / 2 and R * (R + 1) / 2 here? In leff01's code (67434904), he has another way:

          left = left_am * mid - left - left_am*(left_am+1)/2;
          right = right - right_am * mid - right_am*(right_am+1)/2;
          
          • »
            »
            »
            »
            »
            »
            10 months ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            He don't include mid for both of ranges.

            $$$[x-L, x-1]\;[x+1, x+R]$$$
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone prove that editorial solution of div2C gives correct answer?

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

    Yes, I can. Consider the set of all beautiful integers. For example, 123123123 can be written as (123)*(10**(0)+10**(3)+10**(6)) So any beautiful integer in general can be written as (a1a2a3..ak)*(sum of powers of 10). Now, the key thing to realise is if the number a1a2a3...ak is lesser than the first k digits of the input number x, then the beautiful integer of the same length so formed is definitely less than x. This can be easily shown.

    Since we have to find y>=x, we start our search from the first k integers of x.

    Note again that if a1a2a3...ak is greater than the first k digits of x, then the beautiful integer so formed is definitely greater than x. This can also be shown similarly and easily.

    So we start our search from a1a2a3...ak, the first k integers of x. If the beautiful solution so formed is greater than or equal to x, we can print y. (We are sure that this is indeed the smallest, since any smaller and y definitely becomes less than x).

    If y is smaller, we add 1 to the number a1a2...ak and print the beautiful integer so formed. This is definitely greater than x and no number smaller than this is greater than x. Hence proved.

    If you have any doubt, feel free to post it.

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

      Hey man, can you please have a look at my last submission for this problem and tell me why WA is showing? Unable to figure out the bug. Thanks

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

Could anyone here help me figure out what's wrong with my solution for Div 2 (C)? I have tried to follow the editorial here.
Link.

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

    for (int i = 1; i <= n; i++) if (num1[i] > num2[i]) flag++;

    this part of the code is causing the error

    run this testcase: 6 3 427129 your solution — 428428 but the correct ans 427427.

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

      Yes, I figured it out. I was comparing the numbers stored in the arrays incorrectly.

      for (int i = 1; i <= n; i++) 
          if (num1[i] > num2[i]) 
              flag++;
      

      This is not the correct way to check if num1 > num2. Thanks!

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

i think the word 'ciclycally' is a russian word. as a non-russian speaker, i find the use of the word confusing. you should have used a better word, such as 'cyclically.'

edit: the typo was fixed. i don't think my comment warrants such many downvotes, i was pointing out the typo in a somewhat sarcastic way.

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

    that's not a Russian word, that's just a typo.

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

For Div2 C, we can take the first k digits as a number and repeat it for length n, and then add one to that number and repeat it again for length n . This is optimal and i know it works.

But i am unable to proof that why it'll always work, can anyone help me with a proof?

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

    Make new number with first $$$k$$$ digits same as given number.

    Firstly, check if new number ( with first $$$k$$$ repeated till $$$n$$$ ) is greater or equal to original number. If yes, then obviously print it.

    If it is not greater, then increasing the number formed by the first $$$k$$$ digits by one is the smallest increase which enables you to have a number greater than the original, since now your number has first $$$x$$$ ( depending on number of $$$9$$$s at end of the first $$$k$$$ digits ) digits same as original and next $$$k-x$$$ digits greater than original. So already, the prefix of first $$$k$$$ digits is greater than given number. Then repeat it to make answer till $$$n$$$ digits.

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

      Hey man, can you please have a look at my last submission for this problem and tell me why WA is showing? Unable to figure out the bug. Thanks

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

you have 300iq s

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

In problem B div2 I just generated all possible x's and took the most frequent one. Is that right? 67350595

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

I really liked 1269D. To me, the solution seemed very non-intuitive though. (Like I couldn't understand how that train of thought could originate in the first place).

One question I had about it was, wouldn't this chessboard coloring logic be applicable even if the heights columns were not in a non-increasing order? I'd like to understand why this logic would fail in that case.

Any help would be appreciated.

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

    1 0 0 1

    or

    1 2 1 1 2 1

    it's possible to get non-connected diagram.

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

      Ah I see! It was quite silly of me to miss that. Thanks for pointing it out. Btw, I still find the idea of coloring the diagram in white and black quite elegant. Would you happen to know if this is a well known idea (like are there other problems which use similar techniques) or did people come up with the solution on the fly during this round?

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

        I don't know another problems like this, but coloring board with chess order is common idea. Another idea with 1x2, 2x1 tiles is bipartite matching of graph with vertices as board cells and edges between cells that have common side. Its equivalent problems. Interesting thing about domino tilings is Aztec diamond. But have nothing common with div1B problem )

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

        Coloring chessboards and packing there some weird shapes is one of the most popular genres of mathematical olympic problems and packing dominoes into a 8x8 chessboard with two opposite corners removed is the most classical problem in it (which I learned in first half of my life)

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

I always look forward to contests with a single writer behind them and 300iq did not disappoint with this. The questions were really good !

How to solve the bonus question of $$$B$$$ ?

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

    Maybe peeking into other submissions might help.

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

I have written code for div2C as per logic: 1) First, simply repeat 1st K characters and compare 2) If new_string is >= old string, print it 3) Otherwise, look for the index from first K character (starting from last one) for which if you iterate over K-sequence of (index, index+k..), then old_str > new_str. If so, increase the character value at that found_idx and at other position in its K-sequence order. After this, make all character K-sequences in between found_idx and K to '0'. I couldn't find the flaw in above logic and thus couldn't see why am I getting WA. Test case on which it's failing is pretty HUGE itself. I looked for other test cases from accepted solutions but still got the correct answer. Can someone please help me out of this trauma? My submission Link

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

can anybody explain what will be the answer of this test case ,n = 3 ,m = 17,a = {2,4,7},b = {3,10,15},problem 1269B

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

Clarifying the editorial's $$$Div1B$$$:

Suppose you mapped the diagram to a chessboard, where the white cells count is $$$w$$$ and $$$b$$$ is the black cells count. We can see that the upper bound of dominoes we can put is $$$min(w,\, b)$$$. But what is the proof that we can always achieve it?

Let $$$a_i$$$ be number of available cells in the $$$i^{th}$$$ column. Starting with the original diagram, try always to place a vertical domino in a column i where $$$a_i>a_{i+1}+1$$$ (decreasing $$$a_i$$$ by $$$2$$$), or a horizontal domino on top of 2 columns $$$i$$$ and $$$i+1$$$ where $$$a_i=a_{i+1}$$$ and $$$a_{i+1}>a_{i+2}$$$ (decreasing both $$$a_i$$$ and $$$a_{i+1}$$$ by $$$1$$$).

Both of the previous $$$2$$$ operations will not change the property of $$$a_i\geq a_{i+1}$$$, and will not change $$$w-b$$$. If you can't do any of the previous 2 operations any more, then you have reached a configuration with values of $$$a_i$$$ being $$$t$$$, $$$t-1$$$, ..., $$$2$$$, $$$1$$$. In this configuration $$$b\neq w$$$, this means that $$$b\neq w$$$ from the beginning (So if $$$b=w$$$ from the beginning, you could have filled the entire diagram).

If you didn't fill the entire diagram, how can you still achieve $$$min(w,\, b)$$$? Assuming without loss of generality that the column with $$$a_i=1$$$ (the $$$t^{th}$$$ column) has a white cell, we can see that $$$w-b=\lceil \dfrac{t}{2} \rceil$$$. So if we kept putting vertical dominoes, we will end up with leaving exactly $$$\lceil \dfrac{t}{2} \rceil$$$ cells (the number of columns with odd $$$a_i$$$).

»
10 months ago, # |
Rev. 2   Vote: I like it -28 Vote: I do not like it

can any one tell me, what is wrong with with my code, i just did same as explain in bottom ? @link https://codeforces.com/blog/entry/72358?#comment-566338

it fails at 13th test case i didn't understand where i did mistake. my code ->

include

include<bits/stdc++.h>

using namespace std;

int main() { long int n,m,i,j,q=1; cin>>n>>m; long int a[n],b[n],c[n],temp[n],mim=1000000001; for(i=0;i<n;i++) { cin>>a[i]; } for(i=0;i<n;i++) { cin>>b[i]; c[i]=(abs(b[0]-a[i]))%m; temp[i]=a[i]; } sort(b,b+n); sort(a,a+n); sort(c,c+n); sort(temp,temp+n); for(i=0;i<n;i++) { q=1; if(i>0) { if(c[i]==c[i-1]) continue; } for(j=0;j<n;j++) { temp[j] = (a[j]+c[i])%m; } sort(temp,temp+n); for(j=0;j<n;j++) { if(b[j]!=temp[j]) { for(j=0;j<n;j++) { temp[j]=a[j]; } q=0; break; } } if(q==1) { if(mim>c[i]) mim=c[i]; } } cout<<mim<<endl;

}

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

Thank you for these contests

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

300iq can you please elaborate on how to solve problem E of Div2

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

Can anybody please explain me how to get second value for each k in div2 E how to do it with segment tree

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

    I guess you can initially have all values set to $$$0$$$. As you increase $$$k$$$, set $$$a[k]$$$ ( this array is the one on which segment tree is build ) to $$$1$$$. Then at every k, you have $$$1$$$s on some positions. I don't know how to do it, but now the problem is, given an array of $$$0$$$ and $$$1$$$, find minimum operations ( swaps ) to get all ones together. As editorial mentions, this value should be sum of indices of $$$1$$$s to the right of the median $$$1$$$ minus sum of indices to left of median $$$1$$$ ( think of it as right side $$$1$$$s have plus sign, and left side have minus sign ). Also, on each update, atmost $$$2$$$ signs will change, so you can handle sign change on update, and then keep track of the sum of the indices ( with sign ).

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

    I knew that it's possible to use segment tree, but I was unable to came up with it during contest.

    Then, after a while, I realized key observation: all times you add $$$k$$$ ! I know, it sounds ridiculous. But listen. You add $$$k$$$ <- this is last in sequence. In other words, it's biggest number. So, you don't have any number higher than $$$k$$$. According to inversions, the impact of including $$$k$$$ is number of all inversions with it. To calculate this impact, all you have to do is find all numbers less than $$$k$$$ at positions with higher indexes than $$$k$$$. But they all already less than $$$k$$$.

    This means, that if you hold in segment tree all numbers from 1 to $$$k$$$, your request is just: find all X that has index higher index of $$$k$$$.

    With segment tree, it's just sum of ones from (position of $$$k$$$)+1 to $$$n$$$.

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

    Oh, sorry, I thought about inversions. it was harder to me.

    About swaps with segment tree. Lets note $$$p_i$$$ initial position of 1 and $$$t_i$$$ position we want. Then total swaps:

    $$$\sum{\left|p_i-t_i\right|}$$$

    Why? Because it's useless to swap 1 with 1, so we just 'pack' them. Now, split into two sums:

    $$$\sum{\left|p_i-t_i\right|} = \sum\limits_{p_i<t_i}\left(t_i-p_i\right) + \sum\limits_{p_i\geq t_i}\left(p_i-t_i\right) = \sum\limits_{p_i<t_i}t_i - \sum\limits_{p_i<t_i}p_i + \sum\limits_{p_i\geq t_i}p_i-\sum\limits_{p_i\geq t_i}t_i$$$

    First and last sum is sum of arithmetic progressions. You can find them by formula. Other two are just sum using segment tree or fenwick tree.

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

      Ohh can you explain it more please. What is $$$t_i$$$ and what does mean 'pack'? Please )

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

        $$$t_i$$$ is target position. Look at following example:

        01234567890123456 // helper for indexing
        00100010001010010 // initial
        00000000111110000 // target
        

        Then $$$p = [2,6,10,12,15], t = [8,9,10,11,12]$$$. So, sum is

        $$$ |2-8|+|6-9|+|10-10|+|12-11|+|15-12| = \\ (8-2)+(9-8)+(10-10)+(12-11)+(15-12) = \\ (8+9)-(2+8)+(10+12+15)-(10+11+12) $$$

        I pick word 'pack' because you can imagine this by 0 — space, and 1 for example pens, and you just move leftmost towards center and rightmost towards center and they meet together.

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

          Hey, in case of even number of 1s you "pack" them towards which of the two medians?

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

            I pack towards best of two, calculate cost of both. It should work if indepentence is correct (I don't know proof).

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

            you can prove that both medians has same sum, using same argument that minimum should be median.

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

          you are the best) thank you) I got accept

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

      This helped me to understand it very well THANK U

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

What was the logic you all used in div2a i am having hard time understanding tutorail.its normal to not able to solve que i can solve a b sometimes but sometimes i have problems,

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

    There are two obvious solutions:
    First:
    check if number is composite and bruteforce.
    Second:
    Since you can output any answer you can conclude that 9*n 8*n is always a valid answer.

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

    If a — b = n, then we can rewrite a as (x+1) * n and b as x * n. In order for both (x+1) * n and x * n to be composite, we need n to be at least equal to 2.

    Basically, you can print every possible pair of type (x+1) * n and x * n as long as x >= 2 and (x+1) * n <= $$$10^{9}$$$

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

    Here is how I approached this problem, you are given an integer $$$n$$$ and you are asked to find $$$a$$$ and $$$b$$$ such that $$$a-b = n$$$.

    First thing that can come to mind is: let $$$a = n+1$$$ and let $$$b = 1$$$

    but the problem states that $$$a$$$ and $$$b$$$ must be $$$composite$$$ numbers (not prime and not $$$1$$$, or formally have at least one divisor other than 1 and the number itself) so $$$b$$$ cannot be equal to $$$1$$$.

    think of the case if $$$n$$$ is an even number, you know an even number is divisible by 2, you also know that $$$even+even=even$$$, therefore one way to solve the case if $$$n$$$ is even, $$$a = n + even$$$ and $$$b = even$$$.

    But be careful, we want $$$b$$$ to be a composite number so the even number we want to add cannot be $$$2$$$, let's try $$$even=4$$$

    this way we know that $$$a$$$ is divisible by $$$1$$$ and $$$2$$$ and $$$a$$$ itself, and $$$b$$$ is divisible by $$$1$$$, $$$2$$$, $$$4$$$.

    If n is an odd number, one way to solve it is $$$a = n + odd$$$ , $$$b = odd$$$, think of an odd $$$non-composite$$$ number, $$$9$$$ comes to mind, because $$$9$$$ is divisible by $$$1$$$,$$$3$$$,$$$9$$$.

    Also, if we add $$$9$$$ to $$$n$$$, we get an even number because we assumed $$$n$$$ is odd, and $$$odd + odd = even$$$, hence $$$a$$$ is an even number and is divisible by $$$1, 2 , a$$$ itself.

    67335704 here is my solution.

    Let's break down the author's solution, $$$a=9n$$$ and $$$b=8n$$$.

    For any value of $$$n$$$, you are sure that it is divisible by $$$1, 3, 9$$$ and whatever $$$b$$$ is you are sure that it is divisible by $$$1,2,4,8$$$.

    $$$9n$$$ and $$$8n$$$ were particularly chosen because $$$9n - 8n = n$$$ which satisfies $$$a - b = n$$$

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

Can anyone tell me what is wrong with dp approch in div 2 D https://codeforces.com/contest/1269/submission/67394114 I have first converted a[i] to a[i]%2 that is making the sequence 100110... 1 if odd 0 if even. Then I note compute dp[i] as the min no of squares up to column i that can go unfilled.For this I use the following observations, 1. we can use the full column of even length (dp[i]=dp[i-1] ) 2.if columns are of the form 111..m times (i.e all odd), if m is even then all the squares can be filled, if m is odd 1 square is not filled. 3.sequence of the form ( 1.. even times 0..1 ) can be completely filled.(you can take example of 3 2 2 3) Am I missing something??

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

Will an editorial for all problems on the actual ByteDance contest be posted?

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

In Div2 D, why do we have a contradiction?
Does the proof still work in this case?
2
1 1
I think it has an equal number of white and black cell.

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

    I think that it doesn't meet the request in the editorial "If all rows and columns are different".

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

      It's not required to be different prior to all deletions of dominos, is it?

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

Can anyone please tell why O(n2) solution doesn't work in Div2 B? Please have a look at my submission and help.

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

    O(n^2) submission works and your submission for the problem is accepted. What's wrong?

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

      It's not accepted. I'm talking about modulo problem!

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

        Because your soln is not O(n^2). Its O(1e14 * n)[Notice your outer loop] which would obviously give TLE even for small n.

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

        Oops sorry, I looked at the wrong row

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

Weak systests in Div2B. Some test cases where multiple x values existed, submissions have passed without taking the minimum of them. Example test case:

4 4
1 1 3 3
0 0 2 2

Here both x=1 and x=3 are valid and output should be x=1. But hacked submission outputs 3.

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

    What does hacked submission mean sire?

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

      Users with 1900+ rating can hack a submission even after the contest is over. It does not result in decrease of points of submitted code though.

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

Help me please, I'm able to implement brute force solution of the problems but not able to optimize it in limited time, how can I improve? [DIV 2]

»
10 months ago, # |
  Vote: I like it -27 Vote: I do not like it
#include <bits/stdc++.h>
#define ll long long
#define ibs ios_base::sync_with_stdio(false)
#define cti cin.tie(0)
#define pb push_back
#define N 400015
ll y=0;
struct table{
    int val,id;
};
bool cmp(table a,table b)
{
    return a.val>b.val;
}
bool isPrime(ll n) 
{ 
    // Corner case 
    if (n <= 1) 
        return false; 

    // Check from 2 to n-1 
    for (ll i = 2; i < n; i++) 
        if (n % i == 0) 
            return false; 

    return true; 
} 
using namespace std;//coded by abhijay mitra
#define watch(x) cout << (#x) << " is " << (x) << endl
int main()
{
    ibs;cti;
    int n;ll m;cin>>n>>m;std::vector<ll> a(m,0),b(m,0);bool Check=0;ll x;
    for (int i = 0; i < n; ++i){
        cin>>x;a[x]++;
    }
    for (int i = 0; i < n; ++i){
        cin>>x;b[x]++;
    }
    if(m==2){
        if(a[0]==b[1] and a[1] ==b[0]){
            cout<<"1\n";return 0;
        }
    }
    if(n==1){
        if(b[0]==a[0])
            cout<<0<<"\n";
        return 0;
    }
    for (ll i = 0;; ++i){
        if(a==b){cout<<i<<"\n";return 0;}
        std::rotate(b.begin(), b.begin()+1, b.end());
    }
}

it got rte in question B. I used vector rotation. Where is issue?

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

Can someone explain Div2 D, the domino problem?

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

In div2D/div1A, I understood the soln but what is the significance of "column lengths will be in sorted order"?Even if it's not sorted this algo shud work right?

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

For Div2 E. I can not get how to maintain the second answer. Who can explain more, thanks.

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

    Let $$$a_i$$$ be the number of $$$1$$$ after place $$$i$$$, $$$b_i$$$ be the number of $$$1$$$ before place $$$i$$$.

    You're going to work out $$$\Sigma_{i=1}^{n}min(a_i,b_i)*[place_i=0]$$$ while each time a $$$0$$$ changes to an $$$1$$$.

    It's easy to conclude that $$$a_i$$$ is non-increasing and $$$b_i$$$ is non-decreasing.

    As a result, there exists an $$$i$$$, which satisfies that for all the $$$j \leq i$$$, $$$min(a_j,b_j)=b_j$$$ and for all the $$$j>i$$$, $$$min(a_j,b_j)=a_j$$$.

    So just do a binary search to find $$$i$$$ (Or, according to the definition of $$$a_i$$$ and $$$b_i$$$ it is the median of all the $$$i$$$ that $$$place_i=1$$$), and the answer is $$$\Sigma_{j=1}^{i}b_i*[place_i=0]$$$+$$$\Sigma_{j=i+1}^{n}a_i*[place_i=0]$$$.

    You can work it out on a segment tree.

    This is my code and I hope it can help you more: 67425987

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

      Thanks very much!

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

      Can you explain how we do calculation after finding median i?

      I mean.. Okay, we got that we have to add to the answer sum of Ones before 0 (if 0 is before i) and sum of ones after 0 (if 0 is after i) for all zeros

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

        After finding median $$$i$$$ you realize that for all the $$$place_j=0$$$, if $$$j \leq i$$$, then the contribution of $$$j$$$ is $$$b_i$$$, else it's $$$a_i$$$.

        Consider that each time a $$$0$$$ changes to $$$1$$$.

        You can maintain it through the following steps: (suppose that $$$place_k$$$ changes to $$$1$$$)

        1) Let $$$a_j$$$ $$$(j \in [1, k-1]) = a_j + 1$$$, $$$b_j$$$ $$$(j \in [k+1, n]) = b_j + 1$$$.

        This can be realized on a segment tree.

        2) Erase the label $$$k$$$ in $$${a_n}$$$ and $$${b_n}$$$.

        To achieve this, you can maintain a $$$size$$$ on the segment tree node to show how many labels are still existing on the range that this node stands for.

        Then when you are going to add $$$1$$$ on a whole segment tree node, you can simply add the $$$size$$$ of the node to the $$$sum$$$ of that node and leave a lazy tag there.

        If you still have problems you may view my code above to better understand it.

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

In div2 D how to prove it cannot be less than minimum of both colors ? I did not got the editorial

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

I see a tag of "Graph Matchings" on DIV-2 D, how the problem can be solved using such an algorithm. I couldn't see any mention of it in the editorial though.

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

    All cells are node. Edges between adjacent cells. You get a bipartite graph. Find the largest matching in it.

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

Can someone please explain for Div2E how to calculate the second value(mentioned in editorial)? And why does it work(taking the median)? I understood the inversions part but unable to get the median thing!!

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

How DIV2 B can be solved in O(N)?

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

In problem B,isn't it b[i] or b[1] as stated in tutorial

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

How we can solve problem D using graph matching as given in tag ??

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

    All cells are node. Edges between adjacent cells. You get a bipartite graph. Find the largest matching in it.

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

      But there are too many cells so the time limit will exceed

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

        Using hall's theorem you can show that the maximum matching set will have the same size as the smaller of the two bipartite sets. So you don't actually need to solve the flow problem.

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

          Can you explain a little more?

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

            I mean that consider the graph you get as $$$G=(X+Y, E)$$$. Creating this graph and then getting $$$X$$$ and $$$Y$$$ is easy in $$$O(N+M)$$$ and since $$$O(M) = O(N)$$$ the result is $$$O(N)$$$. Now using Hall's Theorem you can say that the maximum bipartite matching will have a size of $$$min(|X|,|Y|)$$$. You don't need the actual coverings.

            As for why Hall's theorem is applicable, assume $$$X$$$ to be the smaller set with LOG. We can use induction on the size $$$A$$$ where $$$S$$$ is a subset of $$$X$$$. The base case is trivial, there must be one edge from the $$$S$$$. Now, notice that whenever we add a another node to this subset, it must add at least one new node to the neighborhood. Therefore, the proof is complete.

            Why must it add at-least one node? Well, I haven't been able to prove that part yet but I'm pretty sure it's related to being the smaller set.

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

Div 1.C — Div 2. E

The editorial says (or at least i understood this) that it's optimal to put the first $$$k$$$ elements together (consecutive) with the minimum number of swaps and the sort them (and because they are together we have to add the number of inversions), but why is this optimal?

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

The approach for Div2 D is very interesting. Just wondering can we use it for the case when size of domino is 1X3 or 3X1 (coloring the board in 3 colors and finding the minimum number of occurence of those colors)?

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

Can anyone tell me that where i can find the solution code by editorial for problem given above.

»
10 months ago, # |
Rev. 2   Vote: I like it -21 Vote: I do not like it

so weak pretests 300iq can you explain me what the fuck is this do you really think it's normal?

P.S. Я не лайко попрошайка, но блин, уже -12, я не ожидала о_О

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

Hi can anybody explain me DIV2 B problem.I still do not un derstand the editorial.(Please share your code) Thanks:)

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

I think I have a clear proof on 1269D, so I would like to post my proof here.

Without affecting the answer, we add '0' at the end of the histogram.

We define two operations:

  1. If the difference between neighbour two bars $$$ \geq 2 $$$, then delete vertical dominos to reduce the difference.
    Example: 8 7 3 1 -> 8 7 1 1 -> 8 1 1 1 -> 2 1 1 1
  2. Choose the rightmost two neighbour bars that have the same height. Delete the horizontal domino on the top.
    Example: 3 2 2 1 -> 3 1 1 1 -> 3 1 0 0

Repeatedly do the operation (1) and (2) until you can't. Note if no neighbour difference $$$ \geq 2 $$$ or $$$ = 0 $$$, then all neighbour difference $$$ = 1 $$$, which is "basic diagram" stated at the editorial. We then can just choose all dominos vertically on the "basic diagram".

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

Greate problem & contest Thank you

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

Div2 D:Domino for Young

Want to Know why this solution didn't work:

Iterate through the array and ans+=arr[i]/2.Basically making 2*1 domino column wise, if arr[i] is even then we can make arr[i]/2 2*1 dominos marking arr[i]=0 else there will be 1 block left marking arr[i]=1.If arr[i+1] is also odd then 1*2 domino can be made else it can't be made.

1269D-13 - Домино для молодыхHere is my code:https://codeforces.com/contest/1269/submission/67506647

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

How to prove that if (a + x) mod m = b then x = (b — a) mod m

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

    $$$a + x = b + km$$$ for some integer $$$k$$$

    Subtract $$$a$$$ from both side

    $$$x = (b - a) + km$$$ for some integer $$$k$$$

    $$$x = p + qm, (b - a) = r + sm$$$ for some integer $$$p, q, r, s$$$ such that $$$0 \le p, r \le m - 1$$$.

    $$$p + qm = r + (s + k) m$$$

    Subtract $$$qm + r$$$ from both side

    $$$p - r = (s + k - q) m$$$

    $$$s + k - q$$$ is integer, and by line 4 $$$-m+1 \le p - r \le m-1$$$. So only solution is $$$p - r = 0$$$.

    Add $$$r$$$ for both side

    $$$p = r$$$

    $$$x \mod m = (b - a) \mod m$$$

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

      thx

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

      ko_osaga hello I have a doubt why didn't you take mod m both sides in 2nd step only

      x = (b-a)+km;

      take mod m both sides

      x%m = (b-a)%m

      This gives us the same result is there is something wrong in my way?

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

For Problem B, I suppose it's an n^2 solution which runs at max 4*(10^6) times, why is it wrong? Please explain (http://codeforces.com/contest/1269/submission/67659382)

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

Can anyone help where i went wrong ?? https://codeforces.com/contest/1269/submission/67673061

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

Another way of thinking 1268E. Consider the problem is: given the start edge, how many possible increasing paths from that start edge? If we can answer this question, then the solution of starting from a vertex u is the sum of solutions of edges that are adjacent to u.

For a given path e, it is easy to find all the feasible next paths of e. Namely, if the weight of e_2 is larger than e_1, then e_1 -> e_2 is feasible. The relations, such that e_1 -> e_2, form a new graph, which is DAG. Thus, it is trivial to find a solution to the new problem.

Note that the edges should be directional. You should convert the original undirected edge to two directed edges.

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

Can someone explain to me the idea behind Domino for Young?(Problem D Div 2). Can someone tell me why this greedy approach fails as well? https://codeforces.com/contest/1269/submission/68692876

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

    This is a small test case with which you can see why your solution is incorrect. If I did not misunderstood your program, it will output 7, yet the answer is 8.

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

      Thanks for the test case. Can you explain to me what the editorial exactly says? It is a bit difficult to understand

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

        Editorial for that problem has two parts:

        1. Proving that the Young diagram can be completely tiled with dominos if and only if the black and white cells are equal in it.
        2. Proving that a Young diagram with different number of black and white cells can be tiled with min( the number of white cells, the number of black cells) dominos (maximally).

        Which part do you have trouble with?

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

          I'm fine with the general coloring argument. What I do not understand very clearly is the first part. The second part was pretty intuitive.

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

            That part has further two part:

            1. If the Young diagram can be completely tiled with dominos, then it has equal number of black and white cells in it.
            2. If a Young diagram has equal number of black and white cells in it, then it can be completely tiled with dominos.

            Part 1. is pretty easy, so the editorial does not elaborate it: However you place a domino it will occupy one black and one white cell, so if you've tiled all cells with dominos, it is necessary that you have as many white cells as blacks cells which both equal the number of dominos used for the complete tiling.

            Part 2. is harder: we first notice that if we delete two equal columns from the diagram and we can tile the resulting new diagram, then that means we can tile the original too. Let's call the new diagram D2, the original D1.

            We can tile D1 the same way as D2 (as they're largely the same) with these two differences:

            1. The deleted equal-height columns in D1 are not in D2. these we can tile with horizontal dominos. (If the columns have height h, we need h horizontal dominos)
            2. It is possible that in D2's tiling a horizontal domino is placed between two columns which are not neighboring in D1 (let's call this domino the fractured one), because in D1 the deleted two columns is between the in-D2-consecutive columns. This is not a problem as we can just shift by 1 the horizontal domino we used to tile the deleted columns (which is at the same height as the fractured one) and put the fractured domino at the empty space at the same height.

            We can say the same thing about rows of equal length, that is: It is also true that if we delete two equal rows from the diagram and we can tile the resulting new diagram, then that means we can tile the original too. (This can be shown the same way as with columns)

            So, now we start to reduce our diagram which has equal number of black and white cells. After we delete equal rows, then equal columns, then again all equal rows, then again equal columns and so on, what do we get? For the resulting diagram we can't get anything but a "basic" diagram, as anything else has either two equal rows or two equal columns. However, we also can't get a "basic" diagram, as every basic diagram have different number of black and white cells, while our row/column deleting operationg preserves the difference of the number of black and white cells. So we can only end with "nothing" which can be completely tiled with dominos (with 0 domino), so consequently the original diagram can also be tiled completeley.

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

I solved three last problems (div1-CDE) during a live stream, https://youtu.be/RrzIwj5k6cY

I don't like graph problems but those weren't that bad and ugly :D

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

can someone please tell me the proof of B? I mean why the list generated will also satisfy other Bj(for j>1)?//ignore->done

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

Hi All. I wanted to know where was my algorithm failing for Div2B Modulo Inequality.

I tried it this way: 1. Get the frequency of elements in array A (store in map ma);

  1. Get the frequency of elements in array B (store in map mb);

  2. Get all unique elements from array A and B in a set s;

  3. For elements in A that are not in B, keep their freq in mb as 0;

  4. For elements in B that are not in A, keep their freq in ma as 0;

  5. First check if no additions are to be made (using map mc);

  6. If changes are needed, then the frequency list of B must be a rotated version of frequency list A.

  7. Once the index where the rotation starts is detected, get the corresponding element from the map ma.

But this seems to be failing in Test Case 5.

I understood the given editorial, but wanted to know why was this approach failing? Any help / edge case please?

Link to my submission: here

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

There is something missing in the solution statement in problem C. If the input is 6 5 765693

If we change first K elements according to the solution statement then we get 765707 But if we do just a[i]=a[i-k] if i=k+1 then the answer is

765697 which is more optimal? can anyone explain please!

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

This editorial is shit. Just the approach , who will prove why the solutions are correct.

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

Problem D: Domino For Young: the solution works even if we don't have non-decreasing heights. So why put that as an additional useless condition?

300iq

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

and add values at the left and add the right with different coefficients.

What does this line mean in the editorial for 1269E-K Integers?

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

Can anyone tell what is wrong with my solution?

86348075

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

https://codeforces.com/contest/1269/submission/88915000 Can someone please tell me the issue with this code. I have trying to debug it for hours now. but couldn't find the error. The idea is very similar to that of editorial. Please can someone tell me what's the error?