AtCoder Beginner Contest 381 Announcement

4 weeks ago, # |

-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?

→ Reply

bramar2

4 weeks ago, # ^ |

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

xcx0902

4 weeks ago, # ^ |

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.

→ Reply

4 weeks ago, # |

-9

Why is there no buzz here?

→ Reply

Horcrux983282

4 weeks ago, # |

G is more hard then past G !

→ Reply

future_zyl

4 weeks ago, # |

-6

This may be a challenging G for its hiiiiiiiiiigh score!

→ Reply

CarroT1212

4 weeks ago, # |

wait why friday?

→ Reply

Yugandhar_Master

4 weeks ago, # ^ |

Because ARC on Saturday and AGC on Sunday

→ Reply

Akil_Newaz_Chy

4 weeks ago, # ^ |

← Rev. 3 →

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!

→ Reply

4 weeks ago, # ^ |

'coz it's 11/22

→ Reply

Cashda

4 weeks ago, # |

Wait, why will it hold on Friday?

→ Reply

alyoks1

4 weeks ago, # |

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

→ Reply

ananthak

4 weeks ago, # |

Weak system tests on D!!

My solution passes system tests but fails for this testcase:

4
2 1 1 2

→ Reply

4 weeks ago, # |

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

4 weeks ago, # ^ |

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

→ Reply

4 weeks ago, # ^ |

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.

→ Reply

bs_commander

4 weeks ago, # ^ |

stop learning useless algorithms.learn how to use binary search

→ Reply

mRXxy0u0

4 weeks ago, # |

Extremely difficult for problem G!

→ Reply

juruoA

4 weeks ago, # |

+14

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

→ Reply

4 weeks ago, # |

← Rev. 6 →

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

4 weeks ago, # ^ |

← Rev. 2 →

2
2 2

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

→ Reply

4 weeks ago, # ^ |

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

→ Reply

4 weeks ago, # ^ |

← Rev. 2 →

8
2 2 2 1 2 2 3 3

ans is 4

clear will not change all elements to 0

→ Reply

4 weeks ago, # ^ |

← Rev. 2 →

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

4 weeks ago, # ^ |

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

4 weeks ago, # ^ |

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

→ Reply

4 weeks ago, # ^ |

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

→ Reply

qiuxioahang

4 weeks ago, # ^ |

you are right , it helps me!

→ Reply

MightZero

4 weeks ago, # |

← Rev. 2 →

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

It's suggested to change the dataset.

→ Reply

MightZero

4 weeks ago, # ^ |

← Rev. 2 →

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

lnw143

4 weeks ago, # |

+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.

→ Reply

4 weeks ago, # ^ |

E is sphrase table and F is dp

it just uses string to show the problem

but still shit

→ Reply

Akil_Newaz_Chy

4 weeks ago, # ^ |

Can you please explain problem F in details ?

→ Reply

4 weeks ago, # ^ |

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

dan04

4 weeks ago, # ^ |

← Rev. 2 →

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

4 weeks ago, # ^ |

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

→ Reply

4 weeks ago, # ^ |

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

My logic.

Build a prefix sum of 1s(array a) and 2s(array b).
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).
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

4 weeks ago, # ^ |

maybe

7 1
111/222
2 6

is a hack

→ Reply

4 weeks ago, # ^ |

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

konjachzx

4 weeks ago, # ^ |

← Rev. 2 →

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

4 weeks ago, # ^ |

What is dichotomy?

→ Reply

4 weeks ago, # ^ |

binary search method

→ Reply

4 weeks ago, # ^ |

Ohh yeah. binary search looks fine for this question.

→ Reply

truth

2 weeks ago, # ^ |

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

alpha1215

4 weeks ago, # |

+13

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

→ Reply

vector1024

4 weeks ago, # |

Is there any thing wrong in this code?

→ Reply

konjachzx

4 weeks ago, # ^ |

← Rev. 2 →

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.

→ Reply