Hi Codeforces!

*Sorry for being late for the announcement.*

I'm glad to introduce to you my first contest Codeforces Round #482 (Div. 2). It will take place on 14.05.2018 17:35 (Московское время).

You will have **5 problems** and **2 hours** to solve them.

The problems were prepared by me (Quyen Dinh), _Kuroni_ (Trung Dang) and _Shirone_ (Lam Le) with suggestions from FallingStar1709 (Nhat Hoang) and HaiDang2001VN (Dang Huynh). I would like to thank KAN for his great help in checking the problems and giving comments, Tommyr7 for testing all the problems and MikeMirzayanov for the awesome Codeforces and Polygon platform.

Note that the round is rated for everyone with rating below **2100**.

In this contest, you will meet *Kuro*, *Shiro* and *Katie*, the three naughty but smart cats who love asking thought-provoking questions. I hope you will find our problems interesting. Good luck to you all!

**UPD:** Also big thanks to cyand1317 for helping us with the problems and arsor for translating the problems into Russian. Sorry, I forgot you guys.

**UPD2:** The scoring distribution is **500 — 1000 — 1250 — 1750 — 2250**. Have fun!

**UPD3:** Congratulations to the winners!

Div. 1 & Div. 2:

*Our top 5 solved all the problems. Awesome!*

Official:

mama_budra (solved all problems!)

coach.31 (solved all problems!)

Thanks for everything! Here is the editorial.

Div-2 the most popular format of Codeforces round.

How did you know? Thanks for the information! You saved my day!

got inspirations from young problemsetter...hope for the best :D

A contest of Vietnamese :)

I'm worried all Asians love math & it's going to be some math/geometry contest FallingStar1709 :3

Although I have to study for the final exam, I am looking forward to join the contest because I want to increase my rating.

In my semester break...The only breaks I see are in my switch statements.

Haha...

I don't write switches :(

I think the round will be interesting and intriguing

Wow, This is the first time I saw the contest was prepared by Vietnamese people that are same my nationality. Hopefully, everyone will get a high rating.

Me too, first time I have seen. I hope the problems will be interesting.

We had some Vietnamese rounds before:

## Is It Rated?

The round is rated for everyone with the rating below 2100

Expecting a balanced contest....

... you will meet Kuro, Shiro and Katie'Katie' is how felines call a special hue only visible to them, I suppose?

It is :D

Thanks to the new rules! Now I can participate in div.2 contests!

Wish all

Candidate Masters(and all participants) can get high rating!Wow, Three cats are a hero to asking the question in this round.

Wish u all low ratings like me :(

Me, currently, reloading room's page to find someone, I can hack in problem A

Candidate Masters These Days..

If you think cf pretests are shit, try to get past the pretest 5 of problem B !!!

True Evil

please tell me the pretest 5 of problem B!

It's for the case that one of them has a letter all over the string(like aaaaa) then there's only one turn... Amazing that many people passed this on the first try :/

Why answer of this test is draw?

aaaaaaa -> aaaaaab -> aaaaaac -> aaaaaaa

aaaabcd -> aaaaacd -> aaaaaad -> aaaaaaa

abcdefg -> aacdefg -> aaadefg -> aaaaefg

1st guy and 2nd, both can win, hence draw

I got it wrong on pretest 10, don't know why.

Welp, the cats are smarter than me.

D was trivial, chess is harder :)

D problem was okay.

but in all honesty . .

If I ever see anyone playing a game like that , I will make sure they see meet their maker.

LOL

u can fold up the pizza and cut it！i think this round should be unrated...

Exactly! And keeping that in mind I tried for a hack with n=2 (3 pieces) for which 2 cuts are enough but it showed unsuccessful hacking attempt!

The shape and size of the pizza slices are the same. Therefore no folds are required.

Pizza with 3 slices of same shape and size can be created using 2 cuts if we fold the pizza by its diameter.

u can cut pizza into 8 slices by cutting and folding 3 times

when number of slices is even，one certainly can fold and get same shape

На Этот раз задачки были нормассс, правда не успел

Hack for B:

3

aaaa

aaab

bbbb

Answer is Draw.(My solution fails this test ;w;(I actually knew of this test but couldn't handle it correctly))

can you explain why answer is draw?

aaaa — aaab — aaac — aaaa

aaab — aaab — aaac — aaaa

bbbb — bbba — bbbc — bbbb

From

aaab

We can get bbbb obviously, so the score is 4.

How can we get a score of 4 from the other ones?

aaaa -> aaab -> aaac -> aaaa(second one is same as this one).

Hmmm, from my understanding the letter has to be different than the one which was at the corresponding position at the original string (without any prior modifications). If I am correct, the expected output should not be Draw.

"an arbitrary color which is different from the unchanged one"

This rule applies only for current turn.

While I enjoyed the other problems, the problem statement was confusing in this case. The word "unchanged" only has a meaning when the context is stated, which was not the case here.

aaaa aaab aaac aaaa

bobo contest gay B suka

too much dotka for you sir

How to solve D?

I didn't solve it completely but I think that segment tree storing divisors in each node + some additional data should work.

My solution kept sets for each possible k, 1 through 100.000. When adding a number u to the array (type 1) I go through all divisors of u, adding that u to each of sets where it qualifies with O(sqrt(n)) complexity (and O(log(n)) for each insert into a set). If the u is already in the array, I don't do anything (not sure if this improves anything but thought it might be a useful optimalisation).

Then, to answer a question for x, k, s, I check if k divides x with the Euclidean algorithm. If not, return -1, if yes, I check if the set for given k is non-empty and if it contains any number not greater than s-x. If so, I can start searching for the optimal solution within this set.

When I know which set I'm using and what is the maximal number from this set I can use, I can search bit-by-bit for the best solution, checking for every j-th bit (beginning with the greatest ones) if there exist a number in the set that satisfies both following conditions: 1) Its first j bits are the same as desired (i.e. all different from the x's bits or the same for those which cannot be different, based on previous steps) 2) It's not greater than s-x This can be done in logarythmical time for each bit.

Why do we need Euclidean's algorithm to check if

kdividesx? I thought meank|vandk|x?Yeah, you're right xD I guess my brain stopped for a while.

maybeit can be solved like this:construct a set which will store array values

since

k|gcd(x,v), if this possible thenx=p*kandv=q*k,if

x%k! = 0 then output is -1,else, iterate over values of , find in set if set, maximise zor to find answer

What should be answer of 3 bbbbaa ccccaa ddddde in B?

bbbbaa -> bbbbba -> bbbbbc -> bbbbbb

ccccaa -> ccccca -> cccccd -> cccccc

ddddde -> dddddf -> ddddde -> dddddd

so the answer will be "Draw".

Got it ty:)

3 aaaaaacc xxxxkkkk xxxxkkkk ans : Kuro

3 aaaaaa abcdxx abcdxx ans : Draw -> Kuro (Sorry My mistake)

1 aaaaaaAAAAAA aaaaAAAAAAAA aaAAAAAAAAAA ans : Katie

My B hack data!! Unfortunately, I realized I'm wrong after lock :(

I don't get it — isn't the second case supposed to be Kuro?

why is second test case "Draw"?

I got it..

aaaaab->aaaaac->aaaaaa

aaaaaa -> aaaaab -> aaaaac -> aaaaaa

Problem D. Why O(NMlog10^5) gets TLE where N = number of query1 and M = number of query2 ?

For example, if

N= 50000 andM= 50000, thenN*Mis a rather big number.My head just blow up. what a stupid.

Fuck statement B, how could

color segmentmeans a single element!!!fuck all problems I think :|

I think segment means the interval length >=1

Yes, but not in problem B

When I was hacked, the more I reading PB again, the more content I can't understand, what is "one color segment"'s real meaning......

hard to understand the statement in pD and pE :(

RIPrating. PS :- bad problem statements and wrong constraints (in C atleast)because n is long?

ya sry , i copy pasted my previous code. fucking silly me!

whats wrong with this solution for B? https://ideone.com/Gbvho1 i just found the string with maximum frequency of a character.

Just a side note: In C, n >= 1 but n = 1 will not be possible according to constraints.

3 aaaa aaab bbbb

Answer is Shiro right?

No, it is Draw

Kuro can do a

aaaa -> aaab -> aaac -> aaaa

chết chưa bobo suka

Could't open the hack page for a long time up to end of the contest!

problem B, what is the answer for this test:

5

aa

aa

as

I tried to hack a solution with this test and the solution answer was "Draw" but I got "Unsuccessful hacking attempt" !!!

Edited

Everone can make aa.

aa->ab->aa->ab->ac->aa

aa->ab->aa->ab->ac->aa

as->aa->as->ab->ac->aa

You use only 4 steps

In my test

n= 5, you are making only 4 movesIt's "Draw", right??

you can do 3 steps and the sequence stay same, aa -> ad -> as -> aa

This doesn't work only if you have to do 1 step

Great, I think I don't have to wait System testing now -_-

We all don't

aa -> ab -> ac -> ad -> ae -> aa

aa -> ab -> ac -> ad -> ae -> aa

as — > ab -> ac -> ad -> ae -> aa

Thanks!

Can someone explain why my hack with test is wrong: 3 aa bb ca. My solution gives "Katie" because of "Each move each of the friends must change exactly one section of the color in her tape to any other color chosen by her.". And solution that I tried to hack gives "Draw"

aa->ab->ac->aa

bb->bc->ba->bb

ca->cc->ca->cc

Thank you very much. I think this test will help many people!)

it's kinda obvious that this is "draw" because "aa" and "bb" are exactly the same strings and should give the same answer, so.

E: why

n= 50 withn^{3}solution?Maybe they wanted to allow

n^{4}solutions like mine!!n= 50 allowsn^{5}solution to pass with small constant..i really hate CF hacking system

a guy that luckily be the first one that could find trivial mistake made by 10 grey/green coder in his room could get more score than a hardworking coder that solve D in last 20 minute.

i think CF should limits the hacking attempt by a person (two or three hacking attempt for each problem)

I would say that pretests in div.2 should cover such obvious (but still easy to miss) cases like

n= 0 in task A because, yes, nobody should be able to get +1000 points in a couple of minutes by just typing 0 and clicking "Hack".But it doesn't feel right to limit the number of hacking attempts because even multiple hacks for the same problem may require you to read and understand various incorrect solutions and come up with unique testcases against each of them (today this was the case for me: I got 5 successful hacking attempts on problem B but I had to use 5 testcases slightly different from each other). These solutions can be relatively large and tough to understand, so I think that such challenges should be rewarded. After all, it's quite important to be able to read somebody else's code, to grasp the logic behind it and to find a counter example if the underlying logic is wrong. If you want to get a bunch of hacks on harder problems, you will have to sacrifice the time that you could have spent solving other problems (with no reward, i.e. successful hacks, guaranteed), so it's about time/risk management as well.

agreed with you. pretest must cover trivial test case so it won't create unfair advantage to the hacker

what is the purpose of the problemsetter by not covering trivial case such as n = 0? anyone know that this type of cases will produce lot of unfair hack.

unfortunately, there are a lot of contest that did not cover obvious test cases. it is really unfair for people that solved ABCD but lost to a hacker that solve ABC.

i think CF should have a hacking point for every problems :)

Even people who haven't solved any problem, and hacked as much as 10 codes in problem A are way ahead in standing than those who have solved even a single problem!

I think In solving problem D I was going in the right direction , whenever query of type 1 happens , find all its divisors and then make a trie for all those divisors in which we add the binary representation of the number v , but later read the problem statement correctly and found another condition that v + xi <= si . . now no idea how to solve this further keeping this condition in mind :'(. .

How did you people solve problem D , i think I was kinda going in the right direction

I didn't solve it. But my idea :

`save array as two dimension bool bit[512][512].`

`1) add u to array: bit[ u >> 9][ u & 511 ] = true;`

`2) find answer for x, k, s : 2.1) find that 0 <= ID < 512 that , x ^ (ID << 9) maximal. 2.2) for that ID go all 512 elements of ID's sub array.`

Вот и решение тоже готово

http://codeforces.com/contest/979/submission/38248944

yes you were. when you are searching the trie, keep in mind that the number you are searching (v) is <= si — xi, and you can verify this relation bitwise

Your thought process is correct. Let's assume we have BSTs instead of tries. Split the BST in two parts: (elements <= s — x) and (elements > s — x). Solve 706D - Vasiliy's Multiset on the first part. This takes time. (Note: Since a trie is essentially equivalent to a BST, I think this can also be done in O(logn) time, but I'm not sure how to implement this.)

You mean 01-trie, right? It's a way, but yes, it can't handle the condition : v + xi <= si

Instead, I used std::set in c++, which is more convenient.

And you can use the

`lower_bound`

function to find the minimal value, And you can solve the problem.If you give every node in 01-trie

`min[]`

value, you can also solve the condition.`min[node]`

means the minimal value in thesubtreeof the`node`

(if you know what I mean).If

`min[node] + xi > si`

, the subtree of`node`

will not have any`v`

that satisfy the conditions.Sorry, my English is poor. Hope you'll understand me.

I get what you are trying to say but all this did not come to my mind immediately , I just started coding what came to my mind in 5 minutes without even reading carefully , was frustrated because of B , but now that I know my approach was ALMOST correct , I am happy ,

as ajecc said above , I just have to add very few lines in my 01 trie searching to ensure the condition v <= s — x , . . I can rest in peace now , the contest was a disaster

the problem is shit!!!

I can't agree more.

the truth！

My honest respect to contest coordinators, setters, testers and to all who worked so hard to arrange this contest. But the contest experience was not good. Lagging from the start, could not submit test case for hacking purpose at the last 10 minutes of the contest. And when I finally submitted the test case before one minute it successfully uploaded but the status keeps loading and loading, even till now. Such an worst experience for me. Maybe it was not my day.

I can just hack others to get points in this contest.

I suddenly realize in Problem B we have to change per string for exactly n times. No less, no more.Crying...

How to solve D? Some kind of divisors search?

Not the best contest =/

Can anyone describe how to solve 979B - Treasure Hunt? Thanks!

I suppose next. Find letter with maximum M appearances (using map for example). It's Beauty before. One can change N letters in the ribbon. So one can increase M with N. But sum should be not bigger than ribbon length. Let

`T = min(M + N, ribbon length)`

. Special case is`M = ribbon length`

and`N = 1`

, here one have to change letter to another and`T = M - 1`

. Finally, compare T for men.Holy sh*t I thought that one letter only could be changed to its subsequent on the alphabet. Read over and over again the problem statements guys!

I lack of special case, probably it 's pretest 5.

I had a serious discussion with

Mike, I have decided that this contest is madeunratedLets make this the most down voted comment

problem B???? what are you saying???

Awesome contest, would be much better without hacks :D.

Just my thoughts.

For problem A, you could make statement more clear, that two best friends baffled me as n can be 0 or 1. Also this sentence — 'A cut is a straight segment, it might have ends inside or outside the pizza.'. I don't know if I'm only, but it took me some minutes to understand this. I think the word 'outside' here is not needed, it confuses. Or you could give a picture for making everything clear.

I hated problem B. Statement is really bad written. For example, look here: 'For example, the ribbon aaaaaaa has the beauty of 7 because its subribbon a appears 7 times, and the ribbon abcdabc has the beauty of 2 because its subribbon abc appears twice.'. You should clarify what does 'appear' mean here. Also 'one color

segment' is really confusing...Unbelievable. I've solved all and have only 300-points advantage concerning the guy who has only solved ABC. I think it isn't fair system, when I can lose the guy who have guessed to hack with the very easy trick, whereas he hasn't solved anything what I even though may try to call "problem", and not "exercise for blue coders".

Another hacking contest

why did you change the statements of problem B without an announcement?

Could you give more information, please? I didn't notice that.

They changed

`If there are at least two cats that share the beauty, print "Draw".`

to`If there are at least two cats that share the maximum beauty, print "Draw".`

without any notification.Actually you can't even pass sample test 2 if you follow the original instruction. So I think most people can guess what it really means.

why in problem C n can be equal 1???

Codeforces is like:

single line of mis-coding leads me to WA on C and I couldn't never fix it until the end of the contest.

As problem setters, we intended B to be a problem where people may think a bit out of the box (dealing with odd turns). But we made some serious mistakes (unclear statements, bad pretests) and I would like to apologize to all of the participants this contest. We are currently having a discussion about the aftermath of this contest.

Although I did the contest badly, overall problems are good. But it's also true there's some mistakes on statements :'(

Thanos: Half of submissions of problem B would cease to exists(snap)just like that.I think the statements are open to different interpretations.

That leads to lots of hacks and unhappy participants.

i agree with u

No one realizes the case where

When you want to hack because you know people will forget about this case...

... but you don't know how to hack.

but there's one thing...

there's one thing...

it's wrong contest to judge with :)

No need to make it unrated.Keep it rated. Problem statements were fine. Many people solved the questions so i dont have any complaints

upvoters : did contest with good score

downvoters : the others

fight of the most subjective voters

The statements weren't fine. Yes, the author's intended solution is to run back and forth between a->b->a. That's what the sample test case description says. Those who understood this way will be judged correct. But there's no problem at all to use a->b->c->a (or a loop longer than 3) under the given description.

What should be the answer of this test?

2 aabc aaab aaac

I believe that is Kuro, but I'm already confused because so many people's code print "Draw".

aaab->aaac->aaaa

Oh, you're right. ty!

Draw because in first move

aaac

aaac

aaad

in 2nd move

aaaa

aaaa

aaaa

Maybe CodeForces should disable hacks in Div.2 Only contests. Some experienced and high-rated (not me :P) candidate masters are solving problems, while others are obsessed with hacks. Inasmuch as there can be a lot of hacks, we obviously see that people solved 2 problems gets a higher rank that contestants solved 3, even 4 problems. There are three options. Make pretests strong so in the contest, it takes less time for the testing solution, and disable hacks. Make the contest full-feedback. Make 12/24 hours hacking phase after the contest. Thanks for reading!

Actually there is one more idea. Someone mentioned above somewhere in comments, I felt it was nice. Limit the number of hacks to 3 per question per person.

So you can start hacking too. No one is forcing you not to hack. Debugging is also an important asset to have

except that hunting for one if statement is not really debuging

But the motive of contest should not disturbed. Also does it seem good that hacking forms important part than solving. In that way coding clean code for A is important than solving(Or rather attempting) rest??

I also hacked some solutions and understand you that because of your skill is not good enough (do not get offensed from that, I'm just saying it to clarify my idea) you prefer hacking than solving further problems. Thinking on that problems would be better practice, at least it worked for me when I was less skilled.

Also don't you think getting points with hacks depends on luck?

spamming "0" to 10 coder that make such trivial mistake isn't called as debugging.

Also, how do you feel when you solved D in the last 20 minute with all complicated code but there are 30 users that don't even attempt to read problem D and get higher score than yourself caused they spammed "0" 10 times.

http://codeforces.com/blog/entry/59431?#comment-430573

i thought disabling hacks won't be a solution. in my opinion, limiting hack attempt or covering obvious test is way better.

there are some coder that seriously debugging other ppl code. but what i saw from this contest, most of the people just spamming 0 and click "hack" to get a free 1000 point because no one have started hacking in their room.

Please don't tell me the intended complexity for D is

O(Q* 128 *log2(10^{5})) (128 = largest number of divisors of numbers from 1 to 10^5).you are right for the complexity

Why my solution 38219517 was

Runtime error on test 29for A?Can you check them please?

`return !puts("0");`

Your solution returns exit code 1 on n=0.Don't know why downvotes for my previous comment, but

`puts`

returns a non-negative value (on success). In your case puts returns 0 and your code makes`return !0`

, i.e.`return 1`

. Any non-zero exit code from the main process of a solution is treated as a runtime error.If you fold the pizza it takes less cuts

Do you have any test?

n=7. Better answer = 3 if stacking/folding is allowed.

if folding allowed then best answer for any n should be 1

For C, can an input have n = 1 ? If n == 1 then x and y can not be distinct. But the range for n starts from 1 :P

I asked about it and the answer was no.

Came across one strange detail while viewing results for my room. The problem is said to be locked one second after it was hacked: https://pasteboard.co/HlaAgFu.png. We can't lock the problem if it doesn't have "pretests passed" status when we click "Lock", can we?

I hope he is able to resubmit after that hack and not hack others xD

Brute AC on D: 38234986.

you can use sigma(n/k)*q to solve D,so interesting

When I read the problems, I misread a part of problem D's statement. I understood that and not . How to solve that version of the problem?

PS:I have a solution, which is a bit complicated (not too complicated, but still) so any solution you can think of will be appreciated.Jonny, they are in the trees!!!

What is test 27 in C?

How to solve this generalization of the problem C:

Given an undirected graph with n nodes and m edges. How many are (u, v) pairs such that there exists a shortest path from u to v that it doesn't visit y if it visited x before? x and y are given.

http://codeforces.com/contest/979/submission/38243030

AC on D with O(n^2) and simple cutting..

http://codeforces.com/contest/979/submission/38236267 Не думал решение — такое простое!!!!!

Wow! Problem B was a devastation! So many people (me included!) got it wrong on system tests!

Can someone point out why my solution to C fails? Link

ll(1000000*1000000) isn't 1e12. type conversion occurs after overflow.

(ll)(n*n) is wrong

Nice problems, Thanks!

Can anyone tell me why LINK is wrong for C?

int ans=n*(n-1); overflow :(

I have defined int as long long int

oh i see..

Please sir can u tell whats wrong?

Leave it i understood my mistake

Problem C TLE. Is this 38236023 not O(n)? Poor python coder!

This solution for problem C yields

MLE-> LINKPlease help.

Because of passing vectors and arrays to recursive functions.

So, you should declare those structures as global structures, to be able to use them without passing them to the functions

I have just looked at your newest submission.

SpoilerYou don't need to pass "visited" to the function, it's enough to keep this array globaly declared.

And for the vector "path", you can do the following:

Each node you need to push it in the vector, push it. Then if this node don't lead to the destination, you just need to pop it at the end of the "dfs" function.

Thanks for keeping a constant check.

I would never have thought of these optimizations.

Welcome to HackForces! I think letting the round rated for everyone with rating below 2100 is a wrong decision.

If they don't hack you then you are wrong anyway bruh.

I just think "DIV2 only" round is not suitable for purple players.

And fewer people will take DIV1 round.

Can someone explain what main test 79 in problem B was. Since the test case is too big, any alternate small test case with same logic?

I've tried the case

3 aaaa aaab bbbb

=> Draw

from an earlier reply which works like aaaa -> aaab -> aaac -> aaaa instead of a->b->a->b

Got the error ! My answer to this case is Shiro ! Thanks a lot.

Why dose this solution (which is O(n^2)) get passed..

http://codeforces.com/problemset/submission/979/38236267

This generator can hack it..

I would like to point out the test cases of D is too weak. It seems to me most of the cases are random cases and does not target for a specific range of values.

My solution is to use trie for ki <= 400 queries (build a trie for each ki), otherwise, use O(n*si/ki) brute force. 38238355

I tried to mess around the constant 400 to see if a faster runtime will be achieved. And I accidentally found that using a single trie to handle queries of ki = 1 and brute force all other ki >= 2 queries can pass all tests. 38260678 I believe brute force solution for ki = 2 should result in TLE like ki = 1. Consider the brute force part alone, ki = 1 should run about half speed when ki = 2. However, my solution pass with 249ms which is unexpectedly low.

Also, it is reported that some O(n^2) brute force solutions with cutting can easily get accepted. See:

I hope the problem authors can investigate this issue and make stronger cases for future rounds. Nevertheless, I enjoyed solving this problem. :)

Note: My pure brute force solution TLE on 14 38260748

Sorry for the weak test cases of problem D. We did not think much about brute force solutions with optimization so the test cases were not tough enough. We will absolutely make progress next time. Thanks for pointing it out.

Why am I getting TLE for O(n) solution in Java ? (problem C) http://codeforces.com/contest/979/submission/38266793

`get(int)`

method of`LinkedList`

is . You should use`ArrayList`

or similar instead.Yeah! :D I almost forgot this. I can use ArrayList instead.. Thanks alot.

s