atcoder_official's blog

By atcoder_official, history, 4 weeks ago, In English

We will hold AtCoder Beginner Contest 381.

We are looking forward to your participation!

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

»
4 weeks ago, # |
  Vote: I like it -20 Vote: I do not like it

Can we please improve the quality of editorials a bit.. if I am not able to get any clue on how to approach the problem during the contest then I can't just out of the blue understand the editorial with just stating the process rather than helping with some intuition behind the problem.

Problem F editorial was written so badly in abc 380. Other low effort editorials too. Is it just me who feels this?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    F's editorial was clear imo. You can interpret "is_first_player_win" as "can_first_player_win" and then simulate the game. The editorial also explains the time complexity and that it does not go in infinite recursion (game always ends). What are you confused about?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If you want to find how to approach of a problem, you shouldn't only read the editorial. Doing some other problems with the same type may help you.

»
4 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

Why is there no buzz here?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

G is more hard then past G !

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

This may be a challenging G for its hiiiiiiiiiigh score!

»
4 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

wait why friday?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Because ARC on Saturday and AGC on Sunday

  • »
    »
    4 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    bro thanks a lot for your comment. Now I will be able to participate in the contest . I thought that the contest will held as usual on Saturday!

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    'coz it's 11/22

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Wait, why will it hold on Friday?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Really liked the idea of ​​the contest) Spent too much time on E so didn't solve F(

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Weak system tests on D!!

My solution passes system tests but fails for this testcase:

4
2 1 1 2

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I just need a little bit of hint. Is it possible to do today's E problem E problem using lazy propagation on segment tree?

I tried it and can share code if required, but other than sample none of the test cases is working fine. Should I continue to debug lazy seg tree approach or think in different direction?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    E does not need segment tree at all. I just used binary search and prefix sums to solve it in offline mode.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah I figured out that count of 1s is a monotonically increasing array and count of 2s is a monotonically decreasing array. But i wasn't able to use this fact properly.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    stop learning useless algorithms.learn how to use binary search

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Extremely difficult for problem G!

»
4 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

I got 4 Wa on D and 6 Wa on E. :(

»
4 weeks ago, # |
Rev. 6   Vote: I like it 0 Vote: I do not like it

for D, why does the following WA? seen makes sure that every character appears exactly twice, each consecutive character is equal and I'm only checking for lengths that are even. Maybe I'm misunderstanding the problem statement in some way?

    auto find_largest = [&](int st) {
        int l = st, r = st;
        std::vector<int> seen(n);
        int ans = 0;
        while (r + 1 < n) {
            if (a[r] == a[r + 1]) {
                if (seen[a[r]]) {
                    // we have to contract the window
                    if (ans < r - l) ans = r - l;
                    while (seen[a[r]]) {
                        // mark the elements removed so they can be used to extend later.
                        seen[a[l]] = 0;
                        l += 2;
                    }
                }
                seen[a[r]] = 1;
                r += 2;
            } else {
                if (ans < r - l) ans = r - l;
                // start a new window
                r = l = r + 2;
                seen.clear();
            }
        }
        return std::max(ans, r - l);
    };
    std::cout << std::max(find_largest(0), find_largest(1)) << std::endl;
  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it
    2
    2 2
    

    note $$$a_i\color{red}{\le} n$$$

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I did --a[i] while reading the input so that should not overflow. The answer is 2 in this case, yeah?

      • »
        »
        »
        »
        4 weeks ago, # ^ |
        Rev. 2   Vote: I like it +8 Vote: I do not like it
        8
        2 2 2 1 2 2 3 3
        

        ans is 4

        clear will not change all elements to 0

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          Thanks, I see that this case fails but I'm surprised why clear does not set everything to 0. I also wrote another implementation that works on this case but gets WA regardless.

          #include <iostream>
          #include <vector>
          #include <queue>
          
          int main() {
              int n;
              std::cin >> n;
              std::vector<int> a(n);
              for (int i = 0; i < n; ++i) {
                  std::cin >> a[i];
                  --a[i];
              }
              std::deque<int> seq;
              std::vector<int> counts(n);
              int ans = 0;
              for (int i = 0; i + 1 < n; ++i) {
                  // seq always has even length
                  if (a[i] == a[i + 1]) {
                      if (counts[a[i]] > 0) {
                          if (ans < seq.size()) ans = seq.size();
                          while (!seq.empty() && counts[a[i]] > 0) {
                              --counts[seq.front()];
                              seq.pop_front();
                          }
                      }
                      seq.push_back(a[i]);
                      seq.push_back(a[i + 1]);
                      counts[a[i]] = 2;
                      i += 1;
                  } else {
                      if (ans < seq.size()) ans = seq.size();
                      while (!seq.empty()) {
                          --counts[seq.front()];
                          seq.pop_front();
                      }
                  }
              }
              if (ans < seq.size()) ans = seq.size();
              std::cout << ans << std::endl;
          }
          
          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Could you provide your complete code?

            For the former code, you can simply use the set to clear it, although it is $$$O(n\log n)$$$.

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            I don't quite understand the new code you wrote, but you can solve this problem by simply modifying the original code:

            photo

            • »
              »
              »
              »
              »
              »
              »
              4 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              You're right, with this change, it worked and got AC. Thank you!

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          you are right , it helps me!

»
4 weeks ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

The dataset of E too weak that brute force can accept it.

It's suggested to change the dataset.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Brute-force Code:

    #include<bits/stdc++.h>
    using namespace std;
    #define pc putchar
    #define rep(i,st,fi) for(int i=st;i<=fi;i++)
    #define per(i,fi,st) for(int i=fi;i>=st;i--)
    const int N=2e5+7;
    int read(){
        int x=0,f=1;char ch=getchar();
        while(ch<'0'||'9'<ch){if(ch=='-') f=-1;ch=getchar();}
        while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
        return x*f;
    }
    void print(int x){
        if(x<0){x=-x;putchar('-');}
        if(x>9) print(x/10);
        pc('0'+x%10);
    }
    void write(int x){print(x);pc('\n');}
    int n,q,sum[N],sum1[N],sum2[N],pos[N],tot;
    char s[N];
    int Get(int x, int l, int r){return min(sum1[pos[x]]-sum1[l-1],sum2[r]-sum2[pos[x]]);}
    int main(){
        n=read();q=read();
        scanf("%s",s+1);
        rep(i,1,n){
            sum1[i]=sum1[i-1];sum2[i]=sum2[i-1];sum[i]=sum[i-1];
            if(s[i]=='1') sum1[i]++;
            else if(s[i]=='2') sum2[i]++;
            else if(s[i]=='/') pos[++tot]=i,sum[i]++;
        }
        while(q--){
            int l=read(),r=read(),ans=0;
            if(sum[r]-sum[l-1]==0){write(0);continue;}
            int L=lower_bound(pos+1,pos+1+tot,l)-pos,R=upper_bound(pos+1,pos+1+tot,r)-pos-1;
            rep(i,L,R) ans=max(ans,Get(i,l,r));
            write(ans*2+1);
        }
        return 0;
    }
    

    It's obvious that a designed dataset like 1/2/1/2/1/2/...... can make this solution TLE.

»
4 weeks ago, # |
  Vote: I like it +41 Vote: I do not like it

i think it's quite not proper to put $$$\color{red}{6}$$$ string problem in an ABC.

by the way, the samples were too weak.

ABC is not the writer's amusement park, but one of the ways that the contestants improve themselves, hope to get better ABC next time.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    E is sphrase table and F is dp

    it just uses string to show the problem

    but still shit

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please explain problem F in details ?

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        $$$\mathrm{dp}_{i,j}:=$$$ the answer of decided what to choose from $$$A_1$$$ to $$$A_i$$$, and:

        if I've chosen an even number of numbers, $$$j=0$$$

        if odd, $$$j$$$ is the last chosen number

        so $$$j$$$ is what I have to choose next time

        so dp transition equation is obvious

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          I am not sure if this is right, if you are trying to form an odd sequence with index i, how do u ensure that dp[i-1][0] (i.e the answer upto index (i-1) with even number of elements) does not contain ar[i], I don't think we can achieve that with the current dp states. Also, can u provide the link to your submission ?

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            sorry i didn't mentioned the "appears exactly twice". we should use bitmask dp

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hey.. Can you please just hint me what could go wrong if I use segment tree with lazy updates for E.

      My logic.

      1. Build a prefix sum of 1s(array a) and 2s(array b).
      2. Store every position of / (let's say i) in array c and store pairs in array d as (count of 1s to the left of i, count of 2s towards the right of i).
      3. Now, build a lazy segment tree for range updates and range query over the array d of pairs. Each node representing segment l..r will store the max(min(d[l].first, d[l].second), min(d[l+1].first, d[l+1].second), .... min(d[r].first, d[r].second)).

      For each query, (l, r), I will find the next '/' ahead of l and prev '/' just behind r using upper and lower bound. Let's call this segment (x, y)

      For this segment of array d, I can do a range update. Subtract no. of 1s from 0 to l-1 from the segment (x,y)'s all values of .first (since we stored pairs in segtre). And another range update of subtract no. of 2s from r+1 to n-1 from the segment (x,y)'s all values of .second

      Then we can have our query over the segment (x, y) with lazy propagation and then after the query undo the update to be ready for the next query.

      I also have the code if you want to see. I have tried debugging for 3 hrs. but can't figure out the issue or why this approach would fail? Is it even possible to apply segment tree to this kind of questions?

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        maybe

        7 1
        111/222
        2 6
        

        is a hack

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        also you can do it like this:

        if $$$s_{i-1}=s_{i-2}=\cdots=s_{i-l}=1\land s_i=/$$$, then make $$$a_i\leftarrow l$$$, representing there are $$$l$$$ 1-s close to the left of slash $$$s_i$$$. do the same to 2 and $$$b$$$. and $$$c_i:=\min\{a_i,b_i\}$$$. if $$$s_i$$$ isn't slash, then $$$c_i\leftarrow -\infty$$$.

        for query, it's just asking $$$\max_{i=l}^r c_i$$$, so it's a sprase table.

        note the case of hack

      • »
        »
        »
        »
        4 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        I think your query is min, when you do a range update, you can't preserve it.

        For me to solve this problem, I use dichotomy to solve it.

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

        i have applied a similar approach, storing prefix of '1' and suffix of '2' but instead of lazy segTree. I apply a ternary search on the array of indexes of slashes. I cant figure out why its giving wrong anwers. as your an array that contains minimum of pfx1[i],sfx2[i] is ternary searchable

»
4 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

in E
WA $$$-$$$ AC = upper_bound $$$-$$$ lower_bound

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any thing wrong in this code?

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    if(mp[a[i]]<i-f[i]+1) g[i]=f[i];
    else g[i]=i-mp[a[i]];
    

    maybe i - mp[a[i]] is an odd number.

»
4 weeks ago, # |
  Vote: I like it -19 Vote: I do not like it

AtCoder, if you aren't able to set Gs for programming just remove them.

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

1122?2024/11/22?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain problem F in details ?

  • »
    »
    4 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    My solution is use the binary $$$s$$$ to express which $$$a_i$$$ had appear. So you need find the first position the $$$s$$$ appeared.

    First, you need preserve for each $$$i$$$ where the next $$$j (1 \leq j \leq 20)$$$ appear.

    you solve the $$$s$$$ from $$$1$$$ to $$$2^{20}$$$, you can enumerate the subset $$$g$$$ of $$$s$$$,you know the first position $$$g$$$ appeared and which $$$a_i$$$ you want next, so the $$$s$$$ first position can be found.

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone please help me understand why this solution for Question D is WA for 7 cases?

To me, it seemed pretty logical to check two items at once. Can someone please help me with a breaking test case or a scenario I missed?

»
4 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

The testcases for problem D were so weak.. so I submitted a wrong solution and got AC.

Hope the upcoming contests have a better testing system.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Editorial for E is missing !!! Is it a technical mistake or intended?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I didnt accept D.Who can hack my code?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

let's use O(N^2) brute forces to pass E!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

when will the dropbox update the test data? in fact it only had data up to ABC 377, where are 378 to 381?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain problem F to me again? i'm a newbie and the solution is really hard to understand

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone look into this, the submission from rank 1 on problem D, is giving wrong answer on stress testing. Link to Code

Test Case:
6
2 5 5 3 2 3

Correct Answer: 2

But rank1 person's code is giving output 6.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Please keep uploading testcases on dropbox link.