chokudai's blog

Panasonic Programming Contest 2022(AtCoder Beginner Contest 251) Announcement
By chokudai, history, 2 years ago, In English

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

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

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

Comments Comments (27)
| Write comment?
»
2 years ago, # |
  Vote: I like it +20 Vote: I do not like it

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$$$.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Welp, I missed this T_T

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it -21 Vote: I do not like it

      But u r 1720 rated on CF. It should have been straight-forward for u ig.

      → Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Please elaborate if you have time, I didn't got your approach.

    My questions : 1. What is this 100 nary number ?

    1. What are A1,A2,A3 ? Are they those three numbers which we are going to take ?

    2. and please explain this : we only need 3∗99+1 distinct numbers to represent all numbers within 10^6.

    Thanking you in advance

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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$$$.

      → Reply
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Took 10 min to solve E as opposed to ~70 min for D. D > E

→ Reply
»
2 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Thanks for the contest!! Problems were nice. (especially problems D and F)

→ Reply
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Problem D is really an interesting problem,isn't it?

→ Reply
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Thanks for problem B has a test with answer > max(w) :)) I spam problem B to guess the arrray :))

→ Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

ABCs are becoming more and more challenging since the last 2 contests.

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The second most difficult D that I participated at ABC (best one is ABC 210 D)

→ Reply
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

→ Reply
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like 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.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But then the sample output for test case 2 would be invalid under your interpretation

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain E?

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

E was very similar to recent contest — AtCoder Beginner 247 F

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

→ Reply