IceKnight1093's blog

By IceKnight1093, 7 months ago, In English

We invite you to participate in CodeChef’s Starters 137, this Wednesday, 5th June, rated for till 5-Stars(ie. for users with rating < 2200).

Time: 8:00 PM — 10:00 PM IST

Joining us on the problem setting panel are:

Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest. The video editorials of the problems will be available only to Pro users.

Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here. Hope to see you participating.

Good Luck!

UPD: Congrats to the top 5 in Div1!

  1. maspy

  2. flytime

  3. Kude

  4. risujiroh

  5. sheercold

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

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

is the contest delayed by 30mins?

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

C++23 when

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

    So you can wait 16 years for the Spice and Wolf remake but cannot wait a few years for C++23?

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

      Wdym? I couldn't wait 16 years so I used time machine to leap to the present time.

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

how to solve unusual queries? related with chicken mcnugget theorem?

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

    Please refer to the official editorial.

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

    The case $$$A = B = t$$$ is easy. For the case $$$A = t + 1$$$ and $$$B = t$$$, note that $$$p \cdot A + q \cdot B = (p + q) \cdot t + p$$$, so the goal is to generate all numbers $$$X = a \cdot t + b$$$, such that $$$a \geq b$$$. Let us fix $$$b$$$, then $$$a \cdot t + b \leq N$$$; $$$a \leq \left\lfloor \frac{N - b}{t} \right\rfloor$$$. So basically for each remainder $$$b$$$ in $$$[0, t - 1]$$$ you will find this value $$$a$$$. But observe that $$$a$$$ has at most only two possible values. So find the range of remainders $$$b$$$ in $$$[0, \text{lo} - 1]$$$, for which this value is $$$q$$$, and another range $$$[\text{lo}, t - 1]$$$ for which this value is $$$q - 1$$$. From here it shall be straightforward.

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

    Here is a more visual solution.

    For the case $$$A = m, B = m + 1$$$, consider the non-negative integers arranged in a grid of width $$$m$$$, where the $$$(i, j)$$$th cell represents the integer $$$mi + j$$$. For the cell labeled by $$$i$$$, we write $$$1$$$ if we can make a sum of $$$i$$$, and $$$0$$$ otherwise. Observe that if we can make a sum of $$$k$$$, then we can make a sum of $$$k + lm$$$ for any $$$l\geq 1$$$. Therefore, if we have a $$$1$$$ in some cell, then every cell below it in the same column has $$$1$$$. Observe that we can make $$$0$$$, implying that the first column is all $$$1$$$s. We can make $$$m + 1$$$ but not $$$1$$$ implying that the second column is $$$1$$$ from the second row onwards. Proceeding similarly shows that we get the following pattern:

    Example for $$$m = 5$$$:

    $$$ \begin{bmatrix} 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ &&\vdots \end{bmatrix} $$$

    The problem thus reduces to some casework to count the number of integers $$$\leq n$$$ that you miss.

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

The testcases of speedrun are weak. The solution got AC. But it is giving NO for this testcase.

Failed Testcase

I have seen many submissions giving answer NO for this testcase. IceKnight1093 Please update the testcases.