physics0523's blog

By physics0523, history, 5 weeks ago, In English,
Tutorial is loading...

Jury solution: 85699387

Tutorial is loading...
Jury solution: 85699884
Tutorial is loading...
Jury solution: 85699939
Tutorial is loading...
Jury solution: 85700178
Tutorial is loading...
Jury solution: 85700334
Tutorial is loading...
Jury solution (Solution 1): 85700515

Jury solution (Solution 2): 85700518

Tutorial is loading...
Jury solution: 85700669

Feel free to share your approach here!

 
 
 
 
  • Vote: I like it
  • +134
  • Vote: I do not like it

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

My first submission for problem A in C++ was

ceil(1.0 * n / 2) and got WA. Does anyone have any idea what is wrong?

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it -61 Vote: I do not like it

    Why the downvote? Same is written here

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

      Because here 1.0*n is evaluated first, the result of which is a float value and the divison of this floating value with 2 (integer type) results in a floating value. Hence, there is no precision loss due to divison.

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

    You have to use (int)ceil(1.0 * n/2), because large values will be in Scientific floating-point notation

    Try n = 1000000000, it outputs "5e+008"

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

    when n = 10^8 it will produce 50000000.0000 something like this but correct answer is 50000000

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

    For some reason, a lot of people use the ceiling and floor function for libraries. There are many ways to mess up when doing this. I personally find it a lot easier to just use the fact that programming languages round down when dividing. Thus, to floor a/b you can do a/b and to ceiling a/b you can do (a+b-1)/b

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

      Totally true. I used ceil once in Problem A and it didn't get accepted. I was not able to solve A in that contest. Since then I'm never using ceil.

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

    At situations like these it's best to do (n + 1)/2

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

    Here's a trick for calculating ceil of (a/b). Just do (a+b-1)/b. No, need to confuse yourself with ceil functions.

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

    I also got wrong answer same way...you can use (n-1)/2+1 for avoid ceil()..

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

    See the link for better understanding Click here...

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it -11 Vote: I do not like it

    bro, correct way to write ceil function is ceil((1.0 * n)) as this will convert our no. into floating variable and here the ceil function works properly hope you got my point :)

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

    One should always point out that that's not the way one spells "Phalange" ;P

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

      Dude, you lost the whole joke.
      The whole point of the name is for fake identity theft. Spelling it right is not actually "right" (P.s if you are not friends fan, drop it)

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

    You can use : double n; cin>>n; cout<<fixed<<setprecision(0)<<ceil(n/2);

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

    Never trust ceil function of C++. It incurred me wrong submission many times.

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

    just write n/2 and it will work without any problem. Also declare n as an int.

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

    1
    99999999
    5e+07

»
5 weeks ago, # |
  Vote: I like it -44 Vote: I do not like it

I don't like the problems which can be done without using functions or loops

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

    Try adding and subtracting using loops then and wrap these loops inside a function.

»
5 weeks ago, # |
  Vote: I like it -73 Vote: I do not like it

Problemsetting might not be the job for you.

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

It shows the message that "You are not allowed to view the requested page" when trying to access the jury solutions.

»
5 weeks ago, # |
  Vote: I like it -91 Vote: I do not like it

Pathetic and Confusing problem statement for problem B. Shitty Contest

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it -9 Vote: I do not like it

    Problem B was pretty beautiful to my taste, even though I couldn't solve it,overall the questions were good.

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

    For problem B I would have to agree the problem statement was pretty confusing, but others were fine.

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

      ya the problem statement confused me too.. after getting the solution it was very easy

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

    Yeah I had a hard time understanding how a shape spread in 2 rows in a calendar with x columns can be compared with the same shape spread in 2 rows in a y columns calendar

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

Link for the solution codes are not working right now ... please fix them.

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

Can someone elaborate problem D's editorial?

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

    The idea is to fill out as many diagonals as possible, where each diagonal could wrap around the left/right sides. Filling in a diagonal increases each $$$R_i$$$ and $$$C_j$$$ by one. For a fully complete diagonal, $$$max(R) = min(R)$$$ and $$$max(C) = min(C)$$$, hence $$$f(A)=0$$$ if $$$k \% n = 0$$$. For an incomplete diagonal, you get $$$max(R) = min(R) + 1$$$ and $$$max(C) = min(C) + 1$$$, so $$$f(A)=2$$$.

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

      what does this means "each diagonal could wrap around the left/right sides??

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

        Wrapping around the left/right sides means that if the diagonal would go off the right side, it would continue on the left side. I think a visual example is the best explanation:

        Step 0:

        00000
        00000
        00000
        00000
        00000
        

        Step 1:

        10000
        01000
        00100
        00010
        00001
        

        Step 2:

        11000
        01100
        00110
        00011
        10001
        

        Step 3:

        11100
        01110
        00111
        10011
        11001
        
        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it +4 Vote: I do not like it

          Thankyou so much.. got it now

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

            i am still now getting...what if k%n is not zero

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

              if k%n is not zero then the answer is always 2. e.g. in case if k=4 and n=3 using diagonal filling you will get:

              110

              010

              001

              you can try out the combination with different numbers to prove this inductively.

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

          Thank you! This was very helpful than the editorial.

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

          SO much better than the editorial. Thanks :)

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

            Even hints will be better than the editorial given for the problem D

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

          How did you get that intuition tho? Wrap around diagonals seems a notch above any intuition I got. The closest I got to is filling out the closest diagonal stripe in the grid —

          111000
          111100
          111110
          011111
          001111
          000111
          

          Only later did I realise that it was wrong.

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

            The diagonals aren't really the important part here, it's just easy to construct that way. These matrices are equivalent:

            1000    0010
            0100    1000
            0010    0001
            0001    0100
            

            Think of it like filling a chessboard with rooks. If you place the first rook at $$$(r, c)$$$ , then you are left with $$$n-1$$$ rows and $$$n-1$$$ columns open (this is equivalent to 1 row and 1 column with a sum of 1 and $$$n-1$$$ rows and $$$n-1$$$ columns with a sum of 0). Since we're trying to minimize the difference in max/min sums, it's better to place the second rook on an open row and column. This will leave you with $$$n-2$$$ rows and $$$n-2$$$ columns. Keep following this pattern, and you'll end up with $$$n$$$ rooks on the board.

            • »
              »
              »
              »
              »
              »
              »
              6 days ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              So after filling in n rooks (as per the finding open column open row method), if k is greater than n, how would the remaining rooks go into the board? Or they could just be filled randomly?

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

                You would treat the $$$n$$$ spaces that the first rooks take up as unavailable spots, then place the next $$$n$$$ rooks in the same way as the first $$$n$$$ where only 1 new rook per row and 1 new rook per column. The important part is that you don't place 2 on the same row/column when they're part of the same "rook group".

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

    The following is not the way written in the editorial, but I have done it in my solution. Firstly, lets observe that if $$$k$$$ is divisible by $$$n$$$, the answer is $$$0$$$, and when it is not, the answer is $$$2$$$.

    Proof

    Now, how to fit the integers?

    What I did was first insert $$$1$$$s in indexes $$$[1, 1], [2, 2], ...., [n, n]$$$.

    In the next iteration, I inserted $$$1$$$s in indexes $$$[1, 2], [2, 3], ...., [n, 1]$$$

    Like this, we have $$$(k / n)$$$ iterations.

    I had put the extra $$$(k$$$ % $$$n)$$$ 1s simply as if it was the $$$(k / n) + 1$$$ th iteration, and only the first $$$(k$$$ % $$$n)$$$ 1s need to be inserted.

    My submission for reference: 85648287

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

      I didn't understand how you put remaining k%n one's please explain

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

        We put the ones in $$$k / n$$$ iterations, and thus the remaining ones will be $$$k$$$ % $$$n$$$. Note, over here the answer is $$$2$$$. The remaining ones should be lesser than $$$n$$$, because if not, then we could have added another iteration to use the $$$n$$$ ones. As the remaining ones are lesser than $$$n$$$, it means that they are lesser than the number of rows and columns. Thus, we iterate for the first $$$k$$$ % $$$n$$$ rows and columns, in the next iteration, and initialise that point $$$a[row][col]$$$ to $$$1$$$.

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

          There is no need to do seperately for k/nand k%n we can fill the matrix in only one loop going from [1,k]

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

            Yes, but don't you think the implementation will go for a toss? I am not telling you that my solution is the best, just telling you from my perspective, I code a solution which is the easiest to implement.

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

    That formular is wrong, isn't it? $$$f(A)=2(1^2+1^2)$$$

    I implemented AC that as

        int ans=0;
        if(k%n!=0 && n>1)
            ans=2;
    
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It says f(A)=2. Which is the result of (1^2+1^2). Correct me if I got it wrong.

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

        It says f(A)=4. Which is result of 2*(1^2+1^2)

        Or what is the 2 good for?

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

          Not logical but grammatical mistake.

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

          No, he means to say that f(A)=2, which comes from 1^2+1^2, that's why the brackets. The brackets are not indicating multiplication.

»
5 weeks ago, # |
  Vote: I like it +54 Vote: I do not like it

I think B and C should have been swapped. Thanks for fast editorial though.

»
5 weeks ago, # |
  Vote: I like it +79 Vote: I do not like it

I think D was little bit similar to 1360G - A/B Matrix and thank you for a nice contest.

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

    I actually copied some code from that problem when the answer is 0

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

    That's why i was able to do this problem otherwise it would be hard to come up with such algorithm during contest.

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

    Little bit? Dude for k%n!=0 you just add one for loop and you get AC.

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

    I need a little help here. I do remember solving that problem A/B Matrix. I read that question again now and I cannot figure out how to solve it. I have no clue how I had up solved. It kind of made sense when I saw the explanations but now its just gone. This is my problem. I solve problems on various judges on various judges but I forget topics too soon. Can you tell me how you remember those ideas? Or do you make notes of these? Or that is what your mind tells you because you have practiced a lot of similar questions? Regards.

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

    Wow man you have such a nice memory XD I think this is the third time I have seen you remembering similar old problems. No offence tho :)

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

pattern in questions!

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

One of the Best editorial for beginners like me.

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

I know it's too much to ask from anyone , but i will be highly obliged and grateful to the one who will look at my submissions of D to see why it fails to pass test cases . My submission link : https://codeforces.com/contest/1371/submission/85694260

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

    testcase
    4 7

    your answer

    5
    1100
    1100
    1010
    0001
    

    correct answer

    2
    1100
    0110
    0011
    0001
    
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

      Thanks a lot man! i understand now . Have a great luck and wonderful day/night ahead ! :)

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

Could E be solved, under the same constraints, if P was not prime ? I'm curious about it.

  • »
    »
    5 weeks ago, # ^ |
    Rev. 7   Vote: I like it -38 Vote: I do not like it

    if $$$p$$$ is not prime, you should replace it with the minimum integer $$$k$$$ such that $$$k!$$$ is a multiple of $$$p$$$
    upd: nvm, it's wrong

    • »
      »
      »
      5 weeks ago, # ^ |
      Rev. 3   Vote: I like it -17 Vote: I do not like it

      reasoning
      the answers are such $$$x$$$ that some $$$P[i]$$$ can be chosen in $$$\geq k$$$ ways
      you can prove that, if this condition is true, for $$$1 \leq y \leq k$$$, some $$$P[i]$$$ can be chosen in $$$y$$$ ways, so $$$f(x)$$$ is a multiple of $$$k!$$$
      upd: nvm, it's wrong

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

though i suck at patterns and constructive algos , but still managed some positive delta ....xD P.S — thank you for the contest ! @physics0523

»
5 weeks ago, # |
  Vote: I like it +77 Vote: I do not like it

Div2 rounds are now tending towards Div3! who else feels same?

»
5 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

Question B should have been better explained

»
5 weeks ago, # |
  Vote: I like it +23 Vote: I do not like it

To be honest, felt like a div3. except the last problem. For others, no. of submissions is almost same as on a div3.

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

    You can't just compare no. of submissions in a div3 contest and a div2 contest. In a div2 contest there are more high rated coders than in div3 contest. The expected rank of a 1500 rated coder in Codeforces Round #654 (Div. 2) was 4299, and his rank would be 2894 in the contest Codeforces Round #650 (Div. 3)

    Problem is easy, coders are not very skilled, no of submissions are X. Problems are harder, coders are also better skilled, the problem might get a similar number of submissions.

    I used this website to calculate expected ranks.

    To compare the div3 rounds and div2 rounds, compare their problem difficulties, not no. of submissions.

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

In C's editorial shouldn't it be m<=min(a,b) rather than m<min(a,b)?

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

    yeah, i am thinking about that. it should be m <= min(a, b)

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

    You are correct for 8 3 4 3 answer should be "YES".

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

Why can't someone who knows English go over the problems and correct bad translations? It's so hard to read these problems with so many out of place commas, and completely messy sentences.

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

Editorial Problem E1 You can find the value of f(x) by the following simulation:

First, let v={the number of enemies they have strictly less than x candies}, ans=1. Then do the following steps for i=x,x+1,...,x+(n−1). v=v + {the number of enemies they have exactly i candies} ans=ans∗v v=v−1

Is it just me or was this part not really that intuitive?

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

    Yeah,
    I still haven't been able to fully understand the Editorial of E1.
    I understood the statement by seeing some solutions but the reason it works is still a mystery to me

    Found a good explanation https://codeforces.com/blog/entry/79624#comment-654544

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

    for a give n x we are calculating all permutations v = all value less then x we can always put all v values in first place x could always defeat these values and will become x+1 now in second position e can select v -1 as out of v we have already put 1 value at first place but, we can also put those values which are equal to x+1 thats why for x+1 we added v += the num of enemy that has exactly x+1 candies. so we should multiply our ans with this num thatis ans = v*(v-1 + k) where k is num of enemies that have exactly same candies as x+1 and v is numbver of candies less then x, and so on.

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

I did the same thing that's mentioned in the editorial for E1. But I am getting WA for test 5. Submission.

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

problem B was little difficult to understand

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

Can someone explain C with examples? And what tags do these types of problems come under?

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

    Well, check the tags in the problem!

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

    Notice Second Type of guest always consume the one which is small in quantity. So if v > c then only chocolate will be consume by Type 2 guest or if c > v then only vanilla is consume and after consuming either the inequality v > c or c > v which one is there will still hold true. So if min(v, c) >= m then we can always allocate 1 cookie to each type 2 guests.

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

      Thank you, that helps!

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

        hello

        In C part I used :

        if(Math.min(a,b) >= m && Math.max(a,b) >= n){

        System.out.println("Yes"); 
            }
            else{
                System.out.println("No");
            }

        and got a wrong answer. Could anyone please tell me.

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

          Firstly, a + b should be greater than or equal to m + n. So, check that first. The second condition inside the if statement is not needed. See the above comment by nicknamee12 for explanation.

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

Finally understood B, thanks!

»
5 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

At least provide some explanation for problem D. We can see the other's submission if we want to see code.

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

    You have to note the pattern. I will explain this by an example.

    For k <= n it is simple : We have to fill only along the diagonal.

    For k > n :

    One thing that is sure : Putting 1 along diagonal is always optimal choice to minimize the final ans.

    Step 1. Fill the diagonal

    Opera-Snapshot_2020-07-02_192810_etc.usf.edu.png

    Step2 .

    Opera-Snapshot_2020-07-02_192810_etc.usf.edu1.png

    Step 3. See the pattern

    Opera-Snapshot_2020-07-02_192810_etc.usf.edu3.png

    Step 4. We will repeat what we have done in step 2, and step 3 till we still some entry to fill.

    Opera-Snapshot_2020-07-02_192810_etc.usf.edu4.png

    Repeating pattern :

    Opera-Snapshot_2020-07-02_192810_etc.usf.edu5.png

    Repeating pattern:

    Opera-Snapshot_2020-07-02_192810_etc.usf.edu6.png

    And finally :

    Opera-Snapshot_2020-07-02_192810_etc.usf.edu7.png

    Trick that I use to print is r-c (or c-r) is constant for a particular diagonal.

»
5 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

Any reason for making problem C around the same difficulty as a typical Div2 A?

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

In D there should be either (1^2 + 1^2) or 2 * 1^2, not 2 * (1^2 + 1^2).

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

My poor brain still didn't understand the solution to problem B. Could anyone be kind enough to explain it a bit more clearly?

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

problem C was fantastic for me.I spended too much time for it.when I finded it's solution I just surprised.

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

The problems were great. I thought C's solution would be much tricky..But now i find that I should have thought about it for a little more time..lol

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

First 4 problems felt more like div3 contest only maths and implementation kind. Or may be I am improving.

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

    You are improving...

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

    How can you judge a problem without taking part in actual contest.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Judging a problem without taking part in contest
      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        solving a problem after the contest is much easier than during the contest. Have a look at problem C, it seemed difficult to most of the people appearing for the contest but after upsolving they found that very easy.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it +10 Vote: I do not like it
          @aryan12 means solving after the contest but with the below constraint
    • »
      »
      »
      9 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I had registered for the contest. But due to some techincal errors I was unable to participate in the live contest. But I solved the problems later without watching the solutions. And I was giving my opinion about the contest and about the level Div2 actually is.

»
5 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

Felt like giving an Aptitude test!

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

    Yes, At least for the first 4 problems Never thought pattern recognition and printing will help me solve my firsts Div2 D problem :D

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

https://codeforces.com/blog/entry/79541?#comment-654173 This single comment has a better explanation for A, B, C than this editorial

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

    lol , how's that even an explanation?

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

      Just the same way how the below code is an explanation ~~~~~ let p=0 , q=0

      for i = 1..k
      
          Change A[p+1][q+1] into 1
      
          let p=(p+1) , q=(q+1)%n
      
          if(p==n)
      
              let p=0 , q=(q+1)%n

      Total complexity: O(n2) ~~~~~

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

Can Any One Explain me Solution of problem:E1? Because I am still not able to understand it through Editorial. Please Explain if You know .

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

    How we can find the value of f(x)???

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

      My reasoning was: Sort $$$a$$$. Fix $$$x$$$ $$$(1 \leq x \leq 2000)$$$. Lets see how many elements we can pick to be $$$P_0$$$ in a valid permutation. Find the last $$$i$$$ such that $$$a_i \leq x$$$. Then we can let $$$P_0 = a_0 \text{ or } a_1 \text{ or } ... \text{ or } a_i$$$. Thus there are $$$i + 1$$$ ways to pick $$$P_0$$$. To pick $$$P_1$$$ we do the same thing, i.e., find the last $$$i$$$ such that $$$a_i \leq x + 1$$$. Then we can let $$$P_1 = a_0 \text{ or } a_1 \text{ or } ... \text{ or } a_i$$$ except that we used one of these elements in choosing $$$P_0$$$. Thus there are $$$i + 1 - 1$$$ ways to pick $$$P_1$$$. Repeat this process for each $$$j < n$$$. If you get to some $$$j$$$ such that the number of ways to pick $$$P_j$$$ is divisible by $$$p$$$, then $$$x$$$ is not valid. Otherwise it is valid. The time complexity is $$$O(\max(a)n\log(n))$$$. This definitely won't pass E2 though.

      Edit: My contest code (disregard the freq array, it is unused): 85694840

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

        I have done the same thing as you. Can you tell me what is wrong with my code?

        https://codeforces.com/contest/1371/submission/85673827

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

          probably overflow? You never modded your ans variable, but it can be as big as $$$n!$$$

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

            Lol you're right...was so close to solving 5 for the first time :(

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

        Thanks for sharing your approach mate...idk why but was struggling to understand the editorial...I found your approach more insightful. Thanks. Appreciate it! :)

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

        You can find the minimum x such that f(x) % p != 0, then you can do binary search on your same approach for maximum x. And print from minimum to maximum.

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

          Yep that's the editorial's first solution for E2. The editorials $$$C_i(x)$$$ function is the number of ways to choose $$$P_i$$$ if the starting amount is $$$x$$$. I implemented it and it works in $$$O(\log(1e9)n\log(n))$$$ (~100ms).

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

            During solving this question on practice. I just guessed(weak guess) that maybe the answer would be a continuous segment. So, did a binary search. Still, not understanding why it worked?

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

              Its because of these two simple observations that the editorial states:

              $$$1.$$$ For each $$$x$$$, for each $$$i$$$ $$$(0 \leq i < n - 1)$$$, $$$C_i(x) \geq C_{i + 1}(x) - 1$$$, and $$$C_n(x) \leq 1$$$.

              $$$2.$$$ For each $$$i$$$ ($$$0 \leq i < n$$$), for each $$$x$$$, $$$C_i(x) \leq C_i(x + 1)$$$.

              From $$$(1)$$$, its clear that if $$$C_i(x) \geq p$$$ at some $$$i$$$, then there must be some $$$j \geq i$$$ such that $$$C_j(x) = p$$$.

              Since $$$p$$$ is prime, $$$p \mid f(x)$$$ if and only if $$$p \mid C_i(x)$$$ for some $$$i$$$ $$$(0 \leq i < n)$$$. I think this is called Euclid's Lemma.

              Thus from $$$(2)$$$ it is clear that $$$f(x) > 0$$$ and $$$p \mid f(x) \implies f(x + 1) > 0$$$ and $$$p \mid f(x + 1)$$$. Therefore there will be a smallest value $$$mn$$$ such that $$$f(mn) > 0$$$, and there will be a smallest value $$$mx \geq mn$$$ such that $$$f(mx) > 0$$$ and $$$p \mid mx$$$ and each $$$x \geq mx$$$ is not good. Thus binary search works. The answer is just the range $$$[mn, mx)$$$.

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

                I can`t understand the first condition.

                suppose x = 3 and i be 2, then power at i=2 will be 5, so C(i,x) will give how many values are there less than or equal to 5, suppose this value is 10, out of this 2 have already been used at index 0 and 1 so value should be 8.

                Now at i+1 we will have value 6 and then we will ask how many values are there less than or equal to 6, this will incude all the values less than or equal to 5 and the values equal to 6, let it be 15 (10+5(freq. of 6)), as now 3 value have been used value value here will be 12

                so we have C(i,x) = 8 and C(i+1,x) = 12, then how is the above condition satisfied ?

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

        Thanks a lot, for some reason I wasn't able to understand this via the official editorial. You saved me from a headache :P

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

        Ha, thank you! Good explanation.

        I'm trying to understand the editorial implementation now. But I can't figure out what the bk array means. Can someone give me an intuition?

      • »
        »
        »
        »
        2 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Could you please explain more clearly?I didn't understand why did you take x in such a way?

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

Can someone please help me with this submission for E1. It gets WA on test 9.

EDIT : I found the mistake. I was using set data structure earlier to get the count of elements less than or equal to $$$x+i$$$ which is wrong as it only stores unique elements and thus might give me wrong count values in case of duplicates.

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

Can anyone figure out what's wrong with this solution? (Problem D). It's showing WA on Test 3 but I am not able to figure out why. https://codeforces.com/contest/1371/submission/85682293

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

how can one arrive to the approach used in problem D. I mean is it really too intuitive? If yes, then can anyone share similar problems for practice.

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

    My idea was to flatten the board into a line of length $$$n^2$$$ and spread the ones "evenly" across the grid. That is, put a one at positions $$$0 \bmod n^2, (n + 1) \bmod n^2, 2(n + 1) \bmod n^2, ..., (k - 1)(n + 1) \bmod n^2$$$. Then you can easily convert the linear position to an $$$(r, c)$$$ coordinate by the formula $$$coord(x) = (x / n, x \bmod n)$$$. I didn't prove it rigorously, but it got AC: 85675022

    I believe a similar technique can be used to solve this problem: https://codeforces.com/problemset/problem/1360/G

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

      Thank you gentleman for this brilliant approach, now I am wondering how to prove and why this works. If possible can you please elaborate? Thanks a lot.

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

        One. No square will be hit twice using this method, and all $$$n^2$$$ squares can be hit if needed (i.e. when $$$k = n^2$$$).

        Proof: Since $$$\gcd(n + 1, n^2) = 1$$$ (easy to show, I hope you can figure it out), the method will hit exactly $$$\frac{n^2}{gcd(n + 1, n^2)} = n^2$$$ before returning to its initial position (0), so the claim holds. This formula follows from a theorem of group theory which states that for any positive integer $$$k$$$, for each $$$x \in \mathbb{Z}_k$$$, the smallest integer $$$d$$$ such that $$$d \cdot x \equiv 0 \pmod{k}$$$ is $$$d = \frac{n}{\gcd(x, n)}$$$. An equivalent way to say it is $$$d$$$ is equal to the number of distinct elements in $$$\mathbb{Z}_k$$$ you get by repeatedly adding $$$x$$$ to itself modulo $$$k$$$. This theorem appears surprisingly frequently on Code Forces for some reason (probably due to its relation to cycles and permutations).

        Two. I'm still not sure how to rigorously prove that this method minimizes $$$f(A)$$$ ... Im guessing it has to do with the fact that also $$$\gcd(n + 1, n) = 1$$$.

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

Shouldn't it be $$$m \le min(a,b)$$$ for problem $$$C$$$?

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

In E2 for solution 1 :

"if C_i(x) exceeds p, then there will be some C_j(x) = p as C_i(x) decrements by at most 1".

Why is this necessary that some C_j(x) will be equal to p?

what if C_i(x) does not decrease but only increase? Can someone explain?

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

    It has to decrease towards the end. If there was no constraints on choices at each turn and you had 5 options you end up with 5*4*3*2*1 choices. The constraints can never increase the number of choices for any turn but can reduce them so any 'good' x will ensure that you never have p or more choices on any turn.

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

    Cn(x) has to be one bcoz total n choices. So,if some c_i > p and each c_j can atmost decrease by one then p+a....p.....1

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

The problems were wonderful. I loved them all.

However Ruby 2.7.1 (which was upgraded from 2.0.0 recently) is too slow on Codeforces. My O(1) (I mean, O(t)) solutions don't pass! https://codeforces.com/contest/1371/submission/85638755 Same code with same input passes in 150ms on Macbook Air and 75ms on AtCoder!

It seems that any Ruby2.7.1 submission takes 900ms at least. (Even if 1 line do-nothing code) So I guess Ruby2.7.1 on Codeforces has somewhat wrong settings.

And I found that previously passed code makes TLE now with Ruby2.7.1.

Please let me know if any better place to report bugs to Codeforces. Thanks!

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

Shouldn't it be m <= min(a,b) in place of m < min(a,b) as written in the editorial

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

For all those who want to understand how the solution for D is working, have a look at the comments of my code.

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

I can't understand the solution of C except the base condition n + m <= a + b. And how to think solution of this kind of problem, I tried different types of conditions but couldn't unite them.

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

    Second type guests always choose fewer remaining type of cookies out of 2 types of cookies, so after they choose, the fewer number of remaining cookie is always reduced by 1. First type guests will not get angry if at least 1 cookie left, so the best thing to do is to put them on the back burner.

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

The contest was mostly logic based for question A to E1 and not much related to algorithms and data structures.

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

In problem E2 (Asterism), after we have calculated b_i, how are we able to find all the "good" x's in linear time?

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

Your algorithm for comprehending D is funny, Mr physics0523 ;P

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

For the whole round, I thought that in problem B, we have to count only one pattern for the row that completely divides the total number of days.The problem statement could have been written more clear.

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

still can't solve C :( if we call type 1 guest before type 2 guest then it won't decrease min(a,b) right? but in editorial

if there is a type 1 guest before a type 2 guest, the type 1 guest have a possibility to decrease the value of min(a,b) unnecessarily

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

    If a = b and we call two guests of type 1, they will decrease the minimum of a and b.

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

      I have a question, if you can't find some order using the greedy approach presented in the solution, how will you prove that you can't find any using a different approach ?

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

    Yes,this statement is conflicting. You can understand it by realising that at any moment,type 1 guest tries to eat the cookie which is more in number and type 2 tries to eat cookie which is less in number.If number of cookies are same the type 1 eats chocolate cookie and type 2 eats vanilla.

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

      got it, tysm! we invite type 2 guests first because they take minimum of vanilla and choclate and in the end we invite type 1 guests and check if we have required remaining dishes.

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

I'm not sure whether this was mentioned before, but there is a DP solution to E1 which generalizes to E2. I am going to present a handwavy explanation of it:

85709850 Here, dp[i] denotes the number of valid permutations of the i smallest elements. From there, we want to insert a new element in these permutations, which does not make any of the existing duels worse, as our candies are monotonically increasing, so we just find the number of positions, where we can put the new element. If we had x candies at start and our new duel is the k-th one, then we will have x + k — 1 candies, so this must be at least the new amount of candies.

Now moving on to E2:85708674

Knowing the recursion from the dp, we can now see that if we have too few candies to win a duel, f(x) is 0, and if we have at least as many candies at start than the p-th smallest enemy, we will also have trouble, because that multiplies our dp by p. So we can find the min and max candies easily, and now we just want to quickly decide whether any of our other products are zero. The parts in the dp product before the p-th smallest element cannot be divisible by p, as they are positive but smaller than p, so we just take the elements from the p-th to the n-th and see whether they give a zero residue with p, granted that we have less candies than them when starting the fights (this follows from the enemies being sorted and us having at less candies than the p-th smallest enemy). This can also be done linearly.

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

E1, "Yuzu should have at least $$$m-n+1$$$ candies initially to win all duels."

Isn't that wrong? Having that much candis garanties that not all duels get lost, but to garantie to win all duels Yuzu must have $$$m$$$ candies. Since all a[i] can be equal $$$m$$$.

I mean, a[] is not a permutation or somehow else pairwise distinct.

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

    bro see my solution for that problem it is easy to understand.

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

      I did not solve it because I was not able to come up with formular to calculate f(x) for any fixed x. And, honestly, I am still not sure about that after reading the editorial.

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

        :D hmm editorial is not good this time

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

        Agreed, they did not explain the solutions well, they just wrote the pseudo-code for the problem.

        Btw, I solved E1 in contest with basic principle of counting, for a fixed x, I counted no. of ways to fill 1st place * no. of ways to fill 2nd place and so on up to n places. My submission 85691626

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

    If you have $$$m$$$ candies, you can definitely win all duels. What the author meant is this:

    Let $$$x$$$ be the smallest number of candies you need to guarantee a win, then $$$x$$$ $$$\geq$$$ $$$m - n +1$$$. Had it been less than that, you'll have maximum $$$m-n+n-1$$$ candies against an enemy with $$$m$$$ candies.

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

      Ok, what he meant is "Yuzu should have at least $$$m-n+1$$$ candies initially to not loose all duels."

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

        Having m — n + 1 candies obviously does not guarantee winning all duels. eg — 5 5 5. Maybe, he meant that if we have candies less than this, then we are definitely going to lose.

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

    Hi! By at least it means that any x below this and we're certain that f(x) = 0, so we don't need to check below that. It's not actually necessary to do this if formula for finding f(x) handles all cases tho.

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

In tutorial of C it should be m <= min(a,b) instead of m < min(a,b) for answer to be "Yes".

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

B. Magical calender As was said before, she considers only shapes, there all cells are connected by side.

but for n=1 , r=any number output should be 0 according to question description. cuz 1 cell has no side by side connection

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

The test cases for E1 were such that I got a TLE when I solved in O(n*n*logn). Till today I thought log(n) does not make a difference. Got to learn something from the question.

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

Why am I getting WA on test case 6 of E1: 85714673

UPD: Fixed it

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

@author can you tell me 26th test case of 3rd problem.

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

I can't understand how is the formula for "Magical Calendar" question derived? Plz help!!

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

Can anyone please tell me what is wrong with my code for E1?

https://codeforces.com/contest/1371/submission/85673827

»
5 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it
#include<bits/stdc++.h>
 
int main() {
	using namespace std;
	ios_base::sync_with_stdio(false), cin.tie(nullptr);
	int T; cin >> T;
	while (T--) {
		int N, K; cin >> N >> K;
		cout << (K % N == 0 ? 0 : 2) << '\n';
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				int d = (j - i + N) % N;
				if (d * N + i < K) {
					cout << '1';
				} else {
					cout << '0';
				}
			}
			cout << '\n';
		}
	}
 
	return 0;
}

This is ecnerwala's solution for Problem D, can somebody help me in understanding how this solution works and what was the intuition behind that :)

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

    It's the same diagonal construction as the editorial, but computed in a different order. For each cell, we compute which diagonal it's on and use that to decide whether it should be set or not.

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

First three problems in O (1) and then we see D,E of O (n2) ... It was more like division 3 contest.

»
5 weeks ago, # |
  Vote: I like it +22 Vote: I do not like it

This editorial is so hard it needs another editorial. Seriously, it was easier for me to solve problems than to understand this, not even saying anything about jury code quality. Some standards for writing editorials are needed.

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

    I think it should be forbidden to have editorials in the form of pseudocode or formal algorithm description. I read editorials to understand how to arrive to the solution. If I want a formal description, I can just open anyone's submission

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

      Pseudocode might be fine, if it is easier to read than actual code. The actual solution must be present anyways. What you might need is a system of "tips", that describe a way of thinking that could lead you to the solution.

      Unfortunately, most of the time this is not the case and we see "just do this" or "we can prove that this works" types of arguments. Even just checking that a thing works might be of little value for me, because during contests you are not checking solutions, you need to come up with one.

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

binary search solution of E2

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

Hello, can anyone tell me how long we have to wait to see the change in our rating, system checking is done hours ago

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

I try to avoid library functions like ceil and pow because for higher numbers as input they give unexpected outputs.

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

Thanks for the contest and a fast editorial. Was able to solve two problems today. Hopefully will improve with time.

»
5 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

If you prefer video explainations, I go over everything (except a rather handwavey description of E2) at the end of my screencast of the round.

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

Can anyone please explain how this solution works for 1371E2 - Asterism (Hard Version). Thanks in advance.

        int n, p, a[n];
        cin >> n >> p;
        for (int i = 0; i < n; i++)
            cin >> a[i];
        sort(a, a + n);
        int l = 0, r = 1e9;

        for (int i = 0; i < n; i++)
            l = max(l, a[i] - i);
        for (int i = p - 1; i < n; i++)
            r = min(r, a[i] - i + p - 1); // need help with this part

        cout << max(0, r - l) << endl;
        for (int i = l; i < r; i++)
            cout << i << " ";
        cout << endl;
Taken from
  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    I have a proof that the solution must be a contiguous sequence of numbers here: https://codeforces.com/blog/entry/79624?#comment-654797

    He found the min and max numbers of the subarray, then printed every number in between.

    It seems that while I used binary search to find the maximum bound of the subarray, he found a cleverer way just using a for loop.

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

I have an interesting solution for E2 using binary search.

It relies on the fact that the answer will always be a contiguous sequence of numbers. I have a proof of that fact below.

85713453 (find minimum value in easy O(N), binary search to find the max value that works, print every number in between).

Proof:

  • Claim: f(x) can be written as some factorial, lets call it X!, multiplied by some mumbers <=X.
  • You can see that this is true when you calculate $$$p_i$$$, the number of possible numbers to go in the $$$i$$$th spot, after you've determined the first $$$p_0$$$ to $$$p_{i-1}$$$. f(x) equals $$$p_0 \cdot p_1 \cdot \ldots \cdot p_{n-2} \cdot p_{n-1}$$$. $$$p_i$$$ is calclated by (the number of numbers in the array <= x+i) — i. $$$i$$$ increases by $$$1$$$ each iteration, and because that is the only way for $$$p_i$$$ to decrease, is impossible to decrease by more than $$$1$$$. There is $$$1$$$ possible number that can go in the last position because only $$$1$$$ number is left, so the $$$p_{n-1}$$$ must equal $$$1$$$.
  • Thus, say you found the position with the maximum number of possibilities had $$$X$$$ possibilities, f(x) = X! * {some numbers <= X} because all numbers between $$$1$$$ and $$$X$$$ inclusive must be represented in $$$p_0$$$ to $$$p_{n-1}$$$.
  • This is important because you can say that $$$f(x)$$$ is divisible by all primes $$$<= X$$$ and not divisible by any primes $$$> X$$$, where $$$X$$$ is the number of possibilities of the index with the most possibilities.
  • You can also show that the $$$X_a \le X_b$$$ for all $$$a < b$$$. This is because having a greater value of x in f(x) will never result in less possibilities for any position.
  • Thus, for all $$$f(a)$$$ and $$$f(b)$$$, where $$$a < b$$$, if $$$f(a)$$$ is divisible by $$$p$$$, then $$$f(b)$$$ must also be divisible by $$$p$$$. $$$X_a$$$ is $$$> p$$$, and since $$$X_b \ge X_a$$$, $$$X_b > p$$$ as well.
  • Starting from the minimum working $$$x$$$ (before of which $$$f(x)$$$ is all $$$0$$$), no value of $$$x$$$ after the first non-working $$$x$$$ can work, so the answer must be in the form of a continguous sequence of numbers.
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    I also came up with a similar idea when upsolving, code with brief comments: 85718984

    The upperbound is the largest number that never has $$$\geq p$$$ options, and every greater number will surely hit $$$p$$$ options "on the way back down" as they run out of options

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

    Thanks. That really helped.

»
5 weeks ago, # |
  Vote: I like it +32 Vote: I do not like it

My solution and explanation for 1371E2 - Asterism (Hard Version)

The number of permutations for a given $$$x$$$ can be written in:

$$$f(x)=\Pi_{i=0}^{n-1} ((\sum_{j=0}^{n-1}a_j\leq x+i)-i)$$$

Since $p$ is a prime number, in order that $$$f(x)$$$ cannot be divided by $$$p$$$, we must ensure that $$$(\sum_{j=0}^{n-1}a_j\leq x+i)-i<p$$$ holds for every $$$i$$$. And in order that there is a possible permutation, we must ensure that $$$(\sum_{j=0}^{n-1}a_j\leq x+i)-i\geq1$$$ holds for every $$$i$$$.

Proof: Let's denote $$$(\sum_{j=0}^{n-1}a_j\leq x+i)-i$$$ as $$$g(i)$$$. We can find that, since $$$\sum_{j=0}^{n-1}a_j\leq x+i$$$ never decreases, so if $$$g(i)$$$ decreases, it can decrease at most $$$1$$$. Another observation is that $$$g(n-1)=1$$$. So if there is $$$i_1$$$ such that $$$g(i_1)>p$$$, there must be $$$i_2>i_1$$$ which satisfies $$$g(i_2)=p$$$, which makes $$$f(x)$$$ divided by $$$p$$$.

So the problem is now: how many $$$x$$$ are there that satisfy

$$$\forall i, 1\leq g(i)<p$$$

Since $g(i)$ increases with x, the answer must be a continuous segment $$$[lo..hi]$$$.

Now we sort the array $$$a$$$ in the ascending order.

For $$$lo$$$, we have

$$$\forall i, lo+i\geq a_i\implies lo\leq\max(a_i-i)$$$

For $$$hi$$$, we have

$$$\forall i, hi+i<a_{i+p-1}\implies hi<\min(a_{i+p-1}-i)$$$

So the final answer is the segment

$$$[\max(a_i-i)..\min(a_{i+p-1}-i)-1]$$$

Code: 85684812

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

    I can't understand the last two steps of your solution.Why Why does this formula work ? ∀i,hi+i<ai+p−1⟹hi<min(ai+p−1−i)

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

      $$$\forall i, hi+i<a_{i+p-1}\implies\forall i,hi<a_{i+p-1}-i\implies hi<\min(a_{i+p-1}-i)$$$

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

        I get it! Let cnt[x] be the amount of number which is equal or less than x,then we have ∀i,0<=i<n => cnt[x+i]-i<p => cnt[x+i]<p+i => x+i<a[p+i-1] => x<a[p+i-1]-i => x<min(a[p+i-1]-i). Thanks for your solution!

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

          anodiebird How did you come up with, x+i<a[p+i-1], steps before this one are clear. Can you please elucidate this one?

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

            ⑴ x+i<a[p+i-1] => x<a[p+i-1]-i ⑵ a+b<c => a<c-b If you look at these two equations,you will see both of them are the same form,in the first equation I just change the position of i,in the second equation I just change the position of b.

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

              anodiebird My doubt is that how did you transition from cnt[x+i]<p+i to x+i<a[p+i-1]

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

                Because we have sorted the elements of a[].If index i begins from 0,then we can see cnt[a[i-1]]=i,and you can deduce that p+i=cnt[a[p+i-1]].So let's substitute that into our expression:cnt[x+i]<cnt[a[p+i-1]] => x+i<a[p+i-1] => x<a[p+i-1]-i

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

If author's approach for problem F is unclear, then you may check my solution. 85721976 Imho problem F is the only problem that I've found interesting in this contest.

»
5 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

It is probably because it's his/her first contest but the editorial solutions to D and E1 are the worst. There is no reasoning/intuition given whatsoever. Please take it as constructive criticism.

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

My solution for problem F : 85724126

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

    Nice! Thanks for your explanation. It really helps.

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

My solution to 1371F - Яростный гром

Helping information

Obviously, this is a segment-tree problem. Then what do we need to maintain in each node?

In my implementation, the following information is maintained:

  • $$$ll$$$, the length of the prefix "<<<"
  • $$$lr$$$, the length of the prefix ">>>"
  • $$$rl$$$, the length of the suffix "<<<"
  • $$$rr$$$, the length of the suffix ">>>"
  • $$$lhi$$$, the length of the prefix ">>><<<" (at least 1 "<" and 1 ">")
  • $$$rhi$$$, the length of the suffix ">>><<<" (at least 1 "<" and 1 ">")
  • $$$hi$$$, the length of the longest ">>><<<" (at least 1 "<" and 1 ">")
  • $$$nlhi$$$, the length of the prefix "<<<>>>" (at least 1 "<" and 1 ">")
  • $$$nrhi$$$, the length of the suffix "<<<>>>" (at least 1 "<" and 1 ">")
  • $$$nhi$$$, the length of the longest "<<<>>>" (at least 1 "<" and 1 ">")
  • $$$mark$$$, whether the children of the current node should be flipped. It is also used as the flag for lazy propagation.

Then the answer to the query within a node becomes $$$\max(hi, ll, rr)$$$.

With such information, node combination and node flipping becomes easier and clearer.

Node flipping

  • Flip $$$mark$$$.
  • Swap $$$ll$$$ and $$$lr$$$, $$$rl$$$ and $$$rr$$$.
  • Swap $$$lhi$$$ and $$$nlhi$$$, $$$rhi$$$ and $$$nrhi$$$, $$$hi$$$ and $$$nhi$$$.

Node combination

  • New $$$ll$$$ is $$$l.ll$$$ if $$$l.ll < l.len$$$, otherwise $$$l.ll + r.ll$$$. It is similar for $$$lr$$$, $$$rl$$$ and $$$rr$$$.
  • New $$$lhi$$$:
    • If $$$0<l.lhi<l.len$$$, just use $$$l.lhi$$$
    • If $$$l.lhi=l.len$$$, use $$$l.lhi+r.ll$$$
    • If $$$l.lhi=0$$$ and $$$l.lr=l.len$$$ and $$$\max(r.lhi, r.ll) > 0$$$, use $$$l.lr+\max(r.lhi, r.ll)$$$
    • It is similar for $$$rhi$$$, $$$nlhi$$$ and $$$nrhi$$$
  • New $$$hi$$$ is the maximum of the following:
    • $$$\max(lhi, rhi)$$$
    • $$$\max(l.rhi+r.ll(\mathrm{if}\ l.rhi > 0), l.rr+r.ll(\mathrm{if}\ l.rr > 0, r.ll > 0), l.rr+r.lhi(\mathrm{if}\ r.lhi > 0))$$$
    • $$$\max(l.hi, r.hi)$$$
  • New $$$nhi$$$ can be calculated similarly.

My code

85729867

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

    Thank you so much for posting this. I was unable to understand after reading the editorial.

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

why i am getting run time error, i am unable to find that?

include<bits/stdc++.h>

using namespace std; int main() { int t; cin>>t; while(t--){ int n,k; cin>>n>>k; int res[n][n]; memset(res,0,sizeof(res)); if(k%n){ cout<<"2"<<endl; } else{ cout<<"0"<<endl; } int p=0; int q=0; for(int i=0;i<k;i++){

res[p+1][q+1]=1;
        p=p+1;
        q=(q+1)%n;
        if(p==n){
            p=0;q=(q+1)%n;
        }
    }
   for(int i=0;i<n;i++){
       for(int j=0;j<n;j++){
           cout<<res[i][j]<<" ";
       }
       cout<<endl;
   }
}
return 0;

}

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

What obfuscation software was used for the jury solutions? It is certainly very effective.

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

For E2 problem testcases are week: take an example: 9 8 3 5 9 11 15 17 19 20 23

answer is -> 0 but some codes of another coders gives output: 15,16,17,18,19

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

Can someone please provide a rigorous proof for Problem C as to why the order of guests where first all type 2 guests come and then type 1 guests come, is the most efficient ? I could not understand the explanation in the editorial.

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

    I don't have a rigorous proof but you can think in this manner that guests of type one can always adjust to any kind of case whether only vanilla,chocolate or both (provided the number of guests of type ones is less than equal to the total number of cookies) so our number of type of cookies is independent of guests of type one.

    It's not so for the guests of type two since they always choose the lesser type of cookies so if you feed the guests of type one before guests of type two it's going to be less optimal.(more chances of failure of satisfying the condition. Our problem asked to print yes even if a single situation could allow all guests to finish them off so always looking for most optimal way)

»
5 weeks ago, # |
  Vote: I like it -14 Vote: I do not like it
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

During the contest, I misread the question B as the total number of shapes of length n one can get if for any block, there is at least one block that shares one side with that block, thereby removing the problem constraint of n consecutive days. I still haven't been able to come up with any solution! Could anyone help with that?

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

UPD: Got it

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

What is wrong in my code for Asterism(Hard version) problem, I mean I am getting WA on test case 11, can someone help in finding the wrong logic that I am using in my code https://ideone.com/iUJnps

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

Are the ai values in E1 and E2 distinct or can some of them be the same?

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

No idea if this is mentioned before but I think there is a much cuter solution for F.

Notice that the balls are seperated by <> only. We only need to store leftmost, rightmost and longest distance between <> in a range. For the reverse it is just ><.

code: 85723638

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

    Thanks! I was able to solve this problem with your idea.

    By the way, I noticed that you use a MAX/MIN template for multiple elements. You don't actually need that since the following is valid in C++

    x = max({a,b,c,d....}) (We just need to use {} for multiple elements)

    Or is there some other benefit that I don't know of?

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

I have a question for the B task. What is the b variable?

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

    there is no b variable in problem B

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

I am a newbie Can someone explain me ( in problem D ) Why is this line included in the Jury solution ** arr[i][n]=0;** Thanks in advance

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

I tried to implement problem D 1371D - Grid-00100 but am unable to do that. Can anyone tell me where I am doing wrong?

Here's my code

P.S. : This code is Python Equivalent of dgupta0812 's code. I saw this in the comments.

Here's his code
»
5 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

Here is my approach and explanation for E1[problem:1371E1]

As Yuzu starts with x candies, we know the number of candies in each position of the array, i.e, x+1,x+2.....,x+n. This means at ith position with i starting from 0, the number of candies at that position must be strictly less than x+i+1.

Sort the array and iterate from the back. Let m1 be the maximum number. Now, how many positions can m1 occupy? It is x+n-m1 as m1 can only occupy positions having candies greater than m1.

Now, let m2 be the next(second maximum) number. It can occupy positions x+n-m2-1. We subtract 1 as one of the positons is already occupied by the maximum number. Similarly, for m3 it will be x+n-m3-2 and so on.

So, for ith number(array[i]), the positions it can occupy is x+n-array[i]-(n-i-1). If the number is less than x, then we have to subtract x-array[i] as the number of candies cannot be less than x, hence the number of positions it occupies will be x+n-array[i]-(n-i-1)-(x-array[i]).

On simplification, the number of positions for array[i]>=x is x-array[i]+i+1 and for array[i]<x is i+1. or simply min(x,array[i])+i+1-array[i].

Now f(x) is simply product the positions the numbers can occupy. 85781407

If someone has a simpler explanation for this approach, please let me know

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

for problem 1371E1 — Asterism (Easy Version), i am doing same as stated in editorial, but still getting TLE. Is it because i am using Python 3 ? here is my solution Please help.

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

    I guess no, there are many Python3 accepted solutions if you see the rank list

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

Why the statement on the tutorial of 1371E2 that once f(x) is divided by p,then f(x+a) is divided by p too is right?

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

Alternative approaches to ceil() is a blog post about the discussion on Problem A. I hope you find this useful.

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

https://codeforces.com/contest/1371/submission/85805079

https://codeforces.com/contest/1371/submission/85805620

The test case 2 is failing in both the solutions because the "jury" is changing it's answer in the second answer. In the first approach, it says that the answer for testcase 14 is 4 but in the second solution, it says that the answer is 0.

Why is this happening?

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

In problem E(hard version),I'd like to ask the conclusion "It's easy to see, that there should be max(ai)−n≤x≤max(ai) to have f(x)≠0 and f(x)≠n! (they are both divisible by p)." mentioned by the author. How to deduce it? While in Solution 1, though the author doesn't mention it, he uses this trick in bucket sort. So I am eager to know about it.

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

    Because when $$$x$$$ is too low you can't beat anyone, so there are no possible permutations. Same for high $$$x$$$, when you can beat anyone, so every permutation is good.

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

In problem E, i think , lower limit value of x where f(x)!=0 should be max(a[i])-n+1 and not max(a[i])-n and upper limit value of x where f(x)!=n! should be max(a[i])-1 and not max(a[i]). Is it so??

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

    Yeah, maybe it's just for convenience.

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

Formula for problem #1 can be simplified to (n + 1) / 2 to work for both even and odd inputs.

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

Any advice for implementing with E2 binary search?

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

Anyone please help me why i am getting wrong answer on test case 9 for problem E1. Thanks in advance. https://codeforces.com/contest/1371/submission/85904339

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

WOW, I'm stunned when reading through the author's code for problem F.

Compare to my code, It's too complicated

Here is my submission: 86278384

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

hello

In C part I used :

if(Math.min(a,b) >= m && Math.max(a,b) >= n){

            System.out.println("Yes"); 
        }
        else{
            System.out.println("No");
        }

and got a wrong answer. Could anyone please tell me.

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

There's something wrong with C's tutorial... $$$ m < min(a, b) $$$ should be $$$ m \leq min(a, b) $$$

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

In problem B, my code(Python3) 86906968 have wrong answer at test case 2.

When I replace the "int()" with "// 2" (integer division), it worked 86907899.

I don't know why it didn't work previously. Can someone explain this to me?