(っ▀¯▀)つ Heeey Codeforces (っ▀¯▀)つ
I and pavlekn are glad to invite everyone to participate in Codeforces Round 885 (Div. 2). The round will take place on Jul/16/2023 17:35 (Moscow time).
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! Vika sweet 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 Vika
that 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 Vika sees the comments
Giving 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 :
Kanroji-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 long for no reasons , just keep it simple like atcoder ,we don't have time to read the entire story
so 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)%2there 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 functionf(n) = g(n) * (k - n).g(n)increases by a constant amount20every timenincreases by four, past a certain constantc.[c, k]across all numbers such that they are≡ r (mod 4)for eachr ∈ [0, 4), then we know thatf(4n+r) = (20n + b) * (-4n + (k-r)), because of what was said above.n, so the result is a quadratic inn. Also, the leading coefficient of the quadratic is negative, so it must only have one maximum since it has an upside-down U shape.gis 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 :)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) = 4andg'(n) = 4f''(n) = 4 * (k - n) - 8k > 2andn = (k - c)wherec > 2.f''(n) = 4 * (k - (k - c)) - 8f''(n) = 4c - 8c > 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,
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.
We 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.
I am getting wrong answer on test 7 214092425
Shit problem statements round
The author for 6 problems could not ask Vika to marry. Why was this contest needed at all? :)
orz!
This is a troll round, the contest was intentionally bad as Vika is probably the girl that the author hates.
BRUH !
M should've been made much bigger in Problem E (bigger than $$$O(Q \log x)$$$) — it looks like the authors weren't aware of the edge case when M is too small and the power of an odd prime in the factorization reaches M (ie you can't simply multiply the answer by (power + 1) * inv(power)).
I think I am getting WA because of this. How to handle this case? My Submission
nvm, Done using counting the multipliers which have mod M = 0
can problem B be done with binary search?
yes
Can you reduce your nonsense when setting questions?
they should have added atleast one picture in problem A.(T_T)
Imagine being forced to do math :sob:
Anyone notice D is so fucking tedious and can be done by solving an inequality to solve for number of cycle for each digit the bonus could ended up at ?
Someone can just use chatgpt to solve for generic inequality for D lmao
how is it tedious? What was your inequality?
generating all digit beginning from 0 to 9. There is a cycle among all of them. Each cycle adds to the bonus a value of 20. You can verify this by generating and print. The only exception is 0.
Now starting from the original X, repeat this until the unit digit of X' has been seen before
assuming the current digit is the terminal digit, And let's call left is the number of moves left. Then we have if we stop here then discount is X * left. Otherwise we got (X + 20 * c) * (left — c) >= X * left. c is the number of cycles we will repeat * length of cycle. -> X * (left — c) + 20*c *(left-c) > X*left
Then solve for c.
It’s not so tedious and can be solved by anyone who has learned algebra. It doesn’t require usage of chatgpt to figure out
is this the correct equation because you are multiplying 20 with number of elements instead of number of cycles
where
c =number of cycles, L =lenght of cycle (here 4)
SimpForces
I'm so disappointed with this trash round.
Authors forgot to prepare A problem
Hello DifficultForces!
I used another account to participate in this contest. I solved 3 problems in total, and got a performance of 1830. One of my friends also solved 3 problems with less penalty, and his performance was evaluated as 2026. Only 60 persons passed A after the first 4 minutes, are you serious?
And F is wonderfully easier than E, what's your explanation for this?
In summary, I think this is a div1.5 round, not a normal div2 round. It's even worse than any of the cn rounds held before.
And some facts about why I performed not so well: I've been away from OI for 3 years and now i'm trying to recuperate.
Why did you use another account? It's not gonna be rated for you anyway, you're over 2100.
Because I just want to know how many things I still remember after 3 years, and use another account to start from 0 is the best choice.
No, using your own account is the best choice because it doesn't get you banned :)
Because of guys like you only our rating not increasing
is this test case valid
1 13 11 1 2 3 4 5 6 1 7 8 9 10 11 1
for question B
No. 12 is missing in between.
you feel that the problem is not difficult enough and decide to add confusing sentences -_-
After Passing this Contest I wish you to break up with her
Why this contest sounds like an atcoder contest
Overall, the contest wasn't good and ig problems were pretty tough. Toughest A I have seen.
Raise your hand if you also tried to solve B problem using Binary Search ┐( ˘_˘)┌
Could someone please help me out with what i am doing wrong in C Link
strings 296 — 298
As I think this is the wrong way, at least you need to calculate the number of operations here. It is also necessary to take care about how it changes (and will it change?)
Figured it out, when i was checking if steps%3 are equal i didnt consider the fact that the pair to the left and right of the case a[i]=0 and b[i]=0 can be unequal,using a set solved it
C problem is very strange
It's based upon the gcd algorithm i believe
Horrible contest.
contest was awful.
I got +73 points in this contest and my level has reached the Master level for the first time. that's cool
Maybe the contest is not good enough, but don't feel sad, and sincerely hope that you and your crush can fall in love forever.
Love and coding can't go hand in hand. Hence proved by today's contest. Love was so cruel. Took more than 1hr to solve just A. Love is war.
Question A and C was very awful
B Is fine. A Is bad
Story Behind DIV2A:
Once upon a time, our protagonist Vika found herself in a bustling mall, having a grand ol' time with her friends. But lo and behold, who did she spot but the infamous diskoteka tailing her! Fearing his presence, Vika hatched a plan to escape the clutches of this relentless pursuer.
However, much to her amusement, diskoteka misinterpreted her actions. The dim-witted diskoteka thought Vika was trying to ditch her friends and decided to be the self-proclaimed hero by aiding her in her "escape." And so, he hatched a devious scheme — he concocted a DIV2A problem that was devilishly tricky yet hilariously described.
In this DIV2A problem, diskoteka portrayed a perplexing puzzle with his comically bad statement-writing skills. It was a conundrum so confusing that even the most skilled programmers would scratch their heads in bewilderment.
With a smile on her face, Vika couldn't help but chuckle at the absurdity of it all. Little did diskoteka know, his attempt at being helpful had turned into a laughter-inducing escapade.
And so, with the mall shenanigans and the DIV2A hilarity, Vika and her friends continued their joyous hangout while diskoteka remained blissfully unaware of his unwitting comedic performance. Ah, the adventures that unfold in the most unexpected ways!
how many contests have you authored? zero right? don't blame him
when you realize the contest he authored was actually better
i don't think that is on cf.. did i read that wrong?
So one has not authored a contest if it's not on cf? Maybe you read yourselves wrong?
in the A , shouldn't the question be like "can any of her friends catch her?" instead of "if Vika can run away from her friends forever?" because Vika can aways run from her friends forever if they go around in circles(even if they are initially standing in boxes of the same color)????
Кому понравился этот дивизион?
Мне
Ну у тебя хорошие результаты
you ain't getting vika thats for sure
Mathforces?
I think C is not so easy and D is not so hard. If C = D = 1750 or 2000, the contest were much better.
Did not know love was equivalent to maths.
People have already pointed out many of the same issues over and over again, so I would like to give the round some compliments :)
Honestly, a majority of the issues people had with the round seem like they would be fixed with just more testers, rather than the problem quality being terrible (like the lengthy statements, errors in test cases, etc).
Personally, I found all the problems enjoyable; in particular, I liked C and F a lot :). To the authors, thank you for the contest! And please, continue problemsetting! I have enjoyed the problems from all of your recent rounds.
problem C is similar to https://community.topcoder.com/stat?c=problem_statement&pm=8178
This is the bad contest, not lovely contest
What? You all have a girlfriend?
damn i confirm that was a very $$$lovely$$$ round (jk it's suck)
Vika is a mathematician :)
Hello, diskoteka, although I dropped points in this contests, but I saw that you really love Vika, the story are all about her lives and I can see the depth of your feelings between the lines, and here's wishing you and Vika forever!
First problem is very interesting and unusual, thanks!
Stop simping
I feel for Vika, listening to boring meaningless fashion talks must be really painful. I wish her to find better friends, with whom she could enjoy fun and exciting conversations about strings, arrays, stacks and graphs, so that she doesn't need to hide from them anymore.
https://codeforces.com/contests/457547 plz try these problems for interview preparation
Hateforces (:
.
I never knew the meaning of the word
penultimate. After this contest, I learnt the meaning of this word. Thanks.2099->2204^_^finally
congrats :)
can someone tell me who is vika
C : Nie prblm
is it a couple contest
hey i got a warning mail from codeforces that "Your solution 214094696 for the problem 1848C significantly coincides with wont_give_srsly/214085235",i used the variable names as common so it might be a coincidence and i used ideone compiler so i dont know if due to that this happed. I did not share my code to anyone. This is second time i got a warning without any copying or cheating. I dont know how this user got same answer as me. I belive in fair play. Please look into it.