**(っ▀¯▀)つ Heeey Codeforces (っ▀¯▀)つ**

I and pavlekn are glad to invite everyone to participate in Codeforces Round 885 (Div. 2). The round will take place on 16.07.2023 17:35 (Московское время).

This round is dedicated to an amazingly beautiful girl **Vika** that I love very much. Every problem will be about her and related to her life.

The round will be rated for participants with rating lower than 2100. We will be glad to see the participants with a higher rating to take part in our round unofficially as well!

You will be given **6** problems to solve in **2** hours.

We would like to thank everyone that makes this round possible:

Artyom123 for coordinating the round

MikeMirzayanov for great Polygon and Codeforces platforms

teraqqq, Be_dos, mibig, FairyWinx, princebelkovetz for red testing

Dominater069, mbolgov, I.Gleb, induk_v_tsiane, Alexdat2000, maomao90, irkstepanov, fishy15 for yellow testing

maksimb2008 for grey testing

Scoring distribution: 500 — 1000 — 1500 — 2000 — 2250 — 2750.

We wish you all good luck and a high rating!

**UPD: Editorial published**

Hoping for a lovely contest.

Hoping that you find love too :)

Hoping you ask out your crush too :)

Hoping you guys find Peace ;)

Hoping You find piece . One Piece

Definitely! :) Well I would love to eat meat first.

SING MINA MINA PLZ!

Minami no shimawaaa atakai ♪ Paina-puru-puru, Atama boka boka, Aho baakaaaaaaa! ♪ ~~~~~~~~~~~~~~~~~~

Ni ban!

Kita no shima wa samuiii ♪ Hyakkoi-koi-koi, Atama buru buru, Aho baakaaaaaaa! ♪ ~~~~~~~~~~~~~~~~~~

HOTS: Find best time to propose your crush.oh look! the guy who got caught copying few contests back.

who ?

Love round

CM THIS CONTEST.

Who Knows.

all knows, you will cross 1000 problem

didn't age well :(

Nice!

LoveForces

So you are saying there is hope for me :) ? Do I need to reach purple first :) ?

Hope the problems are lovely as well :)

very beautiful hearts drawn by yourself?

<3 Lovely <3

Rooting for your lovee! :)

This guy really love his girlfriend.

This guy is really original. No one thought about dedicating their girlfriends a codeforces round :,)

I hope they don't have a fight.

Goals

Can anyone please answer why suddenly round-882(div2),round-884(div1+div2),round883(div2) became unrated?I did really well at those rounds.IS it a temporary bug or anything else?

most probably temporary, ratings are often rolled back, after plagrised codes are removed.

So, will our ratings stay like this, or are they going to be changed back? I participated in the previous Div.3 round, and my rating was 789, but now it is 614.

Yes. Rating will be recalculated and changed back. and it is generally more than previously calculated rating.( for you it will be more than 789 after recalculation, if your code is not plagiarized).

Thanks

Congrats for the increase in the ratings...

Thanks a lot brother.

Hello everybody!

I would like to become a student in this competition (green). And I hope that this competition will be interesting.

Good luck to everyone!

Best, Jelal

Hi, Jelal. Your comment has been very informative and I sure wish that you post more of these amazing messages on all codeforces announcements and I cant imagine the world without them.

Thanks!

Thank you diskoteka and others for an interesting competition!

nice :3

If I reach purple this contest, will I also get gf?

yes,you will get.

keep dreaming buddy

don't worry, one day I will get MA

oppnithv

Best of Luck everyone!

I hope every problem doesnt remind me how single I am

Hoping that you find love

Where purple and green testing?

Waiting for the lovely round.

'Relationship Goals' Round

Codeforces is the last place I thought I'd see PDA in.

a man of culture I see

if you think so, you can leave the codeforces society!

Best, Jelal

dafuq?

:)

:)

Even people downvoting on this comment too

what do i say now :)

Maybe just don't say anything :D

Let's hope his gf is a beginner then

Aww!

Vikasweet name.I won't participate because of cringy subject

who asked

It is a comment not an answer :)

who asked

ur mo-m

what topics could be expected for A,B and C. anyone??

binary lifting

bruh, your username :]

it's so cute

OK i upvoted the blog.

<3

UwU

no wonder it took that long to annaunce

if you have a social life you must not be a real cp-er

there is not any statement in the announcement, which implies that author had any social interactions with

Vikathat makes it weirder...

Finally, a round that doesn't clash with my schedule! Going for purple, good luck everyone! :)

I did it!!!

congrats

The announcement is so cute (face_holding_back_tears)

Still a better love story than Alice and Bob

I take that back

think the problems will be good (based on the last div3 rounds they writy)

sorry, wrong assumption :>.

Best way to celebrate Love and others Loneliness

Feels inferior to Genshin Impact ：D

可以

1<<Love Round

Hope love rating change

6

Meanwhile single people like me reading this blog ^_^

Remember guys heartbreak is the key to unlocking codeforces mastery

This announcement is accompanied by a beautiful picture.

I think today his girlfriend very happy

nurali ne tupi

.

Hope to reach expert this contest.

Best of luck everyone, I hope everyone attempts this one with Love..

Beautiful!

Contests are quite rare these days!

This relationship got 6 problems and we have 2 hours to solve them. Lesssgo.

will be a lot more problems if

Vikasees the commentsGiving contest to increase rating NA Giving contest to know their love story Yes

I want a marriage proposal in one question

A codeforces master with a GF, what do I do to gain a glimpse at this power?

a newcomer like me can solve one problem? what do you guys expect.(hiding imoji)

Normal People express love through Roses and Chocolates. Legends prepare a whole Contest...

I'm curious how long I need to train to get to green.

Score distribution looks scary

Yeah looks like i was right.

LoveForces...hoping to reach blue..

Is the watermelon in Artyom123 profile cheering up!

I also love ... love competitive programming. It is the only thing that understood me like a human being. #sigmagrindset

I think this will be a nice contest! Love codeforces

I can't wait to enjoy the problems.

Codeforces probably the only place where i may find love ;(

I suggest you to have a grey bo'oh'o'wa'er next to you during the contest

Setter be like :Tu Aake Dekh LeHo Maine Contest Kitne SaareTeri Yaadon Mein Banaye SohniyeSohniyeKanroji-san is that you?

Contest about love?

I hope that no issue would ever make me realize how alone I am.

copied comment

NOW?

+ve delta

Is there a hacking session in this round?

No pink testing??

Hope we will still love the contest after rating changes

This comment aged well

Hoping for a lovely contest!

Hope we will still love the contest after rating changes lol

"Every problem will be about her and related to her life" every relationship ever ;-;

The round is cool, recommend to everyone!

Can't wait! :D

Wedding when?

Expecting a breakup party instead, after seeing the votes on the announcement!

this will be the second participation on cf

Plz vika help him to create problem language more understandable.

What went wrong at F?

You should have proofread the statements before the contest. E and F contain silly contradictions and unclear sentences and both were edited after wasting some time trying to unravel them.

Couldnt Participate SED

This contest is as unattractive as the bridge mentioned in problem B. Worst problem statements ever.

I really hate Vika now

Problem statements are very difficult to understand.

For me hardest Div 2 problem A ever.

It's me or I have seen F statement somewhere before?

in problem div 2B , my code giving write output in my machine and wrong answer on codeforces !! Very frustrating experience

Vika is too difficult to get vro

6

maybe problemsetter should have spent less time obsessing over vika and more time making correct tests

Someone get Vika a translator

one of the worst things about codeforces's problems which is

problem statement is too longfor no reasons , just keep it simple like atcoder ,we don't have time to read the entire storyso true , it's always too long to the point you can't even understand it

Vika is too hard to understand bru. I can now understand your pain :(

Worst contest ever.

I agree with you.

Actually, Dytechlab is.

It'll be better to make this contest unrated.

Problem Statements are quite difficult for me to understand.

(love)storyforces

Super math round.

How to solve F in 5 min?

I have seen something similar to it tho i tried to solve it but i got TLE in pretest 20, it's approach is kinda easy tho

Definitely not a lovely contest...

How to solve A?

Even if once the distance(|x1-x2|+|y2-y1|) is even then answer is no as somehow they will diogonally orient). else answer is YES.

distance as in distance between vikas's corrdinates and any of the friends coordinrates

think about a chessboard: if Vika is in a black square, then she can only be reached by someone on a black square and vice versa for white. Also if there's someone on her same color they can always reach her. Colors are just the parity

`(i+j)%2`

there must be atleast two other person otherwise if there's one girl on black and vikka is also on black then she will never got caught

If you think about how to chase her it's easy to drive Vika into a corner (this sounds very bad lmao).

Like near the wall

otherwise just going towards her should do the trick

thx for explaining. However as soon as I see this div2a I skipped the contest. Its too hard to be in this position.

Have you seen or solved a similar problem/idea before ? If yes, do you remember where or from when ? Maybe when you used to do math competitions or something ?

probably yes, but i don't remember any examples. A simple observation is "if a and b are on cells of different colors they'll never meet". From this observation you can think about when Vika can escape from X if they're on the same color. And after some thinking you can understand that Vika cannot escape when there's somebody on the same color

is it hard for me or people solving F in 3 mins lol

How to solve C?, I guess using number theory... multiples like stuff? but couldn't get it!

Observe pattern. Then use recursion to optimize.

Problem A was tricky, Little harder than B.

Little? B is straightforward. Its just obvious what you have to do in B. Instead I think you solve A only if you have seen something very similar before.

I don't like probllem E. It is very OEIS-able. Also can anyone explain why we didn't have a fixed MOD in this problem. The MOD being 100 made the implementation tougher.

Getting to the conclusion that the answer is the number of odd divisors of X is not that trivial. I agree on the MOD part.

I think Vika is his ex so now he want everybody to hate her

How to solve D? Do I need to use ternary search?

What is the approach to D?

I understand that we can ternary search for the solution on f(x), where x is in [0, k] and an integer, and represents the number of times we will increase our number first, and then spend the rest of (k-x) moves on redeeming this number.

It seems to produce correct results for the first 4 sample testcases, but fails on the 2 large ones by a marginally small amount (~1e9 off the answer of ~1e18).

I made it accepted by using ternary search first, and then I padded the borders L and R by some 1000, so that it became L-1000, R+1000, somehow it got ac. But, I fear it can fst though..

I thought to do padding but didn't try. :(

Does anyone has explanation why padding is working?

`g(n) = The discount after adding the last digit to itself n times.`

We want to maximise the function`f(n) = g(n) * (k - n)`

.`g(n)`

increases by a constant amount`20`

every time`n`

increases by four, past a certain constant`c`

.`[c, k]`

across all numbers such that they are`≡ r (mod 4)`

for each`r ∈ [0, 4)`

, then we know that`f(4n+r) = (20n + b) * (-4n + (k-r))`

, because of what was said above.`n`

, so the result is a quadratic in`n`

. Also, the leading coefficient of the quadratic is negative, so it must only have one maximum since it has an upside-down U shape.`g`

is increasing by is no longer constant, we can no longer guarantee that the shape of the graph is nice. Below is a short and informal proof if you're interested :)(Dis)proof by Counter-Example`f(n) = g(n) * (k - n)`

`f'(n) = g'(n) * (k - n) - g(n)`

[product rule of differentiation]`f''(n) = g''(n) * (k - n) - g'(n) - g'(n)`

[product rule of differentiation]`f''(n) = g''(n) * (k - n) - 2g'(n)`

`f''(n)`

must always be negative for ternary search to be possible.`g'(n)`

cycles from 2 -> 4 -> 8 -> 6.`g''(n)`

cycles from 2 -> 4 -> (-2) -> (-4)`g''(n) = 4`

and`g'(n) = 4`

`f''(n) = 4 * (k - n) - 8`

`k > 2`

and`n = (k - c)`

where`c > 2`

.`f''(n) = 4 * (k - (k - c)) - 8`

`f''(n) = 4c - 8`

`c > 2`

,`f''(n) > 0`

. Therefore ternary search is not possible; (dis)proof by counter-exampleThank you!

Should I quit CP? [](https://imgur.com/a/Vx3xutf)

without any doubt

Suggest banning the authors for at least a year until they recover from Vika

agreed

Quite new and interesting problems, I liked this round. Also, I think my D could fst, so can someone share their approach to D?

nice div1 contest

Not able to solve A. LOL

rip vika lover author's english

What was testcase7 of D

How to calculate the number of steps in C?

The process is similar to the Euclidean Algorithm for computing gcd.

How to solve C? I figured out that I need to compute the following value: "how many steps you need to do to make first element zero modulo 3", and calculate it for every $$$(a[i], b[i])$$$ pair. Is that a way to go or I'm missing smth? If that idea is ok, how to compute it fast enough?

That idea is good. To compute it quickly enough, note that if x<<y, then we can compress it down quickly by observing the fact that (x, y) -> (y, y-x) -> (y-x, x) -> (x, y-2x), noting that we can reduce y by 2x in 3 moves without changing anything. You can figure out how many times to compress it down by using math, noting the difference between y-x.

There is an edge case where it starts off as (0, 0), then this pair should not be considered at all as it will always be 0.

Thanks! That was insightful

UPD: got accepted yay!

We have a set of two numbers, {a[i], b[i]}, where each number can be greater than, less than, or equal to the other. If a[i] is less than b[i], we perform one move to transform the set into {b[i], b[i] — a[i]}. Otherwise, if a[i] is greater than or equal to b[i], we perform moves until the set becomes {b[i], a[i] % b[i]}.

For example, consider the set {11, 3}. It undergoes the following transformations: {11, 3} -> {3, 8} -> {8, 5} -> {5, 3} -> {3, 2} -> {2, 1} -> {1, 1} -> {1, 0} -> {0, 1}

Here, 3 (b[i]) remains in the set until the number 2 appears, which is 11 mod 3. At that point, the transformation proceeds when a[i] >= b[i] to get {b[i], a[i] % b[i]}.

We notice a pattern in the moves: a[i] — b[i] appears after the first move, a[i] — 2 * b[i] appears after the second move, a[i] — b[i] * 3 appears after the fourth move, a[i] — b[i] * 4 appears after the fifth move, and so on. These differences follow a sequence of +2, +1, +2, +1, and so on.

By utilizing this pattern, we can determine the number of operations it takes to transform {a[i], b[i]} into {b[i], a[i] % b[i]} efficiently, in constant time complexity (O(1)).

Here's code: 214083155

Problem F seems some sort of Binary search on each bit of a[i].

for j'th bit, we will find when the bit will turn zero for all a[i], 0 <= i <= n-1 .

How did rainboy solved in just 6 minutes !!!!!

submission in just 6 minutes !!!

Any one share code for problem c?

Statement of problem C was wrong + testcase for problem E was wrong. I spent 15 minutes just to figure out what was problem C asking. I think it's fair enough to make contest unrated.

yeah wtf. Problem statement for C and examples are contradictory af.

The statement says that the planks can't have different color after repaint at most once, but the example has the first and last planks of different colors then the rest. In total the girl walks over 3 different colors wtf?

You can end your search, you have found the dislike button for problem A ----->

The worst content I have seen.

Am I happy for solving F or frustrated for not solving A?

I solved C and couldn't do A :clown:

Edit: Turns out I exited the program before reading all my input. :clown: :clown: :clown: :clown:

tgp07 , you haven't yet solved A. So "Literally" you are wrong.

UPDATE : tgp seems to have updated the comment.

My bad lol. I forgot about that :clown:

you like odd indexes i guess

It is ironic how this red-green pattern you achieved is the key idea for solving A.

I didn't realize they can also catch Vika if the distance to one of the girls is 1 :) Spent last 20 mins on problem A

UPD: i meant distance 2

That's not true, the catch happens only after the friends move

Oh no, it's only required to check if parity of one girl is the same XDXD

I thought it's only possible to catch if 2 girls have the same parity, and in some other edge cases

For A, I spent whole 30 minutes... and then I played cat and mouse run-chase on 10*10 board. And, I found that if pairity of (x+y) % 2 matches with any of the friends co-ordinates, then she can always get caught.

This is not A level question honestly.

How to solve F ? any insights please ?

Can you find array after n operations quickly? If you could, then binary search would do it :)

(Actually, simple binary search is probably too slow, but i think it's easy to remove one log n from time complexity)

I could see some pattern like,

pattern spoilerPattern is:Look at the array after powers of 2 steps.

ohhh shiiiit, I was so close to solving it then... Does this mean answer will always be one of the power of 2 ?

If that is the case, then I think I can solve it.

answer doesn't have to be the power of 2, but you can quickly find the array after power of 2 steps in O(n) time, which means:

e.g. to find array after 12 operations

you can apply 8 operations

then apply 4 operations

got it, now makes more sense. thanks :) . I think I can solve it now.

There is an easier way to do it. To add the x-coordinate and y-coordinate together. If two people stay in one room, this sum should be equal. And every change will +1 or -1 to the sum. It will change odds to evens and evens to odds. So if Vika's sum is an odd number, then all the girls with an even sum will not be able to catch her. But when they are both even/odd, other girl could make Vika get to the wall by following her. Then when Vika is driven to the corner, those girls with even sums could 100% catch her.

i grinned from ear to ear when i saw your board, come on man,hahahahahaha

not even Master cant solve A, its so crazy

In A problem I coudnt understand what does "adjacent to the side room" mean?

could have been 700 higher position if i didnt forget to put a command inside the brackets.

in C everytime one element is smaller than half of the the other element, every 3 steps the other number get decreased 2 times from the smaller number right? we count how many steps each number needs and see if they meet. once the number in array a is zero it will be zero again after 3 steps so we can see if the numbers will be zero at the same time.

Don't like when there are only math problems (at least A,B,C and D)

The A question in this game is incredibly mind-blowing, it's a spectacle like never seen before.

bruh what's with F

What's wrong with it?

the amount of solves is quite high compared with average F, and it happens two times in div2 round in a row

What a lovely contest! I am so glad that i participated in this contest!! (i will be green again)

How to handle both a[i] and b[i] even case in C ??

Try to think about the trailing zeroes of a, that's why when a is odd you'll have 121212. The distance between 1 and 2 is 2 ^ x where x is the number of trailing zeroes of a.

C was a monster this time! I hoped that at least I will solve till C, but B kept me occupied most of the time.

love was cruel

Loveforces shouldn't be Cringeforces

Got to see new types of problems, not based on common datastructures or techniques. Contest was harder overall, never did I see so less accepted in each question of a div2 contest xD

I cannot solve A lol

(

I am new here and now I am scared of cf, quit!!!!

This is by far the best round I've ever participated!

By the way, why the answer in E does not equal to the number of odd divivsors?

With problem statements like this, Vika won't understand a thing.

can we solve B using the Binary search??

Yes.

All $$$x$$$, $$$0\leq{x}<ans$$$ are impossible.

All $$$x$$$, $$$ans\leq{x}\leq{n}$$$ have some $$$y$$$ such that $$$y\leq{x}$$$ and $$$y$$$ can be an answer.

It's not binary search, perhaps the problem description is just tricking you into using binary search

I think so, I used binary search too, and passed the system tests.

can you share the logic

I'm sorry, but I'm not a good English speaker, so It'll be hard to me to explain my logic. But at least I can share my code.

The main idea is — Can we cross the bridge by jumping maximum $$$i$$$ planks at once?

Ya I also tried off doing so But Get WA on test 2 :(

Yes, Here is my Binary search code for B. SOLUTION

I wish u to be a single

Problem F is well known in Latvia, a simplified version was used in 2017 for our team selection contest (https://lio.lv/arhivs/arhivs2/2017_4_d2_uzd.pdf problem "Aplis")

trash contest imo...hope Vika havent participated

When you are in a "try not to write retarded problem statements" competition, and your opponent is diskoteka

Well, I see my comment also doesn't make much sense. After effects of this contest ig.

Hi, I got the answer for problem C now (10 mins after contest ended). want to see if it is correct.

I am not able to see the option to test my solution (at summit code), where can I test it?

Wait until the system testing ends and then you can test your solution

Does problem A remind anyone of king opposition in chess? Wish I solved it during contest.

I literally picked up my chess board and played an entire end game with no pawns to study problem A

No hate to authors but I would like to provide feedback regarding the contest, as I found it to be poorly organized and frustrating to participate in.

Today's C was amazing!

can you explain the solution :"

any clue so that no TLE, problem F 1848F - Vika and Wiki

my submission 214069066

2^20 = 1048576. In this test just a long array where all elements will never become zero.

UPD: More precisely, it reaches all 0 for a large volume of operations

Can anyone help me figure out if my idea is wrong for A? My idea was that if at least one friend is on a cell with the same color as Vika, then Vika will eventually be caught. And the color of a cell is determined through a chess-board like coloring.

Here's my submission: 214092967

Edit: I'm going to kms now

Vika and her friends are in the same type of room by calculating the sum of the absolute differences in their coordinates. If this sum is even, it means Vika and her friend are in the same type of room. If the sum is odd, they are not in the same type of room.

For example, if Vika's coordinates are (2, 2) and her friend's coordinates are (1, 2), the sum of the absolute differences is 1 + 0 = 1, which is an odd number. This means Vika and her friend are not in the same type of room.

Based on this logic, if any of Vika's friends are in the same type of room as Vika, she cannot escape. If none of her friends are in the same type of room, she can escape.

The problem is that you are answering before you read all the data. If you will remove the return in the while loop at all — all should pass

You return early without reading the inputs when they start on the same square.

Good problems but hard.

A: If the parity of x+y is same as any x[i]+y[i], then Vika will be caught. Otherwise, Vika will not be caught.

B: For each color we record their positions. For a certain color t, we list all positions with this color, and add 0 to the front of the list and n+1 to the back, and calculate the distance of adjacent positions. For the largest distance D, we can add a position with color t between them to make D-> floor(D/2), ceil(D/2), and (the maximum distance — 1) will be the answer for this color. We can look for all colors and take the minimum answer.

C: If a[i]=b[i]=0, they will always be zero (and this pair can be ignored), Otherwise, they will go into some circulation like (k,k,0,k,k,0,...) with period of 3, so we can find t[i]%3 where t[i]=the number of operations to make (a[i], b[i]) into (0, k). We can find t[i]%3 recursively: For (k, k) return 2, for (k, 0) return 1, for (0, k) return 0, for (a, b) where a>=2*b solve for (a%(2*b), b) recursively (because (a, b) --> (b, a-b) --> (a-b, a-2*b) --> (a-2*b, b)), otherwise let (a, b) <-- (b, abs(a-b)), solve recursively and add 1. Thus we can solve in O(n*log(max(a, b))).

D: If s%10==0, then s will not change in the 2nd operation, so the answer is s*k. If s%10==5, then s will become s+5 after any positive number of 2nd operations, so the answer is max(s*k, (s+5)*(k-1)). Otherwise, s%10 will go into the (2 --> 4 --> 8 --> 6 --> 2) circulation, and each time of loop will make (s, k) <-- (s+20, k-4). So we can do (s, k) <-- (s+s%10, k-1) for 4 times, each time we look for the maximum value of f(t) = (s+20*t)*(k-4*t) where t>=0. (We don't need to consider the case for 4*t>k because f(t) will be negative) This value can be found using ternary search in O(log(k)), or in O(1) by setting t0=max(0, (5*k-s)/40) and check f(floor(t0)) and f(ceil(t0)).

E: The answer is the number of odd divisors of X, so we can solve the problem using prime sieve, and for each odd prime factor p, we make cnt[p]++ and ans=ans*(cnt[p]+1)/cnt[p]. But since modular number M can be small, sometimes cnt[p] will be the mutiple of M and can't be inversed. So we need to record the number of p such that cnt[p]%M==0 and process case for cnt[p]%M==M-1, cnt[p]%M==0 separately.

Explanation for the answerWe need to find the number of positive integer f where there exist some k<=f-1 such that g(f, k) = f+(f-1)+(f-2)+...+(f-k) = (2*f-k)*(k+1)/2 = x. In fact, since g(f, k) = g(f, 2*f-1-k), for each k<=f-1 we can find k2=2*f-1-k>=f such that g(f, k) = g(f, k2), so the answer is same as (number of pair of integers (f, k) such that g(f, k) = x)/2. Then let's take a look at g(f, k). In fact, g(f, k) = x is equivalent to f=(x+C(k+1, 2))/(k+1), where C(k+1, 2)=k*(k+1)/2, which means x%(k+1)=-C(k+1, 2)%(k+1). As we know when t is odd C(t, 2)%t = 0, when t is even C(t, 2)%t = t/2, g(f, k) = x is equivalent to (k+1 is odd and divides x) or (k+1 is even and x/((k+1)/2) is odd). So for each odd divisor d of x, we can find 2 good values of k: d-1 and 2*x/d-1. Therefore, the answer is (2 * number of odd divisors of x)/2 = (number of odd divisors of x).

F: We can solve for each bit of a[i] and take the maximum answer. Now assume a[i]<=1 and we can use bitset to store it. We can find that after 2^t operations a[i] will become a[i] xor a[i+2^t], so we can find the number of operations to make a[i]=0 by binary search, using shift operations of bitset. Thus we can solve the problem in O(n*log(n)^2*log(max(a[i]))/w). But this is hard to pass the time limit. But if we doing binary search like what we do for binary search on the fenwick tree or finding LCA by binary lifting, we can solve in O(n*log(n)*log(max(a[i]))/w).

I got F in $$$O(N \log N)$$$ time. We don't need to binary search, simply start at $$$M = N$$$ and check if $$$a[i]$$$ ^ $$$a[i + M]$$$ is 0 for all $$$i$$$, if so then the answer is at most $$$M$$$. Otherwise, set $$$a[i]$$$ to $$$a[i]$$$ ^ $$$a[i+M]$$$ for all $$$i$$$ and divide $$$M$$$ by $$$2$$$, and continue, adding $$$M$$$ to the final result.

Then, add $$$1$$$ to the final answer, unless the array started at all zeroes. Then, the answer is $$$0$$$.

IN problem D, why we are not considering the cases when we start and end at different positions in cycle. (like intially s%10=2 and at the end s%10 = 4 or 6 or 8)

These cases can be found by setting (s, k) <-- (s+s%10, k-1) for 4 times, and each time we found the answer assuming we will use 4*t additional operations.

Did the same thing while upsolving C but i couldnt really prove the fact that the solution won't TLE, is there any way to bound the number of cases when b[i]<=a[i]<2*b[i].

Also in D, there are a 1-4 steps usually before we go into the 2-4-8-6 loop, shouldn't we check those cases too, or will that case never be the answer.

D is not solvable using ternary search, you can check this comment

https://codeforces.com/blog/entry/118293?#comment-1048731

what an amazing contest! (i love pupil)

Solved 1 problem only. But it means I'll probably learn a lot from editorial which is good.

Problems A, B, C and D were all non-fun to solve. Problem statements were so unnecessary long. Problem D isn't even CP problem it's just math. Vika will never love you.

Totally agree. I believe that most people gave up on the contest when they saw the text of the problem A. Pls don't write rounds anytime again.

Bro is malding over someone else's relationship on a competitive programming forum of all places.

I could not wrap my head around A (gonna be cyan now lol). I also think C was a beautiful problem requiring many interesting insights even though I didn't solve it in contest.

+1 gonna be cyan as well)

Can't agree, that C was a good CP problem, D was much-much-much easier and CP-alike. I figured out the solution for D after reading statement for the 1st time, but after 1h 40m spent on A+C, so couldn't implement it in time...

I didn't get purple because I forgot to use doubles for D to calculate (k — s / 5) / 2. sad T-T

chill guys don't downvote, we just not good enough to solve the problems

Only 8k solve in A?? Keep in mind that 25k registered for the contest

did anyone else solve F with SOS-DP?

Bad Problem Statement and unbalanced round

I saw a variation of A when practising for the Facebook Hacker Cup once, and that's probably the only reason I solved it so quickly :)

worst contest

what's up with people hating on A? it's just parity check right? The parity for (x+y) changes everytime, and friends can always try to come near Vika so it all comes down to is there a cell that has the same parity from original position between Vika and at least one of the friend

Oh, then prove it. Always comes close by what sense?

the distance between Vika and a friend is always non increasing, and since the board is finite it must eventually decrease

No, it could just not increase without decreasing, aka stay equal, at least given only your two observations.

um ok. more specifically, if Vika wishes for the distance to never decrease, then she must move away from the friend on each move. this is because the friend will always move one square closer each turn. this limits Vika to the same subset of moves for all of her turns, so eventually she will not be able to make a move without decreasing the distance. note that except for a single exception on the first move, it is not possible for two opposite direction moves to both increase the total distance, so this is true.

imagine the board has only 2 people. Because the board is limited, one person can always chase toward the other on at least one of the dimension.

Like if A tries to runaway on X dimension, B can always follow A until A has to turn around or stop on that dimension, then B advances one more position toward A on X. Keep repeating that until they meet.

Let's check Vika's possible moves:

If she moves towards her friend, her friend will also move towards her and the (manhattan)distance between them decreases by 2.

If she moves away, her friend will do the same move and she will be closer to catching Vika because she can't run indefinitely, she will hit the walls then the corners(and then not be able to move away).

Note: Towards means that the area of the bounding box containing both Vika and her friend will decrease. Moving away means the area will increase.

It's not a bad problem, but it can be really frustrating if you don't have that intuition. It shouldn't be on a Div2A.

Vika better not read those comments or she'll start packing her bags!

For problem E, my submission works even when $$$M$$$ is not prime. We need to find the number of odd prime factors of $$$x$$$. So we can keep dividing $$$x$$$ by $$$2$$$ until $$$x$$$ becomes odd. Now we assume that $$$x$$$ is odd. Basically we not need to find $$$(y_1+1) \cdot (y_2+1) \cdot (y_3+1) \ldots (y_k+1)$$$ % $$$M$$$ where $$$x={p_1} ^ {y_1} \cdot {p_2} ^ {y_2} \cdot {p_3} ^ {y_3} \ldots \cdot {p_k}^{y_k}$$$, and $$$p_1, p_2, \ldots p_k$$$ are distinct prime factors of current $$$x$$$.

So we can have an array $$$A$$$ of length $$$MAX(MAX=10^6)$$$ such that $$$A_i = 1 + $$$ exponent of $$$i$$$ in the prime factorisation of $$$x$$$. Note that $$$A_i = 1$$$ if $$$i$$$ is not prime. After $$$i-$$$th update, we need to change the values of $$$A_{q_1}, A_{q_2}, \ldots A_{q_z}$$$ where $$$q_1, q_2, \ldots q_z$$$ are prime factors of $$$x_i$$$. After changing all the required values, we need to find the product of all elements. These operations can be performed easily with a segment tree.

If $$$x$$$ contains a prime factor larger than $$$MAX$$$, its exponent will never change. So, we can take care of that separately.

I need complete help or hints in Prb A..

+the length of road to go from all to vika position

you can find that the length of all roads from (x,y) to (a,b) is only odd or even

If the difference between Vika and her friend's position is even then they can catch her. By difference in position i mean [abs(a-c) + abs(c-d)]. Remember that all A problems have a trick only, and if you look at the example tests, you can see this pattern

When you planned to solve 5 and end up solving just 1: Pain,

codeforces please drop me to pupil. I want to give div 4

I bet you will get promoted to Expert again before the occurrence of next Div4 contest.

A > B

stop using google translate

Problem E is absolute DOG SHIT, imagine a problem-setter who can't come up with original ideas so he decided to adopt a Div2-C problem and then mess with the modulo. Next time, try to be less creative!

Mathforces!

More like ObservationalForces

How to solve D?

I could think of a ternary search solution, but seems like something is missing...

S mod 10 goes in cycles

Yes included that too, still WA on test 1. https://codeforces.com/contest/1848/submission/214095213

Let t be the number of second operations used. For sufficiently large values of t, the bonus is increased by ~5t. So you can approximate the value function f(t) := (s+5t)(k-t). Note that f(t)-f(t-1) = -5k+s+10t-5, so the maximum value is reached when t roughly equals (s-5k)/10. Then you can just search in the range [(s-5k)/10-100, (s-5k)/10 + 100] or some larger range if you want to be safe.