### chokudai's blog

By chokudai, history, 10 days ago,

We will hold Panasonic Programming Contest 2022(AtCoder Beginner Contest 251).

The point values will be 100-200-300-400-500-500-600-600.

• +65

 » 8 days ago, # |   +20 For problem D I represent number in 100-nary ($A_2 * 100^2 + A_1 * 100^1 + A_0 * 100^0$ for $0 \leq A_0, A_1, A_2 \leq 99$, and $10^6$ itself). Therefore we only need $3 * 99 + 1$ distinct numbers to represent all numbers within $10^6$.
•  » » 8 days ago, # ^ |   +8 Welp, I missed this T_T
•  » » » 8 days ago, # ^ |   -21 But u r 1720 rated on CF. It should have been straight-forward for u ig.
•  » » » » 8 days ago, # ^ |   +6 I'll learn from this and I promise to be a better 1720
•  » » 8 days ago, # ^ |   0 Please elaborate if you have time, I didn't got your approach.My questions : 1. What is this 100 nary number ? What are A1,A2,A3 ? Are they those three numbers which we are going to take ? and please explain this : we only need 3∗99+1 distinct numbers to represent all numbers within 10^6. Thanking you in advance
•  » » » 8 days ago, # ^ |   +5 Just regard each $i(1\le i\le w)$ as a $100$-base number. Then $A_0,A_1,A_2$ is each number of the $100$-base number. For example, $23456=2\times 10^4+34\times 10^2+56=(2,34,56)_{100}$, Then $A_0=56,A_1=34,A_2=2$.As for $100$, that's bacause $100\times 3=300$ and $100^3=10^6$.
•  » » » 8 days ago, # ^ |   -17 Jaikant shikre, asli id se aa
•  » » 7 days ago, # ^ |   -8 But the third condition is — We can choose at most 3 different weights from the prepared weights with a total mass of n.If the chosen number is 15 then we can select 9,3,2,1 four different weights from the list. How is this correct?
 » 8 days ago, # |   +8 Took 10 min to solve E as opposed to ~70 min for D. D > E
•  » » 8 days ago, # ^ | ← Rev. 2 →   0 yep E was straight up dp. how do they decide the ordering.
 » 8 days ago, # |   +14 Thanks for the contest!! Problems were nice. (especially problems D and F)
 » 8 days ago, # |   +8 Problem D is really an interesting problem,isn't it?
 » 8 days ago, # |   +8 Thanks for problem B has a test with answer > max(w) :)) I spam problem B to guess the arrray :))
 » 8 days ago, # |   +3 ABCs are becoming more and more challenging since the last 2 contests.
 » 8 days ago, # |   0 The second most difficult D that I participated at ABC (best one is ABC 210 D)
 » 8 days ago, # |   +8 Problem D is somehow quite surprising! Thanks to the writers for providing such a nice problem. It gives me another way to think about the construction of integers. I think, in general, if the maximum integer has n digits, and we divide them into m groups, then the upper bound may be about m*10^(n/m). For this problem, n=6 and m=3 and this is how "300" comes out. It really took me a long time to find out this approach.Problem E is about dp and F is about dfs/bfs, which is very nice as well. I am really lucky that at first sight, I have recogonized the correct solution, and I could seldom solve both E and F within the contest, but this time I made it.
 » 8 days ago, # |   +8 For B, I think "at most 3" means: n can only be represented by the sum of <=3 weights. If it can be obtained from >=4 weights, it is not a good integer. Then i didn't solve it during the contest.
 » 8 days ago, # |   0 can anyone explain E?
•  » » 8 days ago, # ^ |   +5 Its based on this standard DP problem. https://www.geeksforgeeks.org/find-maximum-possible-stolen-value-houses/
•  » » 8 days ago, # ^ |   +1 To make it easier, try to eliminate the cycle. To do that, you either pick a[1] then apply dp with elements numbered 3...N, or pick a[N] then apply dp to elements numbered 2...N-1.
•  » » » 8 days ago, # ^ |   0 can you give a code for the top-down approach, please?
•  » » » » 8 days ago, # ^ |   0 bottom-up actually(but it shouldn't be hard to convert to top-down :) )Solution
•  » » » » » 7 days ago, # ^ |   0 thanks ♥
•  » » » » 8 days ago, # ^ |   0 Here is a top-down approach Link
•  » » » » » 8 days ago, # ^ |   0 your idea is to reverse the vector and then run the same DP on it ?!
•  » » » » » » 8 days ago, # ^ |   0 Not reverse it but shifting the array to the right by one and then run the same dp on it
•  » » » » » » » 7 days ago, # ^ |   0 WOW!thanks, bro ♥
•  » » » 6 days ago, # ^ |   0 How does applying it twice remove the cycle?
 » 8 days ago, # |   0 E was very similar to recent contest — AtCoder Beginner 247 F
 » 7 days ago, # |   0 For problem G, I try to find the largest and smallest length of intercept (X or Y intercept whichever is smaller) of a particular side among all polygons. Then line passing through the query point (a, b) must have intercept not lying in the range [smallest, largest] and must lie in one of the polygon. Do this for all n sides.The problem with this is intercept if stored as double lead to floating point issue, and if stored as a rational number will lead to overflow of long long. What can I do in this case? Some testcases are showing TLE too.submissionI understood the japanese editorial given in atcoder, which is actually very nice and simple!
•  » » 7 days ago, # ^ |   -22 But you are just an expert, Do not try solving G in the contest.