triple__a's blog

Codeforces Round #630 (Div. 2)
By triple__a, history, 5 years ago, In English

Hello Codeforces!

I am glad to invite you to my first official round Codeforces Round 630 (Div. 2), which will take place on Mar/31/2020 16:35 (Moscow time) (please note for the unusual starting time) and will be rated for all Division 2 participants.

You will be given 7 tasks and 150 minutes to solve them.

All tasks in this round were prepared by me. Hope that you will enjoy those tasks!

I would like to thank:

To avoid queueforces, we will provide small amount but strong (hope so) pretests for first few tasks. Hope it works!

Score distribution will be announced later.

Good luck and have fun!

UPD1: Score distribution: 500-1000-1250-1250-1750-2250-3000

UPD2: Contest is over, and here is the editorial.

UPD3:

I am sorry that pretests were not as strong as I excepted.

Congratulations to the winners:

div1+div2:

  1. vepifanov

  2. int128.

  3. PinkRabbitAFO

  4. 300iq

  5. nuip

div 2:

  1. int128.

  2. sorry_to_tourist

  3. camilla

  4. jerome_wei

  5. [user: _dawn]

people who were first to solve each task:

A: white_paperdog

B: MagentaCobra

C: okwedook

D: white_paperdog

E: GsjzTle

F: yooooooooo

G: GoGooLi

Lastly, thanks to Handsome2004 for the brilliant hack of E.

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

Comments Comments (258)
| Write comment?
»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Auto comment: topic has been updated by triple__a (previous revision, new revision, compare).

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -54 Vote: I do not like it

    this round suddenly come there was april fool contest and after that div1+div2 after last div3. thanku for the contest. :)

    → Reply
»
5 years ago, # |
  Vote: I like it +43 Vote: I do not like it

Welcome everyone to join in $$$⩾w⩽$$$

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

    What does it mean?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

      maybe I should add a full stop

      Welcome everyone to join in. ⩾w⩽

      $$$⩾w⩽$$$ ← it's just a emoticons.

      → Reply
»
5 years ago, # |
  Vote: I like it -17 Vote: I do not like it

hoping to get expert

→ Reply
»
5 years ago, # |
  Vote: I like it +30 Vote: I do not like it

I really hope that this H̶o̶p̶e̶ ̶s̶o̶ works!

→ Reply
»
5 years ago, # |
  Vote: I like it +46 Vote: I do not like it

Small but strong pretests yey no more queue thank you

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +110 Vote: I do not like it

    t = 1e5 in the sample...

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

    The number of participant is more and more large, it is another factor causing long queue, I think.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Long time no Chinese Round

→ Reply
»
5 years ago, # |
  Vote: I like it -60 Vote: I do not like it

Waited for Div.2 Round long time. :)

→ Reply
»
5 years ago, # |
  Vote: I like it -7 Vote: I do not like it

I hope I can get a good score!

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

Hope to see my username in blue after this contest. ^_^

→ Reply
»
5 years ago, # |
  Vote: I like it -26 Vote: I do not like it

The time is nice for Chinese :P

→ Reply
»
5 years ago, # |
  Vote: I like it +180 Vote: I do not like it

I like queueforces. My code feels like schrodingers cat.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

Thanks to all contest writers to make us busy during this lockdown situations. You are doing a great job. STAY SAFE STAY HOME

→ Reply
»
5 years ago, # |
  Vote: I like it +28 Vote: I do not like it
Best line
→ Reply
»
5 years ago, # |
  Vote: I like it -11 Vote: I do not like it

I hope that this contest will increase my rating.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why 150 minutes? Is it hard?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +45 Vote: I do not like it

    One of the reasons is there will be 7 problems, not 6 :)

    → Reply
»
5 years ago, # |
  Vote: I like it +15 Vote: I do not like it

how to get started in this contest , can anyone help i am new here

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

    go here and click Register Now on Codeforces Round #630 (Div. 2) and be online at the given time.

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

    Just go to contests section and you will find the contest

    You can register in it

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

      Already did earlier i didn't know where to start

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

        the problems are (mostly) ordered in the order of difficulty. So start with A and then B,etc.. But if you are stuck for a long time and can't go anywhere in current question try out another. Also if you have an issue with how to workaround with the UI recommend checking youtube video, there are some which will explain it and also try out a virtual contest to get a practical understanding of it. Best of luck for the contest!!!

        → Reply
»
5 years ago, # |
  Vote: I like it +125 Vote: I do not like it

→ Reply
»
5 years ago, # |
  Vote: I like it -30 Vote: I do not like it

Just curious about the "useful" discussion Nanako and Nezzar took part in.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +73 Vote: I do not like it

    Test different kinds of strange solutions, help to structure test datas, give some advice about problems to make difficulty gaps reasonable and so on.

    My work range is not much more than a tester, but my workload is more. I keep communicating with triple__a about these since 2 months ago, and help for much more than 7 problems meanwhile (you know, some problems will be denied when preparing a round), instead of temporarily taking a virtual participation.

    Actually I also tried to give a Problem B when needed, but it was denied. :thinking:

    Don't want to tell much before the contest lol. wish you get a good result in this round.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it -22 Vote: I do not like it

      Hopefully I will :)

      (PS -Didn't knew about the amount of efforts you guys give while preparing contests. Thanks :) )

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

    Generally testing & discussion of problems. Hope you enjoy the problems triple__a prepared!

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -43 Vote: I do not like it

Due to Quarantine registration will exceed 20K for sure. Thanks codeforces for arranging contests, the only partner in this quarantine :)) #GOCORONA #STAYSAFE #HAPPYCODING.

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it -8 Vote: I do not like it

how rating of expert contestents change in last div 3 round? sorry, I didn't notice.they fixed this.

→ Reply
»
5 years ago, # |
  Vote: I like it +27 Vote: I do not like it

I am glad to be the contributor to this round.But due to my weak ability I can't test hard problems :-(

Wish you guys like this round of Div2!

→ Reply
»
5 years ago, # |
  Vote: I like it -11 Vote: I do not like it
7 Problems !!
→ Reply
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

150 minutes...oh yeah!!...I got no work to do in this quarantine anyway.

→ Reply
»
5 years ago, # |
  Vote: I like it +30 Vote: I do not like it

→ Reply
»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Nice rating graph triple__a

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I receive the message from admin and surprised

The allowed programming languages are C/C++, Pascal, Perl, Java, C#, Python (2 and 3), Ruby, PHP, Haskell, Scala, OCaml, D, Go, JavaScript and Kotlin.

Is Rust banned? I can't see the name on the list.

Below is the one from the last educational and surely see Rust before Kotlin.

The allowed programming languages are C/C++, Pascal, Java, C#, Python, Ruby, Perl, PHP, Haskell, Scala, OCaml, Go, D, JavaScript, Rust and Kotlin.

→ Reply
»
5 years ago, # |
  Vote: I like it +24 Vote: I do not like it

I need triple(+7) to become Candidate .. I hope i will earn them !

→ Reply
»
5 years ago, # |
  Vote: I like it +14 Vote: I do not like it

****I'm really honored to take part in this test**** ****Good luck everyone!****

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

Thanks all of the members of this contest to prepare another good contest hopefully

→ Reply
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

First time participating in a live contest. Y'all got any pointers ?

→ Reply
»
5 years ago, # |
  Vote: I like it -23 Vote: I do not like it

Alas! I can't solve solve problem B/C. I just can solve problem A.

→ Reply
»
5 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Corona has definitely increased the participation in the recent contests. Thank you MikeMirzayanov for providing a great platform and, Thanks to problem setters too, for providing set of some amazing problems.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by triple__a (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by triple__a (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +56 Vote: I do not like it

B worth 1000 and D worth 1250 points? Quite weird, I think you could have saved one problem (C or D) for a future contest.

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

    Maybe C and D are subtasks? Who knows ))

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

      The author said that there are no subtasks

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

        My bad. Perhaps it is because of the fact that all the tasks are made of the same author, so it would be better to gather them together. Wish we will experience a great round with full of new challenging problems!

        → Reply
»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Best of luck guys !!!

→ Reply
»
5 years ago, # |
  Vote: I like it -28 Vote: I do not like it

My request to admin to conduct more contests while this lockdown period. Thanks

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

    They need time to prepare good quality rounds. Holding more rounds will definitely affect their quality.

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

      Yeah, But by taking help of good programmer may help to conduct. Code forces is known for its good quality rounds. Yeah.Quality of rounds should not be compromised. :)

      → Reply
»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

After seeing the score for question c and d. Excited to see which one will be easy one.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Guess, Which one will get more accepted, C or D?

→ Reply
»
5 years ago, # |
  Vote: I like it -9 Vote: I do not like it

We need more such contests in this quarantine period. Another Reason to stay at home.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

HackForces?

→ Reply
»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Small number of pretests is somehow already making me feel uncomfortable, I just hope it works well.

BTW, I am curious how hard it is for Codeforces to scale to the increasing number of users, I think registrations are about thrice the amount I used to see in last year, so can't just CF add some more processors(so that now they get 3x processors) or get something like thread ripper to judge systems so that queues are gone. I expect the number of submissions to be linear to the number of participants.

→ Reply
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

More than 20k people! this will be fun!! :D

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

    Fun by waiting for the problem to get judged (long queue) ?

    → Reply
»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Quick Check:- This is first contest designed by triple__a

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

WOOOOO I am very expect to join the contest,hope for a good game experience and everybody will get good rating improving o-o

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Huge participation indicates more people performing home quarantine.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

CF gonna fall down

→ Reply
»
5 years ago, # |
  Vote: I like it +27 Vote: I do not like it

problems are so fricking complicated I dont mean it is hard it is complicated fricking contest

→ Reply
»
5 years ago, # |
  Vote: I like it +54 Vote: I do not like it

I guess it's just my taste but A was quite disgusting

→ Reply
»
5 years ago, # |
  Vote: I like it -84 Vote: I do not like it

stop setting problems.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    stop complaining. The service provided here is free, you are not paying anyone and why does it matter to unrated acc.

    → Reply
»
5 years ago, # |
  Vote: I like it -27 Vote: I do not like it

let's make a round which is neither queueforces nor readforces next time!

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -27 Vote: I do not like it
The comment removed because of Codeforces rules violation
→ Reply
»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Quality with Difficulty

→ Reply
»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Really all problem are look like more tougher than usual contest

→ Reply
»
5 years ago, # |
  Vote: I like it +15 Vote: I do not like it

I feel like 2:30H is too much for a cf contest.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it -49 Vote: I do not like it

    fuch triple__a[user:triple__a] worst contest ever. dumbfuck dont know how to set problems

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +26 Vote: I do not like it

      Stop insulting people just because you were not able to solve the problems.

      → Reply
»
5 years ago, # |
  Vote: I like it -9 Vote: I do not like it

Chinese Round is too hard for me.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am glad that at today's round there were no queues and exits from the profile, thank you very much!

→ Reply
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Praying God for not failing in system test.

→ Reply
»
5 years ago, # |
  Vote: I like it +40 Vote: I do not like it

→ Reply
»
5 years ago, # |
  Vote: I like it +14 Vote: I do not like it

For everyone that had WA#3 on E: Every board is valid for odd N and odd M... Took me more than an hour to notice it :D

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

    It's also the first test on which not changing mod from 1e9 + 7 fails :P

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

    Exactly the same problem. Fortunately noticed it in the last 5 minutes, and only needed 1 line change in code to solve it :D

    → Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve G?

→ Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Video tutorial for problem D

Hope you enjoy it!

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

    Could you explain how you approached C

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

      You can observe that the string which is the period has to be palindromic as well

      Just greedily choose the maximal frequency of each letter and drop from n the sum of maximal frequences

      → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    What is the minimum size of the matrix which could be formed in que D?

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

      You need at least two lines to make some variation(for n = 1 the DP algorithm is optimal)

      You also need at least two columns to generate the variation, but we need one more column to actually translate the new result, so 2x3 is min size(or 3x2, it's the same thing)

      → Reply
»
5 years ago, # |
  Vote: I like it +25 Vote: I do not like it

I don't know how it was for you guys, but for me it was a hard round. :\

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

    So hard :с

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

      I am excited to see the editorial now :D

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

      It is true that the problems were hard to comprehend at first. But I think it's only A and B that hindered the progress of most participants. While the problem A was quite obnoxious, B was not as bad. I personally think they should have swapped B and C.

      → Reply
»
5 years ago, # |
  Vote: I like it +46 Vote: I do not like it

Hardest ever A .

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

    I think D was hard. It made me really sit and think.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -29 Vote: I do not like it

      D was really Trivial.

      But it took me an hour because I was thinking in the wrong side

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +17 Vote: I do not like it

        D is trivial then and only then you already know, how to solve it

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

          Lmao the example case literally gave you the working grid. If it weren't for the example case it would've taken me much longer.

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

    I solved B & C but not A. actually it seems so lengthy for me I didn't wanted to give time for this. :(

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

      What is your approach for solving B?

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

        B was easy I just generated all primes within 1000. and for each prime p (from least >=2) I traverse the array and i checked if(arr[i]%p==0) I assigned same color to these because gcd will be >=2. and you can see you can't have composite number n<=1000 such that n= pi*pj & pi,pj both > 11st prime

        → Reply
»
5 years ago, # |
  Vote: I like it +80 Vote: I do not like it

When you realize B solution only need first 11 primes

→ Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

had a bad experience

→ Reply
»
5 years ago, # |
  Vote: I like it +41 Vote: I do not like it

E is one of the most elegant problems I've seen so far :o

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

    Can you tell your thought process for it?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it +30 Vote: I do not like it

      First, note that you can replace all numbers with their values mod 2. Indeed, take m = max(a_ij), and then add 2 to each cell until they become either m or m + 1. The parity will not change. Then the first operation in the statement is useless, and the second one is simply inversion mod 2 (0 -> 1, 1 -> 0). In fact you can swap numbers in adjacent cells. This means you can move 1's arbitrary around the board. Also, if you have two 1's in adjacent cells, you can turn them into 0's by adding 1 to each.

      So the problem reduces to the following: you have nxm board with 0's everywhere apart from the corner cell, where it stands 1 or 0 (depending on the parity of the initial sum in all cells). Then 2 cases:

      1) n*m is odd
      2) n*m is even

      So the answer is the following: if n*m is odd, it is always possible with any a_ij. If n*m is even, it is possible if the sum of all a_ij is even. Now, let's solve the problem :)

      1) n*m is odd
      2) n*m is even

      All what is left is to calculate n*m powers — this you can do by fast power calculation, and fact that $$$x^{nm} = ({x^n})^m$$$.

      → Reply
»
5 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Can someone please help, how to calculate the number of correct boards in E when n * m is even.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    if (r-l) is odd $$$\frac{(r-l+1)^{nm}}{2}$$$

    else $$$\frac{(r-l+1)^{nm}}{2}+1$$$

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

      How did you get that formula?

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

        In odd case, it is number of all possible grids. In even case, it is same but divided by 2, because we only need ones whose sum of initial heights is even

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

      It should be $$$\frac{(r-l+1)^{nm}+1}{2}$$$ instead of $$$\frac{(r-l+1)^{nm}}{2}+1$$$

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

        Can you tell how you get the formula in brief ?

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

          If $$$nm$$$ is odd, all grids are valid. One way to prove it is coloring the grid with a checkerboard pattern (let's assume that the cell in the upper left corner is black) and noticing that you can fill the grid with $$$\frac{nm+1}{2}$$$ dominoes of size $$$2 \times 1$$$ in such a way that each cell is covered and a white cell is covered twice. Using the operation 1, you can increase the value of any white cell by 2 and the value of the other cells by 1 (let's call it operation 3). So, a possible strategy to win is to make the height of all black cells the same, and then use the operation 3 to fix the height of the white cells.

          On the other hand, if $$$nm$$$ is even you can win if and only if the parity of the sums of the heights in the white and in the black cells is the same.
          First, let's calculate in how many ways you can fill k cells with numbers in the range $$$[l, r]$$$ and even/odd sum ($$$dp_{even}[k], dp_{odd}[k]$$$). You can get these values by the following relations:
          $$$dp_{even}[k] = dp_{even}[k - 1] * dp_{even}[1] + dp_{odd}[k - 1] * dp_{odd}[1]$$$
          $$$dp_{odd}[k] = dp_{even}[k - 1] * dp_{odd}[1] + dp_{odd}[k - 1] * dp_{even}[1]$$$
          The relations can be obtained by fixing the parity of the sum of the first $$$k - 1$$$ cells.
          If $$$r - l$$$ is even, there are $$$\frac{r - l}{2}$$$ even numbers and $$$\frac{r - l}{2}$$$ odd numbers in the range, so $$$dp_{even}[1] = dp_{odd}[1]$$$ and $$$dp_{even}[k] = dp_{odd}[k] = \frac{(r - l + 1)^k}{2}$$$.
          Then let's fill all the grid ($$$\frac{nm}{2}$$$ white cells and $$$\frac{nm}{2}$$$ black cells). The result is $$$dp_{even}[\frac{nm}{2}] * dp_{even}[\frac{nm}{2}] + dp_{odd}[\frac{nm}{2}] * dp_{odd}[\frac{nm}{2}] = \frac{(r - l + 1)^{nm}}{2}$$$.

          If $$$r - l$$$ is odd, you can prove by induction that $$$dp_{even}[k] - dp_{odd}[k] = \pm 1$$$. Using some algebra, you can get the result $$$\frac{(r - l + 1)^{nm} + 1}{2}$$$.

          → Reply
»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

this is my first time to take part in a real contest. But... I couldn't solve a single task lol

→ Reply
»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Loved D ques.

It was really trivial if you know the basics of BitWise Operations.

→ Reply
»
5 years ago, # |
  Vote: I like it +22 Vote: I do not like it

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

for E, the idea I had in mind was the total count of odd numbers in the grid must be even, then with finite no of moves we can get all numbers with same parity. can someone say where this is going wrong?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please share soln of B !!!!

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it

    Hint : all number given as input must have a prime factor in 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31 because if all factors are above 31 then number will go beyond 1000 .

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

    The concept is based on Sieve of Eratosthenes, that is crossing out multiples of each prime number, and while crossing out multiples of primes, mark them with colours.

    • p, p*2, p*3, ... , p*n (You can see gcd will be at least p-prime number.)

    And, according to constraints given you can just colour all the numbers with the first 11 prime numbers.

    Submission

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

      sieve is not really needed here just make a set of smallest prime divisor of all numbers it will(number of sets) be less than equal to 11.

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

      I did the same, got wrong answer somehow. Seems correct to me (Works on the testcases given)

      https://codeforces.me/contest/1332/submission/74968519

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

        Your output is not correct. It outputs a total number of 10, which means you can only use color from 1 to 10. Your solution actually uses color 11, but not 9.

        You are missing one step here, iterate over your color array and do a mapping to make each color used within the range of [1, total unique color count].

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

    Since they said Answer will always exist, simply brute over all multiples of numbers from 2 to 1000 present in array which are univisited and assign them color.

    → Reply
»
5 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Shortest solution to a D problem ever. Loved the simplicity ;)

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

I'm failed at D at the last minute because number larger rr than >300000 if only i had read the checker logs :(

→ Reply
»
5 years ago, # |
  Vote: I like it +41 Vote: I do not like it

-what if we use 100% of the brain?

=write a hard contest so many participants will hardly solve A and dont solve any other questions and leave the contest so the traffic on the server wont be huge like the last contests

→ Reply
»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

D sample test itself is a gigantic hint.

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

    That is very true!Guess what xD? I copied the second sample output and modified it a little bit and done, accepted!

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

For G i did this following observations:
1. It's obvious that answer is 3 or 4
2. Let's suppose we have answer with 4 elements and the indexes are i1,i2,i3,i4. if there exists a solution, that means that there is a solution where i1 and i2 are adjacent indexes + i3 and i4 are adjacent indexes too.
3. So from point 2 , we conclude that we need to find i1 & i3 indexes, such that a[i1]>a[i1+1], a[i3]>a[i3+1] , a[i3]>a[i1] and a[i3+1]>a[i1+1] (or vice versa for a[i1]<a[i1+1] and a[i3]<a[i3+1])
Is the solution based on developing this idea or I am going the wrong direction?

→ Reply
»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

This Div2 was having more puzzle problems, I guess!

→ Reply
»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

A,B,C Indexfiddlingforces.

However given that lengthy statements it was still fun to participate. For me B was much harder than C. Felt like being testet on how much index-one-off-errors can one avoid.

→ Reply
»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Me RN

→ Reply
»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

First of all kudos and thanks to codeforces for handling high participation so nicely.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the contest. Wish problem-setters have good days <3

By the way, how to solve E guys ? :(

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone help me , what i am missing in my logic for question C (k- string)??

Logic : I deduced condition that all of given condition will be satisfied if we try to make an string of length K which is a palidrome. and replace it in all n position (i%k th place).

So first , i stored max count of the variable occuring at a position i(1<=i<=k) ; i stored and made a char array for so(max var);

then afterwards in order to make those k char a palidrome ,i checked from both side to find the optimal character for each pos,

at last i ran loop on string and counted the number of pos (pos%k) ,i need to change ,in order to make it combination of k legth optimal string.

Code

Also , my logic gave incorrect ans on 4th tc (i got 17 but ans was 16)

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

    One way to solve it to group positions which must have same characters to satisfy the rules. Then, foreach such group contribute $$$ans+=countPositions-maxFreqInGroup$$$ of that group.

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

      But how this formula is going to ensure that resulting string will be a Palidrome??

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

        You need to choose the groups of positions right.

        That is, every segment of k chars must be a palindrome, too. So within each segment of k chars is is that $$$s[i]==s[k-1-i]$$$ and all segments are equal. So there are $$$(k+1)/2$$$ groups of positions.

        We need to find the min count of operations to make all chars of one group same, for all groups. If they are same, the whole string is a palindrome.

        → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it +4 Vote: I do not like it

    I also had this problem in my code. But I corrected it after realizing that we have to consider both positions period and palindromic as they all should have same characters.

    As you are considering all characters frequency which are at at pos = i % k and you are selecting max from that for pos = i % k.

    But you also have to consider k - pos - 1 characters for pos = i % k.

    Reason is we have to consider frequency of all characters which can come at pos = i % k and they can be due to period positions and due to palindromic positions.

    My Submission 75017302

    → Reply
»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Am I the only one who did problem C. using a simple DFS with connected components? Felt like an overkill...

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

    Wait DFS how?

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

      Build a graph as follows: — each node represents a position in the array — an edge (u,v) exists if and only if u and v must have the same letter

      You can build the edges from the palindromic and period conditions.

      Then, all the vertices in a connected component must have the same letter. And in order to be optimal, we choose the letter that is the most frequent in that component. Then we repeat this for all components.

      Connected components are usually handled with a DFS.

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

    I did that too. I knew there would be an easier way but I just went with the connected components approach and it took me a lot of time.

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

      Can you briefly illustrate your approach?

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

        lets take that example: 6 2 abaaba

        transform it into: 121212 To make it palindrome, the last number and the first number must be the same. You will connect all the components together and use DFS to know which one belongs to which and then get the most repetitive character from all the numbered ones and then subtract it by the total characters that you counted in the set. It is like DSU but DFS is easier and faster to implement than DSU. It is clearly shown in that example that 1 and 2 are connected. So all characters must be the same. But that example:

        6 3 abaaba

        Transformation: 123123

        It is clearly shown that 1 and 3 components are connected. But 2 is not connected. So all 1's and 3's characters' must be the same. But 2 is independent.

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

    I did it as well

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I solved C using DSU (managing connected components). It was the first (and only) approach that came to my mind. I thought it will be the most intuitive approach (for others as well).

    Here's my solution: https://codeforces.me/contest/1332/submission/74985309.

    → Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Solution for E: Let total odd numbers in the range be odd, and total even numbers in the range be even. Let tot=n*m

If tot is odd, then answer is power(even+odd,tot). else the answer is (power(even-odd,tot)+power(even+odd,tot))/2

IS THIS APPROACH CORRECT?

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    The second formula should just be (power(even+odd,tot)+1)/2. EDIT: Nevermind, I think this is equivalent to what you said, you are correct.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by triple__a (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

B has taken much time because I cannot understand the meaning of the range of $$$m$$$ at first.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why Bob is incorrect in question D, i think his algo is correct for maximum??

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    3 3
    7 4 7
    3 7 7
    7 7 3

    Answer should be 3, but Bob's algorithm gives 0

    → Reply
»
5 years ago, # |
  Vote: I like it -75 Vote: I do not like it

MikeMirzayanov

My Code is giving right answer for the given test cases of problem -c while running in IDE geeksforgeeks and ide codechef Then I submit it on codeforces..bt it gives wa for the 3rd case of given pretest..It's really frustrating!! Please check once my code..tell why this is happening

include<bits/stdc++.h>

using namespace std;

define ll long long

define ld long double

define pb push_back

define pi pair<int,int>

define pl pair<ll,ll>

int main() { ll t; cin>>t; while(t--) { ll n,k,i,mx,tot=0,j,f; cin>>n>>k; ll fr[27]={0}; string s; cin>>s; for(i=0;i<k/2;i++) { for(j=0;j<26;j++) fr[j]=0; f=0; for(j=i;j<n;j=j+k) { fr[s[j+k-1]-'a']++;

fr[s[j]-'a']++;
        }



        mx=*max_element(fr,fr+26);
        for(j=0;j<26;j++)
        {
           // cout<<fr[j]<<endl;
            tot+=fr[j];
        }
       // cout<<tot<<" "<<mx<<endl;
        tot=tot-mx;
        //cout<<tot<<endl;
    }
    if(k%2==0)
    {
        cout<<tot<<endl;
    }
    else
    {
    for(i=0;i<26;i++)
    fr[i]=0;

        for(i=k/2+1;i<n;i=i+k)
        {
            fr[s[i]-'a']++;
        }
        mx=*max_element(fr,fr+26);
        for(i=0;i<26;i++)
        {
            tot+=fr[i];
        }
        tot=tot-mx;


    cout<<tot<<endl;
    }
}
return 0;

}

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it
    Suggesting adding code into the spoiler
    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem B

Input:

23

437 519 865 808 909 391 194 291 237 395 323 365 511 497 781 737 871 559 731 697 779 841 961

My output is

10

1 2 2 3 3 1 3 2 2 4 1 4 5 5 6 6 7 7 8 8 1 9 10

And I got this message: wrong answer violates gcd constraint.

Can anyone help explain? I don't really understand the conditions of this problem

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

    the numbers colored with 3: 808,909,194

    they don't have a gcd larger than 1.

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -51 Vote: I do not like it

it was very good contest

→ Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone tell me why I get TLE: https://codeforces.me/contest/1332/submission/74951923 I genuinely don't know.

→ Reply
»
5 years ago, # |
  Vote: I like it -41 Vote: I do not like it

My quick review:

A — classic shitty A with many cases

B — too long statement for such an easy task

C — good task but too simple for C

D — awful constructive

E — classic «try and guess» combinatorics

F — pretty standard dp (counting again)

G — good task

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    My views on A and C are opposite to yours. There is only one special case in A and even that is given in sample tc.

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

      There are 0 edge cases in C though :thinking:

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

        I meant that A was good and C was not

        → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In E, I sincerely thought that answer height had to be between L and R also and was losing my mind for an hour.

→ Reply
»
5 years ago, # |
  Vote: I like it -97 Vote: I do not like it

I just downvoted your contest.

FAQ What does this mean? The amount of contribution (points) on your comment and codeforces account has decreased by one.

Why did you do this? There are several reasons I may deem a comment to be unworthy of positive contribution. These include, but are not limited to:

Rudeness towards me,

Making bad contest,

Sarcasm not correctly flagged with italic font.

Am I banned from the Codeforces? No — not yet. But you should refrain from making contests like this in the future. Otherwise I will be forced to issue an additional downvote, which may put your commenting and posting privileges in jeopardy.

I don't believe my comment deserved a downvote. Can you un-downvote it? Sure, mistakes happen. But only in exceedingly rare circumstances will I undo a downvote. If you would like to issue an appeal, shoot me a private message explaining what I got wrong. I tend to respond to Codeforces PMs within several minutes. Do note, however, that over 99.9% of downvote appeals are rejected, and yours is likely no exception.

How can I prevent this from happening in the future? Accept the downvote and move on. But learn from this mistake: your behavior will not be tolerated on CodeForces.com. I will continue to issue downvotes until you improve your conduct. Remember: Codeforces is privilege, not a right.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +48 Vote: I do not like it

    If you want to criticize someone just say what you don't like, there's no need to be snarky with this whole 'legal downvote' act or whatever this is supposed to be.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I really liked the problems :)

I thought they were balanced; considering the score distribution of course.

I think the reason some found them to be unbalanced is that they were kind of unusual. Especially B D which were not like most B Ds. If you ask me though, that's a very good thing.(some saw A to be too tricky and long though, which is kinda true)

The round was smooth enough to be a success considering how many registered.

Good job, you should be proud!

→ Reply
»
5 years ago, # |
  Vote: I like it +28 Vote: I do not like it

Sample test 2 for D gave it away

→ Reply
»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

A really Good Contest. Handled 23k Participants with almost negligible waiting queue and still fairly enough strong pretests.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Super Fast editorial

→ Reply
»
5 years ago, # |
  Vote: I like it +12 Vote: I do not like it

I figured out why many people(including me) got wa on test 57 in E)
it was because of %(mod-1)

x^y≡x^(y%(p-1))mod p
but there is a condition that x needs to be coprime to p
the following test case was a corner case- 998244352 2 1 998244353

the sad thing is that %(mod-1) wasn't even needed. I wish this test case was in pre-tests

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

    next time you can use % (mod - 1) + mod - 1 instead

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

    Thanks, missed the coprime condition :-(

    → Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Why my first submission to problem B get AC ? The array "to" is out of bounds 75000215

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +7 Vote: I do not like it

    It's an array, so you have undefined behavior without errors. It's not affected to your solution, because you aren't using values from to[11-13], but you're only assigning it.

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

      But in some cases col[i] use all number from 1 to 11，and to[11] is also used

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it +9 Vote: I do not like it

        Undefined behavior is undefined...(You were lucky to have free memory after to array in each test, so you could use it. I'm obviously not expert in c++, but once I saw a similar example)

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 3   Vote: I like it +8 Vote: I do not like it

        On my machine it works, on cf's custom test too, but at the same time it is ub:

        int arr[3] = {1,2,3};
arr[3] = 4;
cout << arr[3]; //output is 4
        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +9 Vote: I do not like it

          Okay I got it ,anyway I should avoid such errors，thank you very much

          → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, can someone help me figure out what was wrong with my submission for problem B?

https://codeforces.me/contest/1332/submission/74968519

I am a beginner and I am really confused as I implemented a very similar solution to the problem as is given in the editorial.

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

    Re-read the "Output" part of problem statement and compare it with your output of the 3rd subtest.

    → Reply
»
5 years ago, # |
  Vote: I like it +76 Vote: I do not like it

To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove the cheaters, fix wrong division cases and update ratings them again!

→ Reply
»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Am I the only one who started solving D with XOR instead of AND (and only realized the mistake after getting WA2)?..

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

    I first started solving with OR got wa on test 2 and then realized its AND

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

Was A tougher than normal today or was it just me?

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

    It was the worst A in my life:/

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    my theory is they made it a bit implementation-heavy to avoid the initial congestion of 20000 submissions in the first 2 minutes :p

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

      Lmao

      I hope problem setters don't find this tip xD

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

    I think no.. One simple solution is to print 'W' at last cell i.e at (n,m) and keep all cell 'B'..It will be quite tough if try in other way

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

weak testcases and the queue wasn't full like last div3

→ Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Math forces :/

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice contest.

A was somewhat harder than usual Div2 contests (BTW, thanks for including the third testcase in the sample — I completely missed that possibility), but I have seen far worse.

B and C were good problems — moderate implementation. I felt D was a bit more difficult to think of, so D should have been worth more points than C. D should probably be worth 1500 points, and E at least 2000 points.

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

    D was a 2 liner task even in C++

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

      No. of lines is never a good estimate of difficulty. It took me a lot of time to think of an idea for solving D.

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Was it really necessary to make the bounds up to 2 * 10 ^ 5 instead of 10 ^ 5, I felt this was unnecessary. I am a bit biased because this was the cause of my FST on problem C.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What does "violates gcd constrain" means?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Minus A
I really enjoyed the problems from this round

And the definitions of left, right, down and up in A were really weird

  • exactly a steps L: from (u, v) to (u − 1, v);
  • exactly b steps R: from (u, v) to (u + 1, v);
  • exactly c steps D: from (u, v) to (u, v − 1);
  • exactly d steps U: from (u, v) to (u, v + 1);

This doesn't feel right at all!
I feel left and down should be swapped same for right and up

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

    it would be natural if you consider it as the 2D coordinators

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

triple__a, respect.

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

You should post the top scorers as well as the 1st solves for each problem. That would be cool

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

Thank you for the contest triple__a, I really enjoyed it :) Particularly problem D, which I managed to get in the last 2 minutes (luckily), which was really fun to do!

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why do we need to consider both cnt[i%k][j] and cnt[k-i%k-1][j] in question C?

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

OK！

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

does memset work slow?

problem c gives TLE using memset [submission:https://codeforces.me/contest/1332/submission/74982492]

with vector got AC [submission:https://codeforces.me/contest/1332/submission/74983633]

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

    Memset is wildly fast. The issue with your submission is that you memset the entire array (of size 5.2 million) for each of up to 100000 test cases. This is $$$5.2 \cdot 10^{11}$$$ operations, which is way too many. Manually filling the array with zeroes up to $$$n$$$ or $$$k$$$, or using vectors in your case, makes your runtime on the order of $$$\sum n$$$ instead of $$$T \cdot 5.2 \cdot 10^6$$$.

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

Auto comment: topic has been updated by triple__a (previous revision, new revision, compare).

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey! I am very beginner to competitive coding. may anyone suggest any lead from where i should start?

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

    Solve problems, the more the better. Click above on "Problemset" and just do it.

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

    whatever you are typing here just type in google and press enter you will get millions of suggestions already suggested.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey guys, I made a video tutorial for problem F which, btw I really enjoyed solving! https://www.youtube.com/watch?v=oEPtZLUG4iQ

→ Reply