We will hold Panasonic Programming Contest 2022(AtCoder Beginner Contest 251).
- Contest URL: https://atcoder.jp/contests/abc251
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20220514T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: leaf1415, Nyaan, m_99
- Tester: nok0, m_99
- Rated range: ~ 1999
The point values will be 100-200-300-400-500-500-600-600.
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$$$.
Welp, I missed this T_T
But u r 1720 rated on CF. It should have been straight-forward for u ig.
I'll learn from this and I promise to be a better 1720
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
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$$$.
Took 10 min to solve E as opposed to ~70 min for D. D > E
yep E was straight up dp. how do they decide the ordering.
Thanks for the contest!! Problems were nice. (especially problems D and F)
Problem D is really an interesting problem,isn't it?
Thanks for problem B has a test with answer > max(w) :)) I spam problem B to guess the arrray :))
ABCs are becoming more and more challenging since the last 2 contests.
The second most difficult D that I participated at ABC (best one is ABC 210 D)
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.
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.
But then the sample output for test case 2 would be invalid under your interpretation
can anyone explain E?
Its based on this standard DP problem. https://www.geeksforgeeks.org/find-maximum-possible-stolen-value-houses/
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.
can you give a code for the top-down approach, please?
bottom-up actually(but it shouldn't be hard to convert to top-down :) )
Solution
Here is a top-down approach Link
your idea is to reverse the vector and then run the same DP on it ?!
Not reverse it but shifting the array to the right by one and then run the same dp on it
How does applying it twice remove the cycle?
E was very similar to recent contest — AtCoder Beginner 247 F
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.
submission
I understood the japanese editorial given in atcoder, which is actually very nice and simple!