Bro had a breakup revenge

A,C,D and E are just math problems. Cf should do better.

Problem statements were too long.

guess getting stuck in problem A was a sign I should not appear for this round

look at As editorial :0

I agree with the general mood that A-C of the contest were too hard. D-F were okay, although in E $$$M$$$ should have been set larger than $$$O(Q \log x)$$$ to prevent the edge case where one of the prime powers reaches $$$M$$$.

I liked A and B, even though the latter was mostly implementation. C and D were too mathy and guessable though.

problem statement of A was pretty confusing for me.

There exists an $$$O(n)$$$ solution for problem C, which is better than the editorial's $$$O(n\log a_i)$$$:

Submission

This contest problem statements are too long like a reading comprehension.

I think C is more difficult than D

May be I'm too foolish , but what is the tutorial of C's meaning???

Personally I don't think problem A is too hard for its position. The idea is fairly common in game theory puzzles like https://www.youtube.com/watch?v=dh4nEuhZBgg and just requires a bit of good intuition.

diskoteka [user:pavlovn]

My thoughts on this round:

The problems themselves were fine.

I do think A was not suitable to be a div2A, but that’s because I think div2A’s should be “submitbait”. The problem itself was fine, and may have done better as div2B.

Perhaps D was too math-y than ideal, but that’s fine.

Perhaps E could’ve had $$$M \geq 10^8$$$ or have been fixed, but it wasn’t much extra (and it is not too hard to generalize to all $$$M$$$). It is bad that the sequence is on OEIS though, so ideally this problem shouldn’t have been used.

Also, don’t listen to the haters, and please keep setting contests. Over time you’ll get better, and this contest probably provided good feedback!

C was a beautiful problem!

Your tutorial for problem D should write (b+20x)(a-4x), not (b+20x)(a-x) in the 4th paragraph, as reflected in your code.

Easier for F is just doing binary lifting as soon as you know the power of 2 thing. It's basically the same solution but O(NlogN) and you don't have to think about reducing it to an array of size N/2.

For problem A, vika's friends can see her(vika) right? So they see her and try to modify their movement right? Can vika see her friends as well?

please explain me this(Problem A):

1 2 1

1 1

1 2

I think when vita goes to right , friend will catch him . Perhaps, i misunderstood something.

This is the WORSR contest i've ever seen. Can you just stop writing such long description of problems?? If you want to show your ability of writing, you don't need codeforces. And problems DEF are so easy to think, the difficulty is too low to be the div2 DEF, it can be used in div3. The quality of the problems are also too low I think. And the awful test cases of problem E, can you just check your test cases before the contest? To my surprise, this contest has not been unrated, but I don't want to see such contest like this anymore. YOU DO NOT NEED TO CREATE THE CONTEST IF YOU DO NOT HAVE THE ABILITY OR YOU DO NOT WANT TO DO IT WELL!!!

when problem A has the longest tutorial, you know you did something wrong.

wthforces

I don't get why so much hate for this round. A is better than normal, I liked problem C quite a bit, and rest of problems were fine. (yet another round with no datastructure tho ;-;)

Sorry ,but I feel A lengthy and language is very tricky

pavlekn, откуда взялось вот это равенство в разборе F? a[2^t][i]=a[2^(t−1)][i]⊕a[2^(t−1)][next(i,2^(t−1))]

In solution1 of problem C , it will be ai-4*bi in place of ai-4ai

can someone explain me the problem statement of B in easy way.. i have read it multiple times but i am not able to understand

thanks..

Problem A was way too unbalanced for its position and difficulty range. Its not a great idea for begineers

in task B, isnt it necessary to mention in the problem statement that k distinct colourst will definitely be present.

My solution for A :
So we need to check for every position (i,j) in n*m grid, if there is a position where both main person and anyone among the k people have the same distance to (i,j). So we iterate over every position and check whether the distance of main person is same as distance of any of k friends to that position. TC : O(n*m*k).
AC code : 214108505

After reading editorial for problem A, do you still feel like this is DIV-2 A problem ?

diskoteka

Only in Vika-land, problem would need this much logical thinking and proof for problem A solution.

Because of problems like A, people start to hate math in cf-contests. The problem would be great if it were at the math contest, but not at cf.

Personally, I loved this round! I only solved ABCD, but this round had better problems than most recent Div2s in my opinion. I don't understand why the announcement blog post was downvoted. Keep making rounds!

ive done other coding contests but this was my first cf contest and i solved 0 questions, so skill issue for me ig

In problem C, I have a different way of finding the $$$cnt_i\% 3$$$ mentioned in the editorial.

Similar to solution 2, we will build the sequence from the end. It will be of the following form:

Now try to build a tree of all possible values before $$$x$$$. You will notice values in a particular level are either of the type $$$odd * x / 2$$$ or $$$k * x$$$ where $$$k$$$ is a positive integer. You will also notice that $$$k * x$$$ has a period of $$$3$$$, same as the period of $$$0$$$.

So the problem reduces to finding which of the $$$a_i, b_i, c_i$$$ is of the type $$$k * x$$$.

Here's my submission.

diskoteka, in the editorial of C, while writing Solution 1: I believe where you wrote

(ai, bi, ai — bi, ai — 2 * bi, ai — 3 * bi, ai - 4 * ai)

(and should have written: ai - 4 * bi)

Thank you diskoteka for great math problems, better than previous div(1,2) speedforces

E and F are well known math problems.

E: 2016 AMC 12B P16

F: Trivial special case of 2023 USA TSTST P9

It has been pointed out to me that the setup for F is actually identical to USA TSTST 2023/9 with $$$p^e=2$$$, although I’m not sure how much knowing the solution to the TSTST problem helps with the codeforces and vice versa. At the very least, one of the solutions to the TSTST problem proves that you will never print $$$-1$$$ (see the first claim in post #5 by a familiar-looking user).

Edit: sniped by the person who pointed this out lol

Great round! Like these problems very much :3

We've found some alt ways to solve F, but they have higher time complexity.

A is too hard...

I think problem A is harder than problem B.

Different Approach For Problem C. Code

Then, if the cycle is "scroll" x times, the discount will be (b+20x)(a-x)

WHY NOT (b+20x)(a-4x)?

In C, I tried to find the number of operations to make ai zero manually in the hope of getting some pattern or some formula but all in vain. May be they should try not to give such mathematical things till C.

C is one of those problems which gives neither the pleasure when I solve them nor guilt when I could not.

Can someone break down C for me, I observed a few things during the contest.

Let a>b for all below expressions, if not we can just move to the next stage where b and |a-b| will fit the scenario(moving one parity ahead).

Every pair will eventually reach a loop of GCD(a,b), GCD(a,b), 0. So essentially we needed to check if every pair have the same parity (%3 values of the number of steps they reach 0). I also noted that we can go from a,b to a%b,b keeping the same parity, except for when (a/b ==1). And that is where it stopped for me.

I saw some people use a%2b to move a parity ahead, but where does that 2 come from?

Typo in d editorial:

$$$(b+20x)*(a-4x)$$$

I found a very interesting pattern for problem C. For every i, we count number of trailing zeroes in binary representation of A[i] and B[i], now if A[i] has more, then this pair can be made 'dull' in 3k steps, if B[i] has more, then 3k+1 steps, and if they both have equal trailing zeroes, then 3k+2 steps. And we just have to ignore A[i]=B[i]=0 case.

Can someone provide me with clear insights on Problem C? Or provide resources to learn the topic. It is clear to me that the only thing that matters is the modulo 3 of the first occurrence of zero for each position of the array. But I find the tutorial very confusing on how to proceed further (maybe I am missing some number theory / modular arithmetic prerequisites)?

Did everyone lose rating? Half of the people must have gained acc to algo

I didn't understand the solution explained for problem C. Can someone explain it clearly.

Who can explain the tasks C, D? I didn't understand the author's decision at all

The tutorial is clear.

WTF you haven't said that sum of Ks over all test cases is at most 200000 in B!

Is the kind of reasoning used in problem E familiar to high-rated coders? Looking at the tutorial, I don't see any way I could have solved the problem on my own, so I want to know if people who solved it are well-versed with such kinds of reasoning or if it came to them naturally.

Can someone please explain what does area to Vika mean? Is it something other that the number of blocks between Vika and one of her friends?

Simpler Solution for A:

1. Every move, the parity of R+C changes by 1 for both Vika and her friends. Therefore, a friend can catch up to Vika if and only if the sums of their coordinates have the same parity.

2. Because the friend moves after Vika, she can always decrease the distance between the two of them. By contrast, Vika can only increase distance by moving in the same direction as the gap between her and her friend (e.g. if Vika is three units to the right of her friend, she can only decrease horizontal distance by moving to the right). Because the map is finite, Vika will be forced to decrease the distance between her and her friend after a maximum of R+C moves, and so she will eventually be captured.

Problem E Observation: # of odd divisors = # of distinct initial f can also be proved in the following manner:

• Consider all the pairs of [l,r] such that $$${\sum_{i = l}^r i = x}$$$

• We are sure the the lengths len of all these segments have to distinct

• So we need to find what all valid lengths are there. We have the following formula

• Consider one of the case where len is even. The case when len is odd is similar to prove.
• let len = 2p and p>=1

where did the formula (b+20x)(a-x) in D come from?

I have created video editorial for problem A,B and C in english link. If you understand it, upvote.

Can anyone please give me a more intuitive idea of the induction of problem F? I mean how can we see it happen beside trying to prove the equation?

Maybe there is something wrong with problem A statement. What will happen when $$$n=1,m=1$$$?

In this case none of the girls can move to the neighbouring rooms, which violates your statement.

Finding $$$cnt_i\%3$$$ in problem C is not that hard I think.

$$$[a,b]$$$ will change like this $$$[odd,odd] \to [odd,even] \to [even,odd] \to [odd,odd] \to ... $$$

And $$$a$$$ can be $$$0$$$ in only $$$[even,odd]$$$.

(of course if both number is $$$0$$$ a is always $$$0$$$ and otherwise we can divide numbers by $$$gcd(a,b)$$$ so we can remove $$$[even,even]$$$ case)

Can anyone share there solution for D using ternary search. Mine is failing. My solution for D

In Problem D why are we only subtracting 1 from k after every iteration, shouldn't we take into account the fact that we are performing 4 * x number of operations and adjust k accordingly?

cf should do better

A can be done through brute force too , just go to each cell , if distance from vika's starting cell == distance from any of her friend's cell , then vika can't escape

great contest, do consider making more contests please. [user:diskoteka][user:pavlekn]

I spent quite a long time upsolving C in coming up with the formulas to accelerate the procedure when $$$a>b$$$... I have no knowledge of gcd algorithms... how can it make the problem easier?

Alternative solution to F using SOS DP:

Notice that the value of $$$a_0$$$ after $$$k$$$ operations is the xor of all $$$a_i$$$ such that $$$\binom{k}{i}$$$ is odd.

Lucas's theorem states that $$$\binom{p}{q}$$$ is odd if and only if $$$q$$$ is a submask of $$$p$$$. Thus, the value of $$$a_0$$$ after $$$k$$$ operations is the xor of all $$$a_i$$$ such that $$$i$$$ is a submask of $$$k$$$. This can be computed in $$$O(n \log n)$$$ using SOS DP. We know that after $$$n$$$ operations all $$$a_i$$$ become zero, so the answer is the first moment that $$$a_0$$$ becomes zero and stays zero.

Submission

F: Could the answer be -1? Why?

I'm wondering how is one suppossed to come up with a proof such as one presented in tutorial E (or even think of proving the idea that number of odd divisors affects the answer)? Is that even Div2E level? The ideas used in the proof such as considering the parity of $$$cnt$$$ seem so random to me. I'd be grateful if any math gods would explain to me how to think about such problems or if you would show me more intuitive proof than the one in tutorial.

In Problem B, can anyone tell, why we are returning ans — 1 as given in the solution

nvm