maroonrk's blog

AtCoder Grand Contest 075 Announcement
By maroonrk, history, 4 months ago, In English

We will hold AtCoder Grand Contest 075. This contest counts for GP30 scores.

The point values will be 600-800-1200-1200-1600.

We are looking forward to your participation!

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

»
4 months ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

Problem B is similar to https://qoj.ac/problem/8582

→ Reply
»
4 months ago, hide # |
 
Vote: I like it +18 Vote: I do not like it

People who solved A must have the same brainwave with PCTprobability. It takes me 65:28 to solve the sweet honey A.

→ Reply
  • »
    »
    4 months ago, hide # ^ |
     
    Vote: I like it +8 Vote: I do not like it

    Try to write a brute force to generate all valid solution for n=5. That's how I solved it.

    → Reply
»
4 months ago, hide # |
 
Vote: I like it +28 Vote: I do not like it

why this contest can be an AGC?

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

I think it's possible to do $$$k=10^6$$$ in D, because you don't actually have to iterate through all maximum pairs $$$(x,y)$$$ as stated in the editorial. Instead, by just knowing the maximum value $$$x$$$, we can calculate the total contribution of all $$$y$$$ with some case analysis. Since we still need matrix multiplication or BM, the complexity is $$$O(k\log n)$$$.

By setting $$$k=10^4$$$, some even more brute force solution might pass, like iterating through the maximum $$$3$$$ values (there are only around $$$10^6$$$ such tuples that are meaningful).

→ Reply
»
4 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can anyone prove my example in A? For odd $$$n$$$, pattern is like this (here $$$n = 9$$$):

111111111
100000000
101111110
101000010
101011010
101011010
101000010
101111110
100000000
→ Reply
  • »
    »
    4 months ago, hide # ^ |
    ← Rev. 3  
    Vote: I like it +61 Vote: I do not like it

    Everything works, where $$$a[i][j] \neq a[n+1-j][n+1-i]$$$, and the $$$i+j=n+1$$$ diagonal is $$$0101 \cdots 1010$$$.

    There is an obvious bijection between the 0 paths and 1 paths without the middle diagonal. And the rest of the proof is the same.

    → Reply
»
4 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Why B less people solved but less score than D. I solved B but didn't have enough time think D. I lost so many extra rating because of this.

→ Reply
  • »
    »
    4 months ago, hide # ^ |
     
    Vote: I like it +22 Vote: I do not like it

    You knew the score distribution, right?

    → Reply
    • »
      »
      »
      4 months ago, hide # ^ |
       
      Vote: I like it +25 Vote: I do not like it

      I believe you meant to say: you knew the public standings, right? Pointing out score distribution to a guy complaining about score distribution is... pointless at the very least.

      → Reply