UNIQUE VISION Programming Contest 2024 Spring(AtCoder Beginner Contest 346) Announcement

→ Обратите внимание

До соревнования
Codeforces Round 995 (Div. 3)
00:54:09
Зарегистрироваться »

→ Трансляции

Codeforces Round 995 Solution Discussion

aryanc403

До начала 03:14:08

Всё →

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

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

UNIQUE VISION Programming Contest 2024 Spring(AtCoder Beginner Contest 346) Announcement

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

We will hold UNIQUE VISION Programming Contest 2024 Spring(AtCoder Beginner Contest 346).

Contest URL: https://atcoder.jp/contests/abc346
Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20240323T2100&p1=248
Duration: 100 minutes
Writer: yuto1115, cn449, physics0523, nok0, kyopro_friends, leaf1415, ynymxiaolongbao
Tester: sotanishy, toam
Rated range: ~ 1999
The point values: 100-200-250-400-450-525-575

We are looking forward to your participation!

atcoder

atcoder_official
9 месяцев назад
74

Комментарии (74)

Написать комментарий?

Ashnu

9 месяцев назад, # |

-26

Hope to solve a,b,c,d,e.

→ Ответить

Ashnu

9 месяцев назад, # |

-74

I hope all problems are Div3 type only.

Atcoder Beginner contest == Codeforces Div 3

→ Ответить

xiaobai7363

9 месяцев назад, # |

-20

Hope to solve ABCDEF.

→ Ответить

Eternal_crystal

9 месяцев назад, # |

-20

Hope to solve ABCDE. I hope I won't be hacked this time

→ Ответить

railgunjjj

9 месяцев назад, # |

Hope to solve ABCD

→ Ответить

human.exe

9 месяцев назад, # |

Hope to solve ABCDE

→ Ответить

rui_er

9 месяцев назад, # |

+64

Problem E is almost the same as 2023 Chinese NOI Spring Test Problem A. 涂色游戏 (paint), and is an easy version of LGR-162-Div.3 Problem D. 头 which I coauthored.

→ Ответить

nichke

9 месяцев назад, # |

← Rev. 2 →

Please, can somebody tell me why this fails on F it literally binary searches the first left position to place "K" characters for every character in T. These contests are literally implementation only and I hate every minute of it.

16xAC 37xWA Link

→ Ответить

Rideris

9 месяцев назад, # |

I deducted the n^2 brute force solution mentioned at the end of G's editorial in 5 min, but just can't find a way to use a data structure to optimize it:( maybe i just ain't Chinese enough:P

→ Ответить

SpecialOperations0

9 месяцев назад, # ^ |

-10

registered 5 months ago and already master, i am pretty sure that you are chinese D:

→ Ответить

nika-skybytska

9 месяцев назад, # ^ |

In sweepline you add and remove segments. Use a lazy segment tree to maintain the number of segments that cover each point. Adding is += 1 on a range and removing is -= 1 on a range. Query union length after each operation. It is n minus the count of zeros. The count of zeros is the count of minimums if the minimum is zero and zero otherwise code

→ Ответить

Rideris

9 месяцев назад, # ^ |

yeah i figured out the sweepline part with ease but couldnt think of the sgt part...

→ Ответить

Chimpanzee

9 месяцев назад, # |

wtf is F, I cannot understand why this fails: binsearch on K, for checking each character, binsearch again on how far we have to go

→ Ответить

cleanser

9 месяцев назад, # ^ |

I did the same thing but idk where I'm getting 2 WAs from.

→ Ответить

kHarsh3715

9 месяцев назад, # ^ |

← Rev. 2 →

+14

For me, the 2 WAs was because of limits of binary search. Initially I put high to be 1e18 but I don't know why this was causing 2 WAs. Changing it to n*(size of s) worked. 1e18 probably caused overflow somewhere i don't know why. But even 1e17 limit which is 1e12*1e5 was causing 1 WA.

→ Ответить

UP84

9 месяцев назад, # ^ |

← Rev. 2 →

The upper bound of length is (n*(size of s))/(size of t),if you take a take k such that k*(size of t) > 2^63,it can overflow.

→ Ответить

kHarsh3715

9 месяцев назад, # ^ |

ohh yeah, wierd 1e17 failed, but n*(size of s) passed and I don't think it is possible that they did not put n = 1e12 and |s| = 1e5 testcase. Maybe i got lucky lol.

→ Ответить

redcircle

9 месяцев назад, # ^ |

Try this test: n = 1

s = a

t = aaaaa

ans = 0

→ Ответить

harvey_wzy

9 месяцев назад, # ^ |

Me:

1
aa
aa

The answer is 1 and my code output 0. Now I fixed the code by this test.

→ Ответить

fclvbfm934

9 месяцев назад, # ^ |

Had the same issue where I put 1e18 and got 2 WAs. Turns out this is because of overflows on long longs when you do the binary search. Switching to bigint made it AC.

→ Ответить

lw22019

9 месяцев назад, # ^ |

Me too,I used "long long" at first and got "WA",and I used "unsigned long long" and got "AC".

→ Ответить

UP84

9 месяцев назад, # ^ |

This works, i did the same thing, code -Link

→ Ответить

nichke

9 месяцев назад, # ^ |

-8

Did the same and failed 37 WA lol. It's a shit problem tbh just implementationforces.

→ Ответить

nika-skybytska

9 месяцев назад, # ^ |

+11

It may be beneficial for you to focus on improving your implementation or at least debugging skills. It's unfortunate to miss out on some good points because of silly bugs but it's on you.

→ Ответить

TG-STUDIO

9 месяцев назад, # |

first time with Corona Virus （just to D sadness）say no more go to sleep

→ Ответить

cleanser

9 месяцев назад, # |

+10

Is F binary search on answer and for each search, you binary search to find when you have enough letters? My solution was n(logn^2) but it TLEs on a couple cases.

→ Ответить

Farhan20

9 месяцев назад, # ^ |

+17

Binary search for problem F will work perfectly. I used binary search for problem F and got accepted.

Here is my submission link : https://atcoder.jp/contests/abc346/submissions/51615694

Let, p = s.size() and q = t.size()

Then, time complexity : O(q * log(1e17) * log(p))

→ Ответить

TheScrasse

4 месяца назад, # ^ |

Sorry for necroposting. I've just got TLE with your solution (which is also the intended one), I failed to optimize the constant, so I decided to write $$$O(n \log(ns))$$$, which is not that different.

Fast solution

→ Ответить

650iq

9 месяцев назад, # |

Today was a bit on easier side..could solve upto E :)

→ Ответить

amoad

9 месяцев назад, # |

How to solve D using DP ?

→ Ответить

alpha1215

9 месяцев назад, # ^ |

you can do it with prefix sum

→ Ответить

kishor236jha

9 месяцев назад, # ^ |

can u explain prefix sum approach?

→ Ответить

alpha1215

9 месяцев назад, # ^ |

idea

code

#include<bits/stdc++.h>
using namespace std; 
char nl = '\n';
using i64 = long long;

void solve(int t) {
    // cout << "test #" << t << << nl;
    int n; cin >> n;
    string str; cin >> str;
    vector<i64> C(n);
    for(auto& a : C) cin >> a;
    vector<i64> match(n), not_match(n);
    i64 a = 0, b = 0;
    for(int i = 0; i < n; i++) {
        if((i & 1) == str[i] - '0') a += C[i];
        else b += C[i];
        match[i] = a;
        not_match[i] = b;
    }
    a = 0, b = 0;
    i64 ans = LLONG_MAX;
    for(int i = n - 1; i > 0; i--) {
        if((i & 1) == str[i] - '0') a += C[i];
        else b += C[i];
        ans = min(ans, min(match[i - 1] + b, not_match[i - 1] + a));
    }
    cout << ans << nl;
} 

int main() {
    int tt = 1;
    // cin >> tt;
    for(int t = 1; t <= tt; t++) solve(t);
}

→ Ответить

kishor236jha

9 месяцев назад, # ^ |

sorry i really not getting your ideas can you explain more?

→ Ответить

alpha1215

9 месяцев назад, # ^ |

← Rev. 3 →

you have to make string such that s[i] == s[i + 1] for exactly one i and the const should be minimum the idea is calculate cost for all possible i for both cases s[i] == 1 and s[i] == 0

suppose we choose s[i] == 0 and i is odd
now on the left <= i
all 1's should occur at even position
all 0's should occur at odd position

on right >= i + 1
all 1's should occur at odd position
all 0's should occur at even position

total cost = cost of making left + cost of making right

similarly do it for s[i] == 1

and the ans will be min cost considering all possible i for both cases

→ Ответить

yadavDipesh

9 месяцев назад, # ^ |

code

→ Ответить

_Aryan_

9 месяцев назад, # |

how to do D with dp?

→ Ответить

brave-kid

9 месяцев назад, # ^ |

← Rev. 4 →

$$$dp[pos][prev][count]$$$

pos = current position

prev= value of previous character

count = min( 2 ,count of $$$1 \le i \le n-1$$$ where $$$s_i=s_i+1$$$)

→ Ответить

alpha1215

9 месяцев назад, # ^ |

← Rev. 3 →

for s[i] == s[i + 1] you just have to make sure either on the left for all k <= i parity of k == s[k] and on the right k >= i + 1 parity of k != s[k] or vice versa

→ Ответить

_Aryan_

9 месяцев назад, # ^ |

← Rev. 3 →

i am getting wrong on 3 test cases. What have i missed?

Code

void _segfault_()
{
    ll n; cin >> n;
    string s; cin >> s;
    s = '@' + s;
    vector<ll>vec(n + 1);
    for (ll i = 1; i <= n; i++)
        cin >> vec[i];
    ll dp[n + 5][3][3];
    for (ll i = 0; i < n + 4; i++) {
        for (ll j = 0; j < 3; j++) {
            for (ll k = 0; k < 3; k++) {
                dp[i][j][k] = LLONG_MAX / 2;
            }
        }
    }
    for (ll i = 0; i < 3; i++) {
        for (ll j = 0; j < 3; j++) {
            dp[0][i][j] = 0;
        }
    }
    for (ll i = 1; i <= n; i++) {
        for (ll j = 0; j <= 1; j++) { //lst character
            if (s[i] - '0' == j) {
                dp[i][1][j] = min({dp[i][1][j], dp[i - 1][0][j]}); //already 1 pair done
                dp[i][1][j ^ 1] = min({dp[i][1][j ^ 1], dp[i - 1][1][j] + vec[i]}); // doing at curr indiex
                dp[i][0][j ^ 1] = min({dp[i][0][j ^ 1], dp[i - 1][0][j] + vec[i]});
            }
            else {
                int k = s[i] - '0';
                dp[i][1][k] = min({dp[i][1][k], dp[i - 1][1][j]});
                dp[i][1][k ^ 1] = min({dp[i][1][k ^ 1], dp[i - 1][0][j] + vec[i]});
                dp[i][0][k] = min({dp[i][0][k], dp[i - 1][0][j]});
            }
            // cout << dp[i][0][0] << " " << dp[i][0][1] << " " << dp[i][1][0] << " " << dp[i][1][1] << endl;
        }
    }
    cout << min(dp[n][1][1], dp[n][1][0]) << endl;
}

https://atcoder.jp/contests/abc346/submissions/51621500

→ Ответить

Yugandhar_Master

9 месяцев назад, # |

Solved all problems after so many contests, thank you for the contest

→ Ответить

Farhan20

9 месяцев назад, # |

← Rev. 5 →

+10

I have an edge case for problem F.

testcase :

aaa

expected output : 3

But output of my accepted code for this testcase is 1. So, my code should got WA verdict. But my code got accepted.

Here is my submission link : https://atcoder.jp/contests/abc346/submissions/51615694

→ Ответить

nichke

9 месяцев назад, # ^ |

Mine gives 3 lmao but still fails 37 cases. Can you try finding a counter for mine please?

Submission

→ Ответить

variety-jones

9 месяцев назад, # ^ |

Take a look at Ticket 17424 from CF Stress for a counter example.

→ Ответить

nichke

9 месяцев назад, # ^ |

Thanks so much, I rounded one division down instead of up and messed up whole problem. :(

→ Ответить

_Shimla_05_

9 месяцев назад, # ^ |

+15

10 yyqml y answer should be 20 , your code gives 21

→ Ответить

nichke

9 месяцев назад, # ^ |

I got it, I rounded down division in one place instead of up. Thanks.

→ Ответить

rishichowdhury711

9 месяцев назад, # |

I have a question for problem B. I solved it in this manner: https://atcoder.jp/contests/abc346/submissions/51573486.

I was curious though, what if the values of W and B are very large(upto 1e18 or 1e9). In that case how will I be able to approach the problem. Is that even solvable? I am not able to think of any solution .Any help would be appreciated. Thank you

→ Ответить

blaze

9 месяцев назад, # ^ |

Iterate over all starting points on the string and calculate how many strings you need for b since there are less occurences of b in the strings and then iterate over the remainder of the string.

→ Ответить

alpha1215

9 месяцев назад, # ^ |

yes

how

→ Ответить

shivam_sikotra

9 месяцев назад, # |

In B, how answer is "No" for W=7,B=5???

→ Ответить

rainbowtable

9 месяцев назад, # ^ |

the answer is Yes for w=7 and b=5

→ Ответить

Wasif_Shahzad

9 месяцев назад, # ^ |

that's the original string itself so the answer is Yes

→ Ответить

trytoqualify2025voi

9 месяцев назад, # |

absolutely interesting problem, G is hard but the tutorial is very clear.

→ Ответить

RYOMEN__SUKUNA

9 месяцев назад, # |

-13

This Round was really amazing. I really enjoyed this round. The problems are very good

→ Ответить

as_09

9 месяцев назад, # |

← Rev. 2 →

Can anybody tell me why this code is giving RE in problem D. Link to solution: https://atcoder.jp/contests/abc346/submissions/51621300

→ Ответить

nika-skybytska

9 месяцев назад, # ^ |

Because your memory usage (3628612 KB) is greater than the memory limit (1024 MB). You probably run into bad_alloc

→ Ответить

as_09

9 месяцев назад, # ^ |

Can you tell why my code memory usage exceeds, as it is a simple dp solution.

→ Ответить

llc5pg

9 месяцев назад, # ^ |

I modified your submission into this Now it passes. The idea is to change string to string& in the function declaration.

→ Ответить

as_09

9 месяцев назад, # ^ |

Ohh shit man silly error. Thanks for your help.

→ Ответить

sergiu128

9 месяцев назад, # |

← Rev. 2 →

For D, I don't really get why this (http://atcoder.jp/contests/abc346/editorial/9651) is a correct solution. I don't understand how the answer is computed. I thought that if n is even, then the series first character must be different than the last character, so ans = min(ans, l0[i] + g1[i]) and ans = min(ans, l1[i] + g0[i]). If n is odd then the first and last characters are the same so ans = min(ans, l0[i] + g0[i]) and ans = min(ans, l1[i], g1[i]).

However I see that doesn't matter for the solution. I'm confused — can anybody explain it to me?

→ Ответить

aryanc403

9 месяцев назад, # ^ |

Here is the crux of the idea

→ Ответить

sergiu128

9 месяцев назад, # ^ |

Thank you! Everything is clear to me until the last step. For the last point, isn't the validity of a pair out of the 4 based on whether n is even or odd? What i am saying is that if n is even, then (pref0, suf0) and (pref1, suf1) are valid, and if n is odd, then (pref0, suf1) and (pref1, suf0) are valid. What am i missing here?

→ Ответить

aryanc403

9 месяцев назад, # ^ |

Yes, thats the correct interpretation of the last line.

→ Ответить

monkey_d_viper

9 месяцев назад, # |

can i do problem G by taking number of elements to right until not finding current element and left and add to result like res+=l*r is this wrong approach please help me

→ Ответить