atcoder_official's blog

AtCoder Beginner Contest 468 Announcement
By atcoder_official, history, 6 weeks ago, In English

We will hold AtCoder Beginner Contest 468.

We are looking forward to your participation!

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

»
6 weeks ago, hide # |
 
Vote: I like it -42 Vote: I do not like it

So sorry, but waking up at 6am to do this kind of stuff is too tough. CF is at 8:30 am so that's better marginally.

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

I suppose you.

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

I solved A, C and D.

→ Reply
»
6 weeks ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Can anyone prove my F submission, I only wanted to have a try and don't expect it to pass. BUT IT PASSED! And I even don't know why my code is correct.Thanks so much!

→ Reply
  • »
    »
    6 weeks ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Congratulations!>w<

    You are so strong!

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

    Suppose we have x < y (initially x = 0, and we assign p1 to y). Iterating i from 2 to n: if pi > y, we must perform operation 2 to keep x as minimal as possible; otherwise, we just move to i + 1. Finally, we use the remaining elements only for x and use DP LIS.

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

I solved $$$D$$$ by fixing mid point of a palindrome, say $$$i$$$, and then find first index of mismatch with binary search and string hashing, and then find second index of mismatch, and add $$$second - i + 1$$$ to $$$ans$$$. But implementation too hard :(

Is there an easier way?

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

    You didn't need to use binary search or string hashing. For n <= 10000, doing a linear scan works fine

    → Reply
  • »
    »
    6 weeks ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    $$$N \leqslant 10^4$$$, so you can replace two binary searches with just linear search of the first and second indices in your approach.

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

    I use DP. I set an $$$10000 \times 10000$$$ array,but I haven't got a MLE ($$$340$$$ MB) :)

    And no TLE ($$$10^8$$$ in the max size of $$$N$$$).

    → Reply
  • »
    »
    5 weeks ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Use Manacher to solve it.

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

Could someone give the optimal time complexity for Problem D? Thanks, meow~

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

it was my first contest .. can anyone tell me how much time after my rating will be visible?

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

Hey hi can anyone help me out a bit on C :

https://atcoder.jp/contests/abc468/submissions/77865163

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

T_T What's the main idea for solving Problem G

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

    Let pos[i] be the position of i, then with s[k] = 'o' we have prefix_max[k]-prefix_min[k]+1 = k, otherwise prefix_max[k]-prefix_min[k]+1 > k. Let dp[k] be the number of permutaions satisfying the first k conditions, but s[k] = 'o', Find the nearest j < i and s[j] = 'o', then subtract the contribution of dp[k] from j+1 to i-1, k is the first position that s[i] must be 'o', consider first k elements as one block and shuffle it with i — k remaing position.See my code

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

    If you solve for the case $$$\text{o}\text{x}^k\text{o}$$$ which I call $$$g_k$$$ then you can multiply $$$g_k$$$ for each gap between o's of length $$$k$$$ in the final string since you can treat each sub-segment as an atomic unit when picking surrounding positions. To calculate $$$g_k$$$ remove all possible prefixes $$$\text{o}\text{x}^i\text{o}$$$ for $$$i \lt k$$$

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

Hoping the best for solving F

→ Reply
»
6 weeks ago, hide # |
 
Vote: I like it -54 Vote: I do not like it

Why was my account aaa_Pigeon banned? I didn’t even participate in this ABC.

If you believe I cheated in a previous ARC, I have a recording of my participation in ARC223: https://pixeldrain.com/u/AHjiKtsr

maspy

→ Reply
  • »
    »
    6 weeks ago, hide # ^ |
     
    Vote: I like it +52 Vote: I do not like it

    I am not involved in the banning process, so I do not know anything about it.

    Also, appeals regarding bans should be submitted through AtCoder’s contact form, not on the Codeforces Blog: https://atcoder.jp/contact

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

any hint for 5th problem?

→ Reply
  • »
    »
    6 weeks ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Think of finding the sum of all subarrays of a particular size, you may need some precomputations for that. Then the task is easy because we can just add that sum divided by that size i for instance with some modular mathematics in hand....

    → Reply
»
6 weeks ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

I sovle A to D. It's my best.

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

Oh no the closest one to AK,I only solved ABCDEF

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

I think problem F is very educational.

It is a two-dimension dp, and the trick is that we use a loop for one dimension, while using a segment tree to maintain the other dimension. There are several similar problems at codeforces as well.

→ Reply
  • »
    »
    5 weeks ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    can you please share your submission? and the similar codeforces problems that you mentioned if you have them? Thanks in advance :)

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

ban cheater wyc678,he clearly used AI

→ Reply
»
5 weeks ago, hide # |
 
Vote: I like it -18 Vote: I do not like it

maspy can I write editorial for problem E, if it is different than author's solution, my time complexity is O(n) if you are interested.

→ Reply
  • »
    »
    5 weeks ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    AtCoder allows users to post editorials, but there is a minimum rating requirement. If I remember correctly, you need a rating of at least 2000 to write an editorial for an ABC.

    You are also free to post an editorial somewhere other than the AtCoder contest page, including on this Codeforces blog.

    → Reply
    • »
      »
      »
      5 weeks ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it -18 Vote: I do not like it

      Yeah I know, but I just wanted my atcoder account displayed in editorial page

      → Reply
»
5 weeks ago, hide # |
 
Vote: I like it -10 Vote: I do not like it

Many people have used incorrect solutions for problem F. First, find all the prefixes max, and then perform LIS on the remaining ones using the original data. However, this set of data can be disabled: input: 13 5 6 7 8 1 2 13 9 10 11 12 3 4 expected output: 12

but the wrong solution will give 11 as its answer

→ Reply
  • »
    »
    5 weeks ago, hide # ^ |
     
    Vote: I like it +10 Vote: I do not like it

    Sorry for my mistake. I didn't see it. It seems like we have to do something every time

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

Hey atcoder_official,when will you place the english translation of the editorial?

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

Hello, can we have the english editorial please, and thank you for the contest.

→ Reply