Codeforces Round #807 (Div. 2)

№	Пользователь	Рейтинг
1	ecnerwala	3648
2	Benq	3580
3	orzdevinwang	3570
4	cnnfls_csy	3569
5	Geothermal	3568
6	tourist	3565
7	maroonrk	3530
8	Radewoosh	3520
9	Um_nik	3481
10	jiangly	3467

№	Пользователь	Вклад
1	maomao90	174
2	awoo	164
2	adamant	164
4	TheScrasse	159
4	nor	159
6	maroonrk	156
7	-is-this-fft-	150
8	SecondThread	147
9	orz	146
10	pajenegod	145

Hello Codeforces,

We are glad to invite you to Codeforces Round 807 (Div. 2), which will be held on Jul/15/2022 16:35 (Moscow time). As usual, the round will be rated for participants with ratings lower than 2100, while those who have higher ratings are encouraged to participate unofficially. Please note the unusual start time.

You will be given 6 problems to be solved in 2 hours and 15 minutes. There may or may not be interactive problems, so you are encouraged to prepare in case they do appear by reading this guide.

The round is authored by abc241 and me, while joining us is also inwbearX who contributed significantly to the preparation. This is our first time setting rounds in Codeforces, and it wouldn't be possible if there were no support from the following people.

errorgorn for fantastic coordination.
KAN, mtw, geranazavr555, unreal.eugene and MikeMirzayanov for translating the statements into Russian.
antontrygubO_o, kevinxiehk, mango_lassi, Adam_GS, mtw, Utkarsh.25dec, yz_, thanhchauns2, TLP.39, 36champ, jampm, DeMen100ns, Neothehero, and somerandomaltacc3034 for testing the round.
MikeMirzayanov for Polygon and Codeforces.

The score distribution is $$$500$$$ — $$$1000$$$ — $$$1250$$$ — $$$1750$$$ — $$$2500$$$ — $$$3000$$$.

We are looking forward to your participation. Good luck and enjoy our round!

Update: the editorial is up!

Update 2: Winners!

Div. 2

Div. 1 + Div. 2

char ans(int k, deque<char> &d, vector<pair<int, int>> ops, int current_length) { if(k < d.size()) { return d[k]; } else { int previous_length = current_length - ops.back().second + ops.back().first; if(k < previous_length) { ops.pop_back(); return ans(k, d, ops, previous_length - 1); } int diff = k - previous_length; int t = ops.back().first; ops.pop_back(); return ans(t + diff, d, ops, previous_length - 1); } }

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

Показать архивные | Написать комментарий?

thanhchauns2

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

+105

As a tester, please give me contribution.

One of my favourite rounds.

→ Ответить

nyagami

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

-39

ok, that's enough information to make me ignore this contest

+46

As your senpai, that made me feel sad.

TrendBattles

← Rev. 2 →

-10

I would say when a candidate master (or higher) claims that a contest is in favor of his, it's much more overwhelming for me since I could only do up to 1400+ (maybe 1500 or 1600)

doj

-12

As we know, A round author must be at least expert. Then, how a specialist is the author of this round?

At least one of the authors must be. Not all of them.

errorgorn

+37

Do you judge contests by only problems A and C...

tgp07

oh wow

-19

Absolutely no, I read all the problems. They are interesting.

kevinxiehk

+49

As a tester, the problems are interesting and high quality, also be sure to read all problems.

.Ghost.

"High quality"? Is that a caution for newbie,pupil and specialist guys? :")

+41

Nope :D

I meant that the difficulties are well balanced, statements are easy to understand and the topics are also diverse. All in all, it's a fun contest for people of all ratings!

DeMen100ns

+30

As a tester, this round's problem-set interested me so much. Highly recommend reading all problems.

isirazeev

Meme

jiangbowen

+31

Hope that this will be my last rated div2.

+17

2099! I can feel your pain bruh :)

borntobewildandfree

2099 :))))))

Graygoo_401

2099/kk

Eason9002

+13

I think you will become Master in this contest,come on!

Lord_David

Anya motivation.

Anya going to make father proud!

Do you watch spy X family? I like your sophisticated taste. I watch it too XD. Edit: I'm going to keep my Santa hat on for this Christmas as well lol.

white_devil_403

Things turned out bad,details can be found in this blog.

Abito

You became master in the end anyway

jampm

+47

As a tester, I gotta stop doing this as a tester comments but I mean this round is really really cool, the problems are very interesting idea-wise and that's smth I really appreciate. Congrats to the problem-setters, and I hope u enjoy this round as much as I did!

MarkBcc168

Auto comment: topic has been updated by MarkBcc168 (previous revision, new revision, compare).

ldyllic

+28

Have a feeling that a lot of people will be one hour late for the contest.

sugmedic

I would have been an hour late if I didn't see this comment. Thanks.

← Rev. 4 →

+24

Watch out! The contest is 1 hour earlier than usual time.I also didn't notice it first :3

Platanito_Frito

+119

Codeforces bathroom?

Nxxlt

I didn't get. Can u explain the meme?

Go to SlavicG's heat map and find the seven differences.

I found only 5.

Even better XD

Eclipse03

Lol that is hilarious hahaha

jijidawang2

+11

No, it's GitHub Bathroom XD

a_ravi

seems like leetcode bathroom

yogesh_2249103

Hope This round would be my last round as a pupil

Aravind

Pupil Tag is not leaving me so easily :(

FullFocus47

I'm hard stuck as well :)

ganesh_6

Me too, though i became Specialist earlier 2 or 3 times, I want to be a real Specialist

xyz_kr

me too

Congratulations, I think you'll be cyan today, I lost it with time and penalties:(

Hope ths will be my last div2 as Expert

M_bolshakov

Me too :D

SHAHEEN

Note the unusual start time :)

nor

+29

Given the authors, it looks like the round will be IMO-forces (but in a good sense).

IMO — International Math Olympics? :)

Sorry I just don't know what does it stand for

pigmike

-13

IMO-forces is never good

Olympia

I prefer IMO-forces/thinkforces :p

vitosevskich

BTW, IMO is taking place right now.

somerandomaltacc3034

+25

As a tester, hi.

another_love

I wish high rating for everybody, who reads this comment )

ONEHUNDREDPUSHUPS

+14

I usually don't pass contests because I always forget about them, and this has happened so many times that I now set an alarm for each new contest and I will definitely pass this contest!(I really hope)

nikalla

← Rev. 3 →

-22

-15

geniorzity

Very excited!!

same

IDE_AL

I hope today's competition will be amazing. Let's try to solve more problems. I wish you all good luck and success! I believe in each of you.

Retired_Snow

good luck！！

018429

As a participant, please give me contribution.

I hope this will be my last round as newbie :) Good luck guys!

Fagun

I hope i will be solve problem C

Math_is_Good

+10

And i hope for D.

784

And I hope for E

And I hope for A

chjcoder

lol

dukhi_insaan

I hope nothing

I am sure I will not able to do D problem.

abcsumits

+1 only 3 min left ...

Habib_2010

Thanks for the support Alfheim. ::::))))

badluck_1441

expecting to reach expert in next few rounds

same. Edit: It happened XD

hbhz_zcy

interactive problems do make me scared

+32

A friendly reminder that the contest starts in about half an hour. Good luck!

naman3878

as a not good problem solver and 900 rating should i dare take participate in this contest?

pinkhippo

10 minutes left before the start of the contest. Looking forward to it!

50_shades_of_whey

Looking at the submissions, C should be easy but holy hell I feel incredibly dumb for not being able to solve it

c is good problem,i am not able to understand how this much submissions happen.

Literally_Me

idea was easy but implementation was tuff

yeah ...

introart

Because Codeforces is unofficially sponsored by Telegram. If you know you know.

Deep one :)

MarquesLua

I got TLE in some submissions where the verdict should be WA or RTE. Why did this happen?

akshayvijay

Because your solution was not able to reach the final solution where it can be decided about the correctness of solution.

SalmaHatem_

I think problems are a bit hard!

Bn_Gaber

How to solve C ?

EmilyBloom

recursion. Try to find in which of the copy paste operation we performed.

can be done iteratively as well

barun511

For every query, process operations backwards one by one, keeping track of the current length of the string. Note that each operation adds (r — l + 1) length to the string.

Suppose k <= length before the operation. Then just throw away the operation and reduce the length.

Suppose k >= length before the operation. Then if the operation is from l -> r, then the answer for k — previous length is the same as the answer for l + k — previous length, so just recursively find the answer for such a k.

Cereal2

Similar to what EmilyBloom and barun511 said, you should answer each of the queries using recursion.

Code Here

// YoRepi7

#include <bits/stdc++.h>
 
using namespace std;
using ll = long long;
using vb = vector<bool>;
using vl = vector<ll>;
using pl = pair<ll, ll>;
using vpl = vector<pl>;
using vc = vector<char>;
using vs = vector<string>;
 
#define forn(i, n) for (ll i = 0; i < n; i++)
#define rofn(i, n) for (ll i = n; i >= 0; i--)
#define FOR(i, a, b) for (ll i = a; i < b; i++)
#define ROF(i, b, a) for (ll i = b; i >= a; i--)
#define TRAV(a, x) for (auto &a : x)
#define ABC(c) for (char c = 'a'; c <= 'z'; c++)
#define all(x) begin(x), end(x)
#define sor(x) sort(all(x))
#define rsor(x) sort(all(x), greater<ll>())
#define pb push_back
#define mp make_pair
#define ins insert
#define ub upper_bound
#define lb lower_bound
#define len(x) (ll)(x).length()
#define sz(x) (ll)(x).size()
#define f first
#define s second
#define dbg(x) \
	TRAV(a, x) \
	cout << a << " "
#define prll(x) cout << x << endl
#define prllpi(p) cout << p.f << " " << p.s << endl
#define traverse(x) \
	TRAV(a, x)      \
	prllpi(a)
#define readvi(a, n) forn(i, n) cin >> a[i]
#define readvpi(a, n) forn(i, n) cin >> a[i].f >> a[i].s
#define gcd(a, b) __gcd(a, b)

vl lft; vpl rng;
ll n, c, q;

ll get(ll x){
	ll idx = upper_bound(all(lft), x) - begin(lft);
	return idx - 2;
}

ll find(ll x){
	ll pos = get(x);
	if(pos < 0){
		return x;
	} else {
		ll d = x - lft[pos + 1];
		return find(rng[pos].f + d);
	}
}

void solve(){
	cin >> n >> c >> q;
	lft.clear(), rng.clear();
	string s; cin >> s;
	ll cur = n;
	lft.pb(0);
	forn(i, c){
		ll l, r; cin >> l >> r; --l, --r;
		lft.pb(cur);
		rng.pb({l, r});
		cur = cur + r - l + 1;
	}
	forn(i, q){
		ll k; cin >> k; --k;
		cout << s[find(k)] << endl;
	}
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll t; cin >> t;
	forn(i, t){
		solve();
	}
	// solve();
}

It can be done slightly faster iteratively. 164294136

Why cannot we see tutorial yet?

The editorial is up now.

waiting for solution ... i think it would take hardly 5 — 10 min... everyone is becoming fast here.

nimitdidwania27

In some contests there is a hacking phase of 12 hours in some there is not. Can anyone tell me in which contests hacking phase is there and in which it is not??

eagle_02

+20

in educational rounds , in div4 and in div3 we have 12 hrs hacking phase

divyansh_sahu

Contests like educational, div 3 and div4 have a dedicated hacking phase of 12 hours whereas other contests (like div2) have hacking phases which are active only during the contest.

riddle_7

Any hint for D?

+12

Think of the 1's as groups

remastered

Look at what happens to the groups of consecutive ones/zeros under the operation.

Individual

I may be wrong and fail the system tests so take this with a grain of salt, but I figured that the condensed version of the strings (let's say, the array [1,5,2,3] for the string 10000011000) cannot change its size using any number of operations (meaning no continuous segment of zeroes or ones can disappear or be born). That observation helped me.

First Div 2 where I solved 4 problems! Edit: Yay! I'm an expert now!

SunMendi

For me, Problem B seems so much confusing. if we take a test case such as : n=5 the array looks like 2 1 1 0 4 how is the answer 5? I think the answer should be 7.

One sequence of moves is

i=1 j=4: [1,1,1,1,4]
i=1 j=5: [0,1,1,1,5]
i=2 j=5: [0,0,1,1,6]
i=3 j=5: [0,0,0,1,7]
i=4 j=5: [0,0,0,1,8]

anj20

No it should be 5 ig how 7?

can someone pls give me some hints for problem E?

Thanks in advance.

You can see some hints in the editorial :)

AlexMari

Very nice problems!Congrats to authors!

I really liked today's contest, I was able to solve the first three problems, but I didn't have enough time for the fourth one, in general, the problems were very interesting and exciting, especially problem C, thanks to all the creators of this contest!

null0124

+15

A harder version of problem D appeared in yukicoder, a Japanese contest: https://yukicoder.me/problems/no/1209.

Well, I apologize for that, but please understand that there are just too many problems out there, and it's impossible to check them all. Thanks.

I don't think it should've been noticed, but I just think it is beneficial information so I posted. Sorry for misunderstandable post. Thank you for a great contest. I enjoyed it a lot!

Keven

In problem E, I try binary search + segment tree, its time complexity is O(nlog^2n), when n equal 2e5, it remain less than 8e7, why it get TLE? code link

Based on our testing, the segment tree has a high constant factor that an O(nlog^2 n) is very hard to pass. We apologize for the strict TL.

Oh, I ignored those constant. Thank you for your reply!

+16

Oh my god, this isn't funny anymore. In round 804 my new rating was 1898, but I wasted 1 attempt on C because I put whe wrong module (998244353, from the previous round, not 1e9+7). But today, my new rating Again seems to be 1898, according to Carrot, and today I also wasted an attempt, because I forgot to write something I invented at the beginning, which makes me miss my first CM again, And a div1 round for the first time. F

But the round was great.

upd.: No, 1899.. That's insane.

AndrewPav

Internet in Serbia is very good guys. First 25 minutes I wasn't able to submit A, and then last 55 mins internet was so bad that I can't submit B or C(both was ac).

Who is stemroot?

stemroot

Guess. :)

TheStrongest

Раунд очень приятный, мне понравился. Отдельный респект за задачу C и задачу E. Правда Е я, к сожалению, не успел сдать во время раунда.

geranazavr555

+21

Ratings updated preliminary. Unfortunately Mike won't be in touch until July 19th, so cheaters from this round and further rounds will be removed later. We can guarantee that they will be removed not later July 20th.