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

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

We will hold AtCoder Beginner Contest 381.

We are looking forward to your participation!

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

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

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?

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

    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?

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

G is more hard then past G !

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

This may be a challenging G for its hiiiiiiiiiigh score!

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

wait why friday?

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

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

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

Weak system tests on D!!

My solution passes system tests but fails for this testcase:

4
2 1 1 2

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

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?

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

Extremely difficult for problem G!

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

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

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

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;
  • »
    »
    17 месяцев назад, скрыть # ^ |
    Rev. 2  
    Проголосовать: нравится +5 Проголосовать: не нравится
    2
    2 2
    

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

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

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

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

        ans is 4

        clear will not change all elements to 0

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

          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;
          }
          
»
17 месяцев назад, скрыть # |
Rev. 2  
Проголосовать: нравится +4 Проголосовать: не нравится

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

It's suggested to change the dataset.

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

    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.

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

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.

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

    E is sphrase table and F is dp

    it just uses string to show the problem

    but still shit

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

      Can you please explain problem F in details ?

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

        $$$\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

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

          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 ?

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

      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?

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

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

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

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

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

1122?2024/11/22?

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

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.

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

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

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

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

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

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.

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

Please keep uploading testcases on dropbox link.

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

C~F are all very good problems.