Блог пользователя IceKnight1093

Автор IceKnight1093, 6 месяцев назад, По-английски

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

  • Проголосовать: нравится
  • +28
  • Проголосовать: не нравится

»
5 месяцев назад, # |
  Проголосовать: нравится +48 Проголосовать: не нравится

is the contest delayed by 30mins?

»
5 месяцев назад, # |
  Проголосовать: нравится -20 Проголосовать: не нравится

C++23 when

»
5 месяцев назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Please refer to the official editorial.

  • »
    »
    5 месяцев назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

  • »
    »
    5 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
5 месяцев назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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.