chokudai's blog

Exawizards Programming Contest 2021（AtCoder Beginner Contest 222） Announcement
By chokudai, history, 3 years ago, In English

We will hold Exawizards Programming Contest 2021（AtCoder Beginner Contest 222）.

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

We are looking forward to your participation!

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

Comments Comments (39)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it +25 Vote: I do not like it

Here's the screenshot of the contest page:

157.jpg

I'm wondering why the color is orange when the rating is 1999? Shouldn't it be blue?

Also, the point values of each problem hasn't announced yet. Is it a secret in this contest? Sorry my fault.

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

I have been trying from 30 mins to understand the problem C itself....

PS: Still haven't understood the question

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

    I did not read carefully which letters are used for the three options, and used the usual RSP instead.

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

    i don't know how to explain cause i also didn't understand it well but:

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

    I believe the intention of this problem is having you deal with that somewhat counterintuitive memory access. A[i][j] gives the move (rock, paper or scissor) for the i-th player at the j-th round, but you have to keep track of which player is playing which player at each round.

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

    Output is the $$$id's$$$ sorted by their rankings decreasingly (bigger ranking -> more wins, or if same number of wins the smaller id gets the better rank).

    What you need to do is make a custom comparator for your rankings array and sort them for every match.

    I agree statement was bloated and implementation was not fun :(

    Submission

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

      Instead of making comparator, we can also sort by inserting the score and id of participant as,(-score[i],i) into vector and sort it normally.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 2   Vote: I like it +3 Vote: I do not like it

        Neat trick! Will keep this in mind for similar problems. Thanks!

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

        Can you tell me how does this work?

        If we store the -ve of the score comes first?

        Isn't it the same like doing the reverse sorting with +ve score?

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

          If you do reverse sorting then for same scores, the one with bigger id will come first, but in problem we want the one with smaller id to come first in case of tie.

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

E was the best problem and fact-based problem I have ever seen Thanks :))

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

How can the overall complexity for E be $$$O(NK)$$$ if N=10^3, K=10^5?

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it -8 Vote: I do not like it

    I think k won't exceed 999 because n<=1000

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

      Imagine a line of 1000 nodes, M = 100, A = [1, 1000, 1, 1000 ... ], if every edge is painted red, we have K is around 10^5

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

        Removed because apparently I can't math properly.

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

          No, K = (M-1)(N-1). You can check this by imagining M=1 (or M=2)

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

    Even so,if your program's constant is'nt large,it's fast enough on overwhelming majority machine.

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

Thanks for the great contest! Problems are really nice, enjoy it :)

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

E and F were really nice! even though I got 4 WA because I didn't initialize my arrays large enough on E and didn't learn my lesson for F

I like how E combined two seemingly unrelated things: bfs/dfs through a tree and knapsack dp.

For F, I think anything to do with adding virtual nodes is brilliant.

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

how to solve D?

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

    I did DP with prefix sum.
    dp[i][x] = number of non decreasing sequences c[0]...c[i] with c[i]=x and a[j]<=c[j]<=b[j] for all j.

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

Are there any good article about rerooting DP like: the article written by ei13333, but in English?

Thanks in advance!!

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

How to solve G ?

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

I am getting runtime errors in 3 cases for my submission for problem E. Can someone tell me where is the problem.

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

    Did you consider the case when everything in the array M is equal? Eg:

    2 2 0
1 1
1 2

    Answer should be 2 here.

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

      This is the biggest miss on a corner case I ever had, thanks for the test case man!!!

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

      Thanx for the test case dude.

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

Can we solve problem D with recursive DP in O(N*M)?

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

This contest proved that I have serious weakness in dp

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

TLE on D. How to solve it in O(NM)?

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

    using cumalative sum idea. at any position you need a range (current value to next state highest value ) so you can precalculate before .

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

      Hey can you explain the base case dp[0][0] = 1. Is it due to the fact its empty sequence or something else?

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

        We can instead count the number of sequences $$$c_i$$$ ($$$i = 0, 1, \ldots, N$$$) (note that it has $$$N+1$$$ elements) such that $$$c_0 = 0$$$, $$$c_i < c_{i+1}$$$ for all $$$i = 0, 1, \ldots, N-1$$$, and $$$a_i \leq c_i \leq b_i$$$ for all $$$i = 1, \ldots, N$$$. The numbers are identical.

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

      Can you please explain your solution in detail? I can't get the idea.

      → Reply