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:
- Setters: Nishank IceKnight1093 Suresh, Nika nskybytskyi Skybytska, Nitish _helloLad Kumar, Apoorv tyr0Whiz Kumar, harshit.30
- Tester: Nika nskybytskyi Skybytska
- Text Editorialist: Nishank IceKnight1093 Suresh
- Statement Verifier: Nishank IceKnight1093 Suresh
- Contest Admin: Nishank IceKnight1093 Suresh
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!
is the contest delayed by 30mins?
Yes, it is.
C++23 when
So you can wait 16 years for the Spice and Wolf remake but cannot wait a few years for C++23?
Wdym? I couldn't wait 16 years so I used time machine to leap to the present time.
how to solve unusual queries? related with chicken mcnugget theorem?
Please refer to the official editorial.
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.
This solution was very helpful!
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$$$:
The problem thus reduces to some casework to count the number of integers $$$\leq n$$$ that you miss.
The testcases of speedrun are weak. The solution got AC. But it is giving NO for this testcase.
1
4 2
100 101 105 106
100 2 1 100
But the answer is YES because you can place bomb at 100.
I have seen many submissions giving answer NO for this testcase. IceKnight1093 Please update the testcases.