Блог пользователя atcoder_official

Автор atcoder_official, история, 19 месяцев назад, По-английски

We will hold AtCoder Beginner Contest 404.

We are looking forward to your participation!

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
19 месяцев назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

Anyone knows why kenkoooo hasn't been updating the problem difficulty for nearly 2 months (since ABC397/ARC195/AGC071)?

The problems of ABC402/ABC403/AGC072 is also not shown in the chart.(Though I can see my submissions on those problems in /user-submissions.)

»
19 месяцев назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

If we change Page Not Found to Beginner Contest:

»
19 месяцев назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

Another AI Beat Contest.

»
19 месяцев назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Why AC*48 WA*6 here?

Sad, I lost my AK because of corner cases.

»
19 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

In C , isn't checking for the frequency of all nodes as 2 will do ? I got 4 WA for it

»
19 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

In Problem F, the solution which uses brute force to enumerate every strategy can get Accepted. In theory, the Time Complexity is

$$$ \Theta\left(T \cdot K \cdot C^{\sqrt m}\right), \quad C = \exp \left( \pi \cdot \sqrt{\dfrac 23} \right) \approx 13. $$$

Is the solution expected?

»
19 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Any hint for E?

»
19 месяцев назад, скрыть # |
← Rev. 4  
Проголосовать: нравится +8 Проголосовать: не нравится

ban lkfush please. this is an alt account and i can confirm he use ai in the contest 1 2

ban SB_JAPEN, this username is not legal and he must use ai cause he solve ABCDEF veryvery fast

ban timebomb please. he must use ai too

mywwzh is the bigest cheater in China, ban him too please

»
19 месяцев назад, скрыть # |
← Rev. 3  
Проголосовать: нравится 0 Проголосовать: не нравится

I'm trying to figure out why is E allows for $$$O(n^2)$$$, because I claim that this algorithm should pass in O(n) and is straightforward:

Spoiler

Can someone please help me find a test case that should break this? Thinking about multiple possible test case ideas but they all get $$$O(n)$$$ amortized.

(P.S I'm aware of the $$$O(n$$$ $$$log$$$ $$$n)$$$ solution, but I'm trying to figure out why the range min queries are not $$$O(n)$$$ amortized considering the fact that all queries are special since they are all of the form $$$[i-C[i], i-1]$$$ which is not the same as in a segtree problem, which can solve for any general range.)

  • »
    »
    19 месяцев назад, скрыть # ^ |
    ← Rev. 3  
    Проголосовать: нравится +3 Проголосовать: не нравится

    I'm not sure I follow, how do you do the instructions of the third paragraph without visiting all the bowls accessible ? Because if you need to visit for each bowl, every bowl between its range, then your complexity should be O(n²)

    • »
      »
      »
      19 месяцев назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

      I think a solution of time complexity O(nlogn) is possible.

    • »
      »
      »
      19 месяцев назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

      Here's the thing, you do! However, there's a very key observation to be made.

      Spoiler
  • »
    »
    19 месяцев назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    your approach
    Spoiler
    • »
      »
      »
      19 месяцев назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

      Just managed to prove that surprisingly in this case, despite the worst case being $$$O(n)$$$ for each bowl you can get it down to $$$O(n)$$$ amortized if you're clever with how you manage part of the approach you mentioned as supposedly having worse case $$$O(n^2)$$$! (The challenge however, remains in proving that not implementing this allows for $$$O(n^2)$$$ worst case)

      While segment tree is useful to guarantee $$$O(n log n)$$$, because your queries are more specialized (specifically, the start/end points of your queries are known beforehand and the queries chosen are those based on the moves you make, which you have some information you can learn about while doing the algorithm, i.e. "those elements cannot be options you can pick on any future queries"), you can actually avoid the requirement to maintain a segtree which allows for $$$O(n)$$$.

  • »
    »
    19 месяцев назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    Maybe due to $$$\sum_i c_i$$$ is $$$O(n^2)$$$

  • »
    »
    19 месяцев назад, скрыть # ^ |
    ← Rev. 2  
    Проголосовать: нравится 0 Проголосовать: не нравится

    DP was more straightforward , there could be $$$O(NlogN)$$$ optimisation but that wasn't needed to be forced,

  • »
    »
    19 месяцев назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    Figured out that this algorithm would be $$$O(n)$$$ if we're clever with our checking. The question remains of whether or not a direct bruteforce without this optimization is $$$O(n^2)$$$ or also $$$O(n)$$$ by using amortized analysis.

    Completing the Algorithm/ Proof of O(n)
»
19 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I performed pretty badly today, sucks to be stuck in E after 1 WA...

»
19 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

why does my greedy bitmask not work? Link. I believe that if there is a smaller mask, then we don't we need to worry about it in the super masks

»
19 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Can someone give me some advice on how to perform well in a contest? I can't think logically and just want to implement the code at a fast speed so that I often can't get it right.

»
19 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Is G a known / standard problem as it seems very difficult to be solved by so many people ?

»
19 месяцев назад, скрыть # |
 
Проголосовать: нравится +6 Проголосовать: не нравится

Will there be any English editorial, or just Japanese one?

»
19 месяцев назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I think this problem, abc266 E — Throwing the Die, is very similar to today's F.

Somehow I find that atcoder team really likes this kind of problem, which has the following dp pattern. Let dp[x][y] denote that we still have x steps to go, and currently we have obtained y scores, and the value of dp[x][y] denotes the probability. We can find the transition by considering what scheme we select to do in the next step, and thus dp[x][y] usually depends on some dp[x-1][y+z].