atcoder_official's blog

AtCoder Beginner Contest 381 Announcement
By atcoder_official, history, 17 months 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

Comments Comments (46)
| Write comment?
»
17 months ago, hide # |
 
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?

→ Reply
  • »
    »
    17 months ago, hide # ^ |
     
    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?

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

G is more hard then past G !

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

This may be a challenging G for its hiiiiiiiiiigh score!

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

wait why friday?

→ Reply
»
17 months ago, hide # |
 
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(

→ Reply
»
17 months ago, hide # |
 
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
→ Reply
»
17 months ago, hide # |
 
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?

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

Extremely difficult for problem G!

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

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

→ Reply
»
17 months ago, hide # |
← 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;
→ Reply
  • »
    »
    17 months ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it +5 Vote: I do not like it 
    2
2 2

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

    → Reply
    • »
      »
      »
      17 months ago, hide # ^ |
       
      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?

      → Reply
      • »
        »
        »
        »
        17 months ago, hide # ^ |
        ← 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

        → Reply
        • »
          »
          »
          »
          »
          17 months ago, hide # ^ |
          ← 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;
}
          → Reply
          • »
            »
            »
            »
            »
            »
            17 months ago, hide # ^ |
             
            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)$$$.

            → Reply
          • »
            »
            »
            »
            »
            »
            17 months ago, hide # ^ |
             
            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

            → Reply
»
17 months ago, hide # |
← 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.

→ Reply
  • »
    »
    17 months ago, hide # ^ |
    ← 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.

    → Reply
»
17 months ago, hide # |
 
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.

→ Reply
  • »
    »
    17 months ago, hide # ^ |
     
    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

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

      Can you please explain problem F in details ?

      → Reply
      • »
        »
        »
        »
        17 months ago, hide # ^ |
         
        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

        → Reply
        • »
          »
          »
          »
          »
          17 months ago, hide # ^ |
          ← 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 ?

          → Reply
          • »
            »
            »
            »
            »
            »
            17 months ago, hide # ^ |
             
            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

            → Reply
    • »
      »
      »
      17 months ago, hide # ^ |
       
      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?

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

        maybe

        7 1
111/222
2 6

        is a hack

        → Reply
      • »
        »
        »
        »
        17 months ago, hide # ^ |
         
        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

        → Reply
      • »
        »
        »
        »
        17 months ago, hide # ^ |
        ← 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.

        → Reply
      • »
        »
        »
        »
        17 months ago, hide # ^ |
         
        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

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

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

→ Reply
»
17 months ago, hide # |
 
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.

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

1122?2024/11/22?

→ Reply
»
17 months ago, hide # |
← 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.

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

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

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

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

→ Reply
»
17 months ago, hide # |
 
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.

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

Please keep uploading testcases on dropbox link.

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

C~F are all very good problems.

→ Reply