Hello Codeforces!
I am pleased to invite you all to participate in Codeforces Round 981 (Div. 3), which will start on Oct/24/2024 17:35 (Moscow time).
The format of the event will be like any Div. 3 rounds:
6-8 tasks;
ICPC rules with a penalty of 10 minutes for an incorrect submission;
12-hour phase of open hacks after the end of the round (hacks do not give additional points)
after the end of the open hacking phase, all solutions will be tested on the updated set of tests, and the ratings recalculated
by default, only "trusted" participants are shown in the results table.
I encourage participants with a rating of 1600+ not to create new accounts but to participate unofficially.
Only trusted participants of the third division will be included in the official standings table. This is a forced measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:
- take part in at least five rated rounds (and solve at least one problem in each of them),
- do not have a point of 1900 or higher in the rating.
Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600 (or you are a newcomer/unrated), then the round will be rated for you.
Also, it will be a round with unrated register. If you already registered as rated participant you can change registration type here.
I would like to thank
MikeMirzayanov for creating Codeforces and Polygon.
Vladosiya for beautiful coordination and helping in preparation.
Pa_sha, SashaT9 and Skillful_Wanderer for not only testing but also discussion of the problems.
Hyperbolic, Irmuun.Ch for red testing.
LMeyling, Sokol080808, Intellegent, 18o3, amoeba3, -1e11, Error_Yuan, Wandoka for yellow testing.
adepteXiao, yellow_13, macaquedev, Pa_sha, Vinayak286, chromate00 for blue testing.
darysani for cyan testing.
Parag_AP for green testing.
My friends cat Chefir who inspired one of the task statements
Good luck!
Upd: Editorial is out.
Auto comment: topic has been updated by FBI (previous revision, new revision, compare).
cat
finally a div 3 after a month, lets go!!!
duh, cant participate cause of the time (10:35 which is school time)
Don't go to school, CF is more important
carzy
Could you tell my teacher this?(*ﾉε｀*)
Codeforces > school
FBI!Open your mind!
I. WILL. REACH. PUPIL. AFTER. THIS. CONTEST ( else I'll quit cp touch grass and get a life )
xD
Bro Whats reason behind your dp ? .I somehow find it too funny
no such reason btw you know him?
Namo Kaul
Lets get to PUPIL
i failed
How to get +200 in this round?
AK the round
Just belive in yourself
What the heck?By FBI?
Ciallo～(∠・▽< )⌒☆
FBI Contest!
As a participant... oh wait? I cant be? rip I have class at the time
Ill be sure to virtual tho
hope to reach pupil after this
Congrats!
Thank you!!!
Finally a contest with usual time.
As a tester, I would like to say the Chefir is a very interesting cat.
and very naughty :)
for what div3 ? to make it unrated how previous div4? #mike_fix_cdf
oh how many downotes for facts, indian dogs)
As a tester, I would like to say that all the tasks are interesting, and Chefir in the photo is very cute.
dog
Hello! I was a bit late with testing the round, I have sent a message with the feedback, but I am worried that my feedback won't be seen, so I decided to also leave a message here
will be nomore div3s cuz of ai ?
Waga bakuretsu mahou wo kurau ga ii! EXPLOSION!
my max rating is 1190, hoping that i can achieve 1200+ after this contest
You will
That's really nice of you. Thanks
I think I can cross $$$1400$$$ before next Div. 4 round. Since, I opened the account, there's not a single Div. 4 Contest. However, attending straight into Div. 2 helped me to improve my skill quickly.
Anyway, What's the score distribution?
There are no score distributions for ICPC styled contests, where each problem is weighted equally (no individual score per problem). Div 3 and Div 4 contests are ICPC styled contests.
Ohh thanks
Can I go back to being a Pupil?
cat will help to increase rating
What a nice name--"FBI"...
My initials, lol
As a tester, I hope no one will use AI
Just a thought. Can't AI's just partner up with codeforces and not answer the questions during the contest?
I think it is not that easy. If it was, it would be already ig. But it would be fine
Knock Knock !!!
Who is here ? :)
Oh shit… guess I made humans go extinct :/ Time travel: Who is there? :)
Its an
FBI Contest
To qualify as a trusted participant of the third division, you must: do not have a point of 1900 or higher in the rating.
did you mean 1600?
Hi Xanlar <3
as a tester, this round has problems
My greatest dream has become a Div3 not at 17:35. I'm very busy at this time every day , All div3 at this time, why ?
Bro only sets Div 3!!!
LETS GET IT GANG!!!
eyuuuuuuuuuuuuuuuuuu
Can I pet the cat :)
As a tester, good luck have fun
cant wait to get Pupil rank!
Greetings Chefir!
Brown one! or same brand?
As a tester, I respect Chefir orz
Can you provide problems Rating Range?
I would love to see more photos of chefir
Is there a way I can submit during contest if I forgot to register before the contest started?
Thanks for problem B! In all seriousness how is it even possible to screw the problem statement that bad??
I will be personally reading all your problems when (if) you will be hosting a competition someday. Have a great day.
It seems like I was the only one that had trouble understanding the problem. But still I believe the statement before the change was bad and why you get offended(I know it is lot of effort to organize/make contest and I respect that)."It is known that at every point in the valley, the heights are less than 0","height of each spike","she can select a square area of mountains and increase the height of each mountain"...
You are not the only one, I just guessed what they want.
Why do you have to be pricky about it, bad is bad. You went from mountains to spikes in no time.
I was able to solve 3 problems for the first time in a CF contest :)
Same
Nice F,G. No clue where to even start.
problem C is just wow.
i have no word
authors can really surprise you every time with how bad they are at determining the level of the problem
You just had to solve it from the middle of the array, not from the start!
wdym
could you tell me why my logic isn't working for problem C 287809023
Although you are starting from the middle of the array, your approach is still wrong.
The correct approach is to start filling a new empty array
bof sizenfrom the middle using arraya. And calculate the disturbance in that arrayb.How to do C??
what i did. get all pairs. distribute numbers again greedily considering swapping a[i] with a[n-i+1] or leave them at their original positions.
why does this work
It’s based on a simple exchange argument proof. Basically, at each step you have 2 choices: swap a[i] and a[n-i+1] or not (dp works here too).
Assume a=[3,3,7,5,3,9,1,7,4], and we are considering swapping a[1] and a[7], in this case, swapping or not leads to the same optimal answer we can get for a[0…2] and a[n-2…n] but this answer is independent of the optimal answers we can get for a[3..n-3].
Therefore, we calculate the local optima we can get at each step hoping it leads to the global optima. Hope this helps ;)
ll i(1) , j(n-2) ;
while ( i < j) { if ( v[i]!=v[j] && (v[i-1]==v[i] || v[j+1]==v[j] )) {swap(v[i] , v[j]) ; } i++ ; j-- ; }If n is odd, ignore the middle element. Now take 2 middle elements,let their value be 'a' and 'b'. Let the element to the left of 'a' be 'c' and element to the right of 'b' be 'd'. Note that if a!=c and b!=d, this is best you can get(zero disturbances), so do not do anything, otherwise just swap positions of c and d, because this will not worsen the answer, the number of disturbances will either remain same or it will decrease, in this way move to the end points of the array. At last, you have the modified array with you, just count the number of indices where a[i] = a[i+1]
what i did, fix the first pair of numbers, and then greedily order the rest, and then fix the first pair of numbers in the opposite way, and then again greedily order the rest. and then just take whichever of these 2 is better
I did the following: swap $$$a_i$$$ and $$$a_{n - 1 - i}$$$ if either of these elements are same as their outer elements. By outer elements I mean the element just left of $$$i$$$ and just right of $$${n - 1 - i}$$$ respectively. The final array by iterating till the centre of the array is the optimal arrangement.
Proof: Consider an optimal arrangement. we will show that any optimal arrangement can be transformed to our preferred arrangement without worsening the answer at any part of the transformation. Starting from the outermost pairs of elements ($$$0$$$ and corresponding $$$n - 1$$$), let's say the first relative order of elements we encounter which is not arranged according to our preference is between $$$x - 1$$$ and $$$x$$$. Now if we swap all the elements from $$$x$$$ to $$$n - 1 - x$$$, they will preserve their relative order, and thus the disturbance for all the elements in the segment. In fact the only thing that changes is the relative order between indexes $$$x$$$ and $$$x - 1$$$ and the corresponding pair on the other side of the centre. So the overall answer will only change due to the change in this part, which we can easily show, will not worsen if we swap it. We can continue to find such out of order indexes and swap them to our preference and none of these flips will worsen the answer.
Thus, irrespective of the optimal arrangement, we can transform it into our exact arrangement, and the disturbance never got worse. Hence our arrangement algorithm in fact provides optimal arrangements itself.
what is the difference between optimal and preferred arrangement ?
By preferred I mean the arrangement that you propose to be solution, and the optimal is a hypothetical arrangement which has the optimal answer, but not necessarily same as your proposed arrangement. By the end of the argument the goal is show that the preferred solution is optimal itself. Note thatseveral different solutions nay all be optimal, you just need to show yours is one of them.
_ So the overall answer will only change due to the change in this part, which we can easily show, will not worsen if we swap it._
How can we show that ? I am not getting any idea around that.
Was F really that easy (~1500 submissions)? I've been staring at the question for the last 1.5 hours and can't think of anything.
ig there was pattern through which we had to only find first no divisible by k...but after % operation idk how to check if original no was divisible by k
F is oeisforces. Basically you need to find G(1, k). G(1, k) <= 2 * k. G(n, k) = G(1, k) * n.
How do you get G(1,k)?
G(1, k) <= 2 * k
Can just find it in O(k)
Okay but how do you know or observe G(1, k) <= 2*k (assuming you didn't already know it before)
I've generated first 10 G(1,k), put them into oeis and found https://oeis.org/A001177 In "formula" section here you can see it. But I don't know why it's like that.
Found the paper for 2*n upper bound https://jonkagstrom.com/articles/upper_bound_of_fibonacci_entry_points.pdf
Fibonacci mod k always has a cycle. You just find the cycle length and then answer is simply a multiplication of the cycle length times n modulo 1e9+7.
no wondering, F was ChatGPT solvable with single attempt
Born to make problems for div2. forced to make problems for div3.
Nice contest. Got to learn about fast doubling method in finding Fibonacci numbers in logn time complexity. Wonder if it could be used in F ? :/
Good job, guys. Very nice contest!
what's wrong in my F .
We just need to multiply Pisano period of k with n in mod ? Right .
I am Getting this 998488007 instead .
You will
There can be more than one Fibonacci number having $$$0$$$ mod $$$k$$$ in one Pisano cycle. Your answer will only work when there is exactly one $$$0$$$.
oh yes thanks
Even though I will be losing rating again, but great contest!!
Great contest, but sadly D is literally on leetcode
oh... :(
Implementation Forces
I solved F assuming that the period of "0" could be different, depending on the first term of the sequence ((0, 1, 1) is different of (0, 2, 2) for k = 4, for example), and this led tosome more unnecessary thinking and code, instead of just finding the first "0" and multiplying the answer by n. Now I see by bruteforcing all k's the period is always equal.
can u plz share how did u find first 0?
bruteforce. I tried for all k's and found the first 0 in less than 2*k operations.
maybe a dumb doubt but fibo no would have been %. How to check if its divisble by k?
You can do like this for all k
ig there's a method called Pisano Period wiki link
Sequence $$$(0, x, x, ...)$$$ is $$$(0, 1, 1, ...)$$$ multiplied by $$$x$$$, so period is the same ($$$gcd(x, k)$$$ is always $$$1$$$).
This is making more sense now, if $$$gcd(x, k) \neq 1$$$ the sequence wouldn't be periodic (would never be "1" in $$$(mod\ k)$$$ again).
You can also use $$$F_{s+t}= F_{s-1}F_t + F_sF_{t+1}$$$ to show that zeros are evenly spaced.
Didn't understand how we're able to conclude that $$$gcd(x,k)$$$ is always 1
Both $$$fib[n]$$$ and $$$fib[n + 1]$$$ are divisible by $$$d$$$, where $$$d = \mathbb{gcd}(x, k)$$$ and $$$n$$$ is position of first $$$0$$$. Using the Euclidean algorithm we can deduce $$$fib[n - 1] \mod d = 0 \implies fib[n - 2] \mod d = 0 \implies ... \implies 1 = fib[0] \mod d = 0$$$, so $$$d = 1$$$.
Am I the only one who swapped operations in G and ended up solving that for no reason xD
I wasted 30 mins doing the same and then realised I have been solving the wrong problem.
Result: Left the contest XD
What is meant by that?
what is the follow up for F, i understood it will have a modular cycle, upon some search and reduction i can deduce the : nth fibonacci number as
f(n) = (((1 1) (1 0)) ^ n - 1) * (1 0), but how to make progress with this. Any help will be appreciated.for all k, we can find the first "0" element by linear number of calculations. I bruteforced all k's from 2 to 100000 to find out the maximum number of operations, and that's always lower than 2*k (Didn't prove the general case). For some reason this period is always equal for all k <= 100000 too.
Here is proved by AC 287807845
What's the order of swapping in 3rd question or simply what was the logic behind this question, I tried a lot but didn't got the answer.
Great contest, mainly E, still figuring out how to optimise E..
When does the Editorial will publish?
The problem statements were so poorly worded and sample I/O was not explained. For example, in problem B, you talk about mountain and then suddenly ask at the end about spikes. Mountain is defined to have positive height, but a square of mountain can have lakes (that have negative height). Why even write a legend if you cannot be consistent about it in the very problem statement? sigh
I have the same thoughts, the spikes confused me a lot, and I wasted 15 minutes trying to understand it.
F was a sadistic problem
What the hell is problem C
For E. I got TLE on TC 5, how can I further optimize this?
Submission: Link
Given the constraints you can simply use a vector to do what you are doing with the unordered map.
For your reference : https://codeforces.net/contest/2033/submission/287790082
Hope it helps!!
Please add a note or explain at least one of the test cases. I am not asking for an explanation on every test case of the question, but as a beginner, some questions can be challenging for me to understand. I often look through the test cases and notes to get an idea about the question. Again, I’m not suggesting you add explanations for Problem A; I suggest starting with at least Problem B.
Any hints on C and D? My brain is deep-fried and cannot think clearly anymore
C : Think of a swap as penalty increase, no effect on penalty or penalty decrease. Penalty increases after a swap if the ai != ai+1 and we swapped in a penalty value. So we only swap when ai = ai+1 as it will either decrease penalty or will keep it same. I don't know how to explain better than this.
D : Prefix sum map int -> int. store the last index where the sum appears. Iterate from beginning and if you find some sum again update its last appearance and increment ans.
damn I miss the map part... I was completely stuck at D and have no mood for C. Actually thought the same idea but have no time (about C)
I can't solve C, can you explain or hint more?
NEED MORE DIV3s PLEASE CF-SAMA
Greedy Forces
rather guessforces
who else when $$$k=1$$$ printed $$$n$$$ instead of $$$n$$$ $$$mod$$$ $$$10^9 + 7$$$ ?
f is easy to find in google, d < c, excellent round, thanks fbi, now i prefer the KGB
G : Try to solve offline....... For a pair ( v , k ) , find node k distance up from v , now if I go up to a node x , ans of query can be level[v] + ( "distance of deepest leaf node from x found so far" — level[x] ) . we can create a array on the basis of inTime of nodes , and use it to find maximum in a range from l to r using a max segmentTree . l : inTime[u] : u nodes after k jumps up from v ( use binary lifting to make it fast ) r = inTime[v] .As soon as a node is done , update its value with — inf in segmentTree
Just want to know is it somewhat related to Heavy Light Decomposition.
Sorry for my weak English
Refer to code
why are you thinking about hld being gray?
i also want to know "Just want to know is it somewhat related to Heavy Light Decomposition?"
what is the solution to F?
Just find first index of fib for which $$$fib[ind]\%k = 0$$$ and then $$$ans = n*ind$$$. That's it
I see, thanks. So do the zeros always repeat after a set amount? And is there a proof for that?
yeah they always repeat like for 4 after every 6 it will repeat
Yes. After the first index where rem=0, the reminders tend to again follow the fib sequence from the beginning
It seems like some of them aren't the Fibonacci sequence exactly, but eventually it goes back to a Fibonacci sequence after a few zeros. Like this is how it is for $$$5$$$:
$$$1, 1, 2, 3, 0, 3, 3, 1, 4, 0, 4, 4, 3, 2, 0, 2, 2, 4, 1, 0, 1, 1, 2, 3, 0$$$
After $$$4$$$ sub-turns, it eventually went back to $$$1, 1, 2, 3, 0$$$ and just continues looping through the $$$4$$$ sub-turns.
Yeah, it's not exactly fib sequence, but multiple of fib sequence and the multiple is not a multiple of k so it doesn't actually affect the period of 0
After first 0, its $$$3*(1)\%5, 3*(1)\%5, 3*(2)\%5, 3*(3)\%5, ...$$$
The period of multiples of k will not exceed 6*k wikipedia
.
for E, if you also have to print the swaps, then it's similar to https://cses.fi/problemset/task/1698
C is incredibly hard as a 3C
C is greedy with a not so difficult exchange argument proof?
Its hard :(
orzbihany
Fidelity Bravery Integrity
greedyforces. guessforces. readforces.
pA: The problem statement is so long that I need a lot of time to read the statement. Also, no explain testcases makes me more confused. I can't understand who wins on problem A, and I need a lot of time to read the statement again and again. I also don't like the output of A, why not just output yes/no instead of the LONG name?
pB: "If aij<0, then THERE is a lake THERE". Why 2 THERE in the same santence? "With her magic, she can select a square area of mountains and increase the height of each mountain on the main diagonal of that area by exactly one." The sentence is too long, u should split the sentence by "," and ".".
pC, pD, pE, pF are all GREEDY. Why put so many greedy in a contest? To make people guess the ans again and again? pF is the most painful problem among them.
To do pF, we first need to guess that there is a cycle of the remainder of k. Then, guess the upper bound cycle length is bounded by a multiple of k. We just guess everything in pF, that's stupid. Also no need for a ll n in the input, which makes me lose my AC for k=1. Honestly, What do we learn from this problem? Guess? Take care for output of k=1 bcz n is too big?
I learn nothing from this contest. I just guess and guess all the ans from all the problems. Problem statements on pA and pB are fxxking long and really weird, which made me suffer. We DO need the contest to test our CP ability, instead of reading problem statements/guess the ans/avoid the unnecessary traps.
If you think greedy is guessing, then maybe you can try learning how to prove your greedy solutions ;)
no, proofs are too hard, i think he’s better off improving at guessing
thats true for increasing your rating, but he mentioned he learnt nothing from the contest, and trying to prove any greedy solution is of course an enlightening activity.
Yeah, try to prove the greedy of F. That may need a lot of papers. Nobody cares about the proof of greedy during the contest, and also nobody will prove the greedy after the contest. I am just telling the truth.
F is not even greedy lmao
Not greedy, sorry for the wrong word. I mean to guess everything in F. No proof can be provided during the contest, and that remainder property of Fib is not useful in CP.
Yea well I do agree that thinking about proofs is bad during contest. But thinking about it post-contest can actually help improve your intuition so that you can guess better next time. As such, no problem is useless you have seen it before :)
Generally agree your perspective on the extremely boring A, B, D and F with awful statements or ideas. But it seems that C can be solved by linear DP and E can be abstracted into a relatively interesting graph problem(about how to optimally cut the long loops). However despite the multiple solutions, this round is still too relied on key observation and guessing as you just said, and F is the most weird amongst all the unreasonable ones. It's just like a guessing game rather than a true algorithmic problem combined with number theory.
I read the problem A half way, saw the test cases and assumed (idk why i risked it) that its just odd/even and AC.
B was stupid too, I was baffled by the lengthy and confusing statement. C was also not clear in the first instance. went straight for D. really a guessforces.
even i guessed it but still wanted to verify it, there is often bias about these A,B problems.
I feel better after using DP on C instead of greedy. The problem has a single observation to pair the disturbance of i with the disturbance of n-i, instead of n-i+1 as one initially does. The problem also leaves behind one of the repeating pairs count in the description to allow this. You need this "creativity" to solve the problem, regardless of what everyone else says about "proving greedy" or whatever. Fundamentally, it's about math creativity. This means that for the front half of the elements we pair with the element in front and for the back half we pair with the element behind. In doing this the problem of [2,n-1] becomes a subproblem of [1,n]. Then DP follows.
Both DP and greedy have optimal substructure. If u find some optimal substructure, and say that "This problem is DP", then u are totally wrong. "creativity" is indeed greedy choice property.
Yes, I'm totally wrong. Please kill me now.
loved it I got the idea of F but couldn't implement it out as I didn't focused that we just can brute forced it out man but was a great contest for me
tag griefers be like
I was able to solve problem 2033F - Kosuke's Sloth by making an observation that numbers divisible by k occur at regular intervals in fib sequence (I don't know why)
https://r-knott.surrey.ac.uk/fibonacci/fibtable.html
Then you have to find first index i where fib[i]%k is 0 and another observation I made is that this index i is always less than or equal to 2*k. You simply multiply this index by n to get index of nth element divisible by k.
if you see the table in mentioned link, you will observe indexes —
divisible by 2 — 3,6,9....
divisible by 3 — 4,8,12....
divisible by 4 — 6,12,18.... (huh?)
divisible by 5 — 5,10,15.... (why?)
divisible by 6 — 12,24,36... (what?)
Is there a way we can find the first index using k itself?
there is a fact about fibonacci numbers which says that if n divides m => fib(n) divides fib(m), so using this you can see why that property is true
Thanks. I was not aware of this.
Brute force, since k <= 1e5
That's what I did but there must exist some formula that directly gives us the first index divisible by k using k only. That is, f(1)=1, f(2)=3, f(3)=4, f(4)=6, f(5)=5, f(6)=12 and so on.
I missed the constraint on k and was trying to calculate it based on $$$m=p_1^{e1}* p_2^{e2} * ... * p_n^{en}$$$ then $$$a(m) = lcm(a(p_1^{e1}), a(p_2^{e2}), ..., a(p_n^{en}))$$$ and $$$a(p^e) = p^{e-1}*a(p)$$$, found those on OEIS
B's Statement is too long for 3B
C is hard for 3C
D is somewhat classic
I think F was in hand , if we just had better set and statements
What is the idea of E?
You can visualize this as a directed graph where every node i is connected to node P[i]. The given conditions will be satisfied only when all cycles in this graph have a length of 1 (that is i = P[i]) or 2 (that is P[i] = j and P[j] = i).
Notice this is a directed graph.
What property does each connected component have?
Hint 2 Answer: It is easy to show that each connected component forms a loop.
Let's assume there exists a connected component that doesn't form a loop. Easy to see that there exists a (or at least 1) "root" (no other elements have a path directed to it). Since there exists
n - 1nodes that can be directed to, and there existsnpaths. By Pigeonhole Principle, there exists a node where 2 or more paths are directed to. But since this is a permutation (i.e. all values must occur one time), the result contradicts it. Therefore, all connected component forms a loop.Also, notice that the final condition indicates that all connected components have a cycle of 1 or 2. To minimize operations to achieve this, we perform swaps within each connected component. After playing around a bit (in fact I don't know how to prove this), you will find out that if a connected component has a cycle of
k, then the minimum operation required is $$$ \lfloor \frac{k - 1}{2}\rfloor$$$. The answer will just be the summation for all connected component.287844154
Is it just me, or did anyone else implement G , such that if you move from child to parent, your stamina doesn't decrease, but when you move from parent to child, your stamina decreases.
( basically, direction of travel was reversed :| ) .
but even after that how to solve it?
when we do it in reverse, I guess question becomes even more difficult than the question that is already asked.
The question that is asked, for that I guess DFS + Segment tree is enough.
The question that I was solving, we need to maintain monotonically increasing set of nodes, which always improve the answer.
Can you guide me to the solution? How do I start with this one?
Can we use dfs tree flattening? we can go upto k parents up, then we just want to figure out the farthest node from i within that subtree.
Is this approach useful? too complicated? any help would be appreciated.
Lets define few terms,
1) Level of 'node' is equal to distance of current node from node-1.
2) Maximum depth of the node — in the subtree of given 'node', what is the maximum length of any chain.
Now do 2 parse DFS .
First DFS
In the first DFS, you can keep track of level of node, and maxDepthOfTheNode ( You just need to keep track of two maximums ) .
Second DFS
When we travel from 'parent' to 'child' node, we have to find, what is the maximum length chain, that is starting from the 'parent' node, and doesn't pass through 'child' node ( basically passes through sibling of the current child we are exploring ). You need to insert this value in the segment tree. ( Point update in max-segment tree).
Then it is simple range query for last 'k' elements of the Segment Tree.
Hope this helps.
i thought that at first when i read it, but thats fairly trivial. edit: its not that trivial actually nvm
IMO, the implementation is little tricky when we do it reverse. The implementation is very straight-forward, if you have max-sementTree template.
The reverse of the question, was little edge-case involving.
yea i just started thinking about it, and i just realized its not actually trivial at all. i believe segment tree is needed for both of the versions, and sadly i have no idea how to implement it or use it so i can only wonder :(
I was unable to figure out, how the segment tree would help in reverse direction. Please elaborate idea. What values would you store in segment tree ?
It is solvable and i solved it during contest before realizing I alongside 100s of others made the same misreading
Solution : as in the other solution, we assume we have d_i a depth array calculated where d_i represents deepest node in subtree of i'th parent of v (which is not present in subteee of (i — 1)th parent of v)
Now, we want to find the maximum of expression
Find the last index $x$ where d_i >= k using Walk on segment tree. Then, either optimal index is $$$x$$$ or one of the indices $$$x + 1....$$$
Calculating value for $$$x$$$ is easy, and for $$$x + 1...$$$, you can note thar the function becomes $$$i + d_i$$$ because $$$d_i < k$$$, and the segment tree we are already using for this version of the problem suffices
exactly what I did bhai... But instead of using the segment tree, I had used monotonic set of nodes, which will always improve the answer. and then applied lower_bound search on those. couldn't think of SegTree based solution.
While running sample test cases, I realised, I am screwed. Although it was good problem to solve.
can anybody tell why the code for G problem of this contest is giving tle its complexity is (n+q)logn https://codeforces.net/contest/2033/submission/287818878
I am sad
For the problem f, The proof of the solution is
Let F(i) be the first term when F(i)%k == 0, then the series from the ith term modulo k for every term (F%k) onward will be like F(i-1),0,F(i-1)*(1), F(i-1)*(1),F(i — 1)*(2), F(i — 1)*(3),... F(i-1)*F(i)
Now, we can can say that F(i — 1)%k != 0 since F(i)%k == 0 as we assumed, therefore the 2*ith term which is F(2*i)%k = F(i — 1)*F(i),.. Now carrying on forward, we can say that i,2*i, 3*i, 4*i,... will be the term when F(i)%k == 0.
This is nice, but how do we know that there is no zero in between $$$F(i)$$$ and $$$F(2i)$$$. I was wondering what if $$$F(i-1)*F(j)$$$ is a multiple of $$$k$$$, where $$$j < i-1$$$
The Fibonacci sequence modulo k is known to be periodic, with the period length called the Pisano period. This means that Fibonacci numbers modulo k will eventually repeat after a fixed number of terms. Once the sequence reaches F(i) (the first number divisible by k ), the subsequent terms follow a predictable pattern.
Its a little unclear still. Can you explain a little more?
Pisano period
I read pisano period. But pisano period just says that there is a cycle. Not necessarily that the 0s also cycle.
What if there are two zeros but unevenly occurring in the cycle, then the 0s don't cycle.
For ex: Let's say the cycle length if 5 and the first, 4th and 5th number is a 0. Then the 0s don't form a cycle.
For the problem F ,
what is the proof for the following fact : I brute forced for all prime's up to 1e6 (p) to find index of the smallest fibonacci number that is == 0 (mod p)
2:3
3:4
5:5
7:8
11:10
13:7
17:9
19:18
23:24
29:14
31:30
37:19
41:20
43:44
47:16
53:27
59:58
61:15
67:68
71:70
73:37
79:78
83:84
89:11
97:49
as you can see the value is at most n+1 , that allows for submissions like rainboy's to pass as they just naively find the first fibonacci number which is == 0 (mod k) and multiply it by n.
Does anyone has a proof for this , why does this work ?
i do the same thing, and my function that does this was promptly named PROOFBYAC :D.
C was too hard for a div3C, totally made for guessing the solution. In D, you could have explained what you meant by non-overlapping, do you consider (a,b) and (b,c) to be non-overlapping? or do you consider (a,b) (b+1,c) to be non-overlapping? Its the former,which i got to know after a WA.
totally made for guessing the solution
Disagree with this. If you start solving the problem from the middle, the problem becomes quite simple I believe. If we consider the even case, we can fix the middle two elements in any order, because no matter how the middle two are arranged, we can always adjust the rest of the elements relative to them. Now once we fix the middle two elements, we start moving outward. Suppose we are at $$$l,r$$$ currently, now we just need to compare with elements $$$l+1,r-1$$$. If swapping $$$l$$$ and $$$r$$$ results in a better answer than not swapping, then we should definitely swap them. Instead of just swapping $$$l$$$ and $$$r$$$, think of each step as swapping the entire prefix till $$$l$$$ and the entire suffix from $$$r$$$ onwards. If we think of it this way, one can see that only the relationship between $$$l,r$$$ and $$$l+1,r-1$$$ is changing, everything else stays the same. Hence, it is always enough to look at the immediate inner neighbors, and swap if it improves the answer.
I'm a little surprised that this problem has barely more solves as E. I was a tester and when I was giving virtual contest, this was actually problem B. While I did feel that this might be a little hard for a B, didn't think it's as hard as E.
instead of just swapping land r, think of each step as swapping the entire prefix till l and the entire suffix from r onwards
Could you explain this more?
did you get it ?
Assuming we have an array of 6 elements:
a1, a2, a3, a4, a5, a6
We can actually fix the middle two elements in any order because the two middle elements are a3 and a4. We can place a3 on either the left or the right. Wherever we decide to place it, it won’t affect our future choices because we can choose a2 and a5 however we want in the future. So, if a3 in the optimal arrangement should be before a5, we can leave a3 in its place and then swap a2 and a5, which will have the same effect as swapping a3 and a4.
That’s what he means by prefix and suffix. If you decide to swap L and R, then whatever needs to be a neighbor to L after it’s swapped can still be its neighbor, and the same applies for R. disclaimer : I wrote this comment to better understand the problem myself so I might be Hallucinating
Sorry for the late reply, I had gotten extremely busy with some stuff. Hope this will still be a relevant answer to your question.
I am trying to prove why it is optimal to swap $$$l,r$$$ solely based on their relation with their inner neighbors $$$l+1,r-1$$$. One might think that swapping $$$l,r$$$ might be better with respect to the inner neighbors, but maybe it worsens the situation with the outer neighbours, i.e. $$$l-1,r+1$$$. The answer to this is that, instead of thinking as just swapping $$$l,r$$$, think that you are swapping all of $$$(l,r), (l-1,r+1), (l-2,r+2),....(0,n-1)$$$. Basically the entire prefix till $$$l$$$ is being swapped with the corresponding mirror element in the suffix till $$$r$$$.
The reason why I tell you to think of it in this way is that if you look at the kind of a swap overall, the only thing that is changing is the relationship between $$$l,r$$$ and $$$l+1,r-1$$$, everything else stays completely the same. Main point being, the relationship with the outer neighbors stays the same, hence this is a counter to the initial thought of 'it might worsen the situation with respect to the outer neighbors'. So we have basically found a way in which we can ensure that we can always get the minimum possible 'disturbance' between every $$$l,r$$$ and their inner neighbors $$$l+1,r-1$$$, which is kind of a greedy approach, since we are able to get the minimum possible answer at every single step, which will obviously result in the minimum answer overall.
Let me know if you happen to have any further questions or there's a part that's still not clear.
Apologies if it is asking too much.
With ref to this comment https://codeforces.net/blog/entry/135421?#comment-1211619
How can we prove the correctness with exchange argument ? Assuming that we have a optimal solution and we can swap reverse the subarray between (i, n-i). ?
When you reverse the subarray from i to n-i, the only thing that is changing is the relationship between i, i-1 and n-i, n-i+1. So that means our operation did not affect anything else, and within what got affected, we got a better answer. So that means that our method will always give an optimal solution.
Ok.
So exchange argument forwarded is. Start with an optimal solution. And show that we can transform from optimal to our solution without changing "disturbance " at any step we are doing the transformation. While I understand the disturbance not changing anywhere except between i-1, i and mirror of it. Not clear, how it is is proved in the original argument provided by the op that the disturbance of combined disturbance (i, i-1) and mirror is same in the optimal before and after the transformation, which op n as can be easily shown.
If you have any idea around will be thankful for that.
Sorry again, to ask you a question for the solution not provided by you.
I don't think I understand your question exactly, what do you mean by "Not clear, how it is proved...."
I started from the beginning. The order of the first and last elements do not matter, so put them in any order. Then, while filling the positions (l, r), I compared them to the elements right outside (l-1, r+1), the position I filled in the previous step. This works, but I do not know why.
Previous to this, I tried swapping each position and comparing whether disturbances decrease. I compared l with both neighbors (l+1, l-1) and r with (r+1, r-1). I got a score out of 4. If swapping decreases this score, then swapping is optimal. Else it's not. This did not even pass the sample test cases. Any idea why?
because you are comparing and determining the current greedy optimal with something that might be changed in the future (l+1,r-1)
Can someone please hack this solution?
https://codeforces.net/contest/2033/submission/287788123
Thanks!
i doubt that anyone can, youre essentially just breaking down a big cycle into 2-cycles or 1-cycle, which is optimal.
Yes, but I thought that since I am using map, so maybe there might be some testcase that can cause a TLE? 1983ms runtime on a qn with 2s limit seems hackable no?
yea it seems so, but im not really sure what makes it so slow in the last test. it seems that no matter the input, you will always do (n-1)/2 operations which means you will be accessing the map that many times, and i tried to hack like that, but that passes in 500ms. maybe when you have multiple test cases and make a new map and initialize it all over again or something like that
Guys what would you suggest to learn or what do you think should be the mane focus on people like my that make it till problem B in div 2 and div 3. Like I know what DP is or Recursion. I've learnt about this topics and can I know on what field to use them but when I get a problem I have a great visualization on what to do but as soon as I get on to typing the code I get lost in stupid shit. What is your suggestion on solving this
why so many D's are getting Hacked ??
Because of unordered map I think.
.
vouch
Overflow/underflow problems, I assume. You need to use a 64 bit integer map/set key as n = 10^5 and ai can be in range -(10^5) to 10^5, so total sum of a can be -(10^10) or 10^10, which are respectively less than INT_MIN and greater than INT_MAX. As such, I believe solutions that use a 32 bit integer map/set key will be prone to hacks.
Below is a generator for hacking people storing their prefix sum in map/set with 32 bit integer key. It causes an overflow which results in the integer value '32704' to be stored in the map, then carefully adds negative integers until a final value is added to be equal to '32704'. This causes the bugged code to falsely find a prefix sum which doesn't exist in reality.
Thanks man
Yeah, mine too got hacked.
Can someone please hack my solution for C?
287837237
I just did mindless greedy.
div 3 more like div 2 lol
guys my solution got hacked, and i dont really understand how, and what is wrong with it, i'm new to codeforces, can anyone check and tell me why did it got hacked?
change unordered_map to map.
How does that actually work tho , like could you please give me an example of the difference or a test case for instance
For unordered_map worst case time complexity for searching can be O(n) while using map it is O(logn).
See test case 12 of problem D.Unordered_map will give you TLE.
Ohh okay, thanks
Does anyone know how to approach problem F intuitively without any googling or guessing the idea. Like ok maybe I can guess the first occurrence of zero must be periodic for all zeros, but how to prove this simply?
This is how i solved: First observe/guess that when you find the first number divisible by k, its just periodic and every x-th number is divisible by k. Then I try and calculate the first k fibonaci numbers and assume that its enough to find the first divisble number. That fails on test cases, but k+1 passes, so i submit. Get WA on test2. Ok so lets just assume that we can calculate it in some y*k time where y isnt too big, and if i just calculate until i find it, it should pass time limits. Submit and get AC.
Ya I thought of that in contest, but here you are still making the guess that after you find the first divisible by k number, you then just output n*k. Is there a proof on why this 0 must be periodic? Like maybe let the first position be x, how do you know there is not also a 0 between x and 2x? This is the uncertainty I had in contest which made me hesitant to submit.
huge part of solving problem C is realizing that it's a div 3 C which is a skill that only needed in code forces
After upsolving this div3C I actually doubt I'm a pupil (Dropped to newbie after this contest). Time to climb up the rating again...
I upsolved also but still didn't learn anything from it there is this comment which I couldn't understand yet but I will try more
Yes, we need to try to get better. The newbie-pupil struggle...
Btw the comment of that tester actually correct/good instinct. Good note
whats the point of questions like F that require some kind of math theory and code that can be easily generated by gpt. I can assure you atleast 80 percent of the people who did it googled/GPTed it.
git gud and stop crying
get good at using GPT? Sure.
how about spending your time learning to solve problems instead of crying about not being able to solve trivial problems
yes very trivial. Just know about some niche math theory. Stop trolling mate. lol.
FYI, googling things is not considered cheating
I solved it with a pen and a notebook in $$$7$$$ minutes (though not fully giving concrete proofs before coding, trusting my intuition), so umm.......
can you go through your thought process? Did you prove the existence of pisano period in 7 minutes?
Disclaimer: As said, I didn't fully prove it. It's just how strong an intuition proved to be in my mind to assert confidence.
First, I see the periodic repetition in the sample, and the really questionable answer for sample case 3 (so close to mod, and given 1e18 was there, the operation should be something pretty simple).
Then, I turn the notebook and draft some $$$k$$$. It dawns on me that it's truly periodic, except for $$$k = 2$$$ there's never a $$$[0, \frac{k}{2}, \frac{k}{2}]$$$ subarray in the modular sequence. The most concrete fact that pushes me into immediate coding is that Fibonacci sequence doesn't really take divisors into account, so in the perfect world, it should be something close enough to a normal random distribution of modulus, rendering the linear nature of the period size.
I got my idea without googling I generated the Fibonacci sequence to check till 20th number and found that there will be cycle which is a fact I got to know later, but I couldn't implement it out in the contest
why did div3 not allow rating???
it will be updated
too unfortunate this 287855687 get wrong on problem C. I was soo close
good round, solved upto D hoping for pupil soon
got hacked on D for using unordered map though, upsolved using set.
overall a good performance on my part, performance of around 1200 (after hack), 1350 (before hack)
how to know your new rate before the contest test end
why aren't people using two pointer to solve C
It's the approach I got during the contest and it's been accepted. After seeing post contest discussions I see a lot of people saying it should be solved using DP.
I will upsolve but I don't understand why didn't a lot of people solve it using two ptr during the contest.
I Will become a specialist in this contest. Lets go!
why contest unrated?
Can someone help my G? I don't know why I got TLE on test 8, plz. 287869462
For F: https://www.geeksforgeeks.org/nth-multiple-number-fibonacci-series/ Added a few modulos and raised max n and got AC
I was trying to find this code during the contest but I was not able to and couldn't implement out my idea :(
I was hacked in problem D. I already was unhappy by my performance in that since I was so close to submitting E, I derived the cycle but then failed on figuring out that it would (k-1)/2, I was trying k/2. But then D also got hacked because of something I can't figure out
Anyway,
I submitted this using an unordered_map which got TLE and was hacked :(
Then I submitted using a multiset which got AC.
Isn't a mutiset slower than unordered_map?
I think this passage Blowing up unordered_map, and how to stop getting hacked on it would be helpful.
Yeah, just read it. Never thought STL could also be inefficient.
Remember one thing donot use unordered map until and unless it is the only choice
yeah. Learned a costly lesson. I think I deserved a rank around 3k. But cudn't solve E because of c/2 and (c-1)/2, got 6k rank. But then D got hacked, got 11k.
So yeah, never using unordered_map or unordered_set again.
Btw, did u get any idea about G?
I am incapable of doing G as I haven't studied graphs properly yet know little basics only
guys that was my first contest and i've solved only one problem (first obv) and will i get rated after this?
Yep, just have a bit of patience until testing is done.
Given the number of successful hacks for Problem D , it is so that deliberately the tests are weak so that the contestants can hack each other's solution and earn points?? JUST A POV :)
https://aryanc403.com/blog/psa-hash-collisions/
For problem E came up with this solution though cannot prove it and didn't manage to submit by some seconds :-))
This basically tries to make permutation and "reverse-permutation" equal in <= N steps.
I got tle on test case 49 of D even after using custom hash in unordered_map.
I think question G is better than question F, question F can be written quickly by guessing the conclusion, and question C is also more difficult than question D and E.
When will the Rating's Be updated
is there any site that give the expected ones out
Rating is already updated. You can use carrot extension.
Oh, NO. I want to regist but late!!
1259 still newbie T_T
Arghhhh, why is https://codeforces.net/contest/2033/submission/287918494 TLEing for G? It's literally segtree + dfs which I hope is intended solution.
Maybe extra logN factor introduced by sorting?
https://codeforces.net/contest/2033/submission/287941915
Removed the sorting thing, made optimization in number of queries made for segtree, still TLEing lol
I have the same question as you. 287933697 I use Heavy-light Decomposition and Sparse Table to make optimization, still TLE too.
So strange after I use multiplication algorithm, it runs in 300ms. 287948215
Well, my update function of segtree was incorrect and worked in O(n) instead of O(log n), once I fixed it, the solution ACed. Maybe same is the case with you. But HLD here is overkill lol
Congratulations, I guess so, lol.
what is the logic behind G
Understand K-father.
It can be done using lca / binary lifting
UPDATE: the solution is correct except for the way I define the end of the range on which I calc dp table,
For example, if n = 5, we need to calc dp for 0, 1, 2
and if n = 4, then we need 0, 1 simply it's half-interval [0,ceil(n/2)) NOT [0,floor(n/2))
This line is wrong
int limit = n / 2;I tried to solve C with dp.
The idea is
dp[i][0] -- min shit in prefix [0, i] and corresponding suffix IF we do not swap at i
dp[i][1] -- same but if we do a swap at i
Clearly, or so I think, dp[i+1][0] can be computed from dp[i][0], and dp[i][1], same for dp[i+1][1]
But my code is not outputting correct result. Can someone help me identify the bug? is the approach wrong? or some bug in the code?
https://codeforces.net/contest/2033/submission/287926217
can anyone help me to get out of this i solved problem D during contest but it get's wrong answer on 9th test case while checking on updated test case then i change my data from int to long i though that might be the cause but now it is giving tle on test case 16 please help here is my code ````````````````````` int n = in(); long[] a = new long[n]; for (int i = 0; i < n; i++) { a[i] = inl(); } int cnt = 0; long pre = 0;
HashSet<Long> hs = new HashSet<>(); hs.add(0L); for (int i = 0; i < n; i++) { pre += a[i]; if (hs.contains(pre)) { cnt++; hs.clear(); hs.add(0L); pre = 0; } else { hs.add(pre); } } out.println(cnt);````````````````````
https://aryanc403.com/blog/psa-hash-collisions/
TLDR, just use normal set and map unless you have a clear reason to use hash map or hash set because though they are O(1) on average, they are O(n) on worst case and it's possible to construct test cases against hash map
got it Thanks
Can anyone help me with my submission for D, I use Java and I've noticed that I am getting tle if I use map.clear() in submission 287709751 but if I re-instantiate the map 287930490 it gets accepted.
Upd: Got it clear function just sets all entries to null by traversing the array and the size remains the same.
How can C be solved with binary search? I am asking because I noticed that problem C tags involved binary search for some time.
Also, I am curious to know how these tags are added. Is it detected somehow automatically from submitted solutions? I noticed that after I submitted my dp solutions, the dp tag was added again.
Tags are added by people that can be "trusted" to handle tags properly, and by "trusted" I actually just mean people above a certain rating (I believe that would be CM)
There actually was an instance when people mass-spammed tags on the D problem, and a similar thing likely happened on the C problem on a smaller scale.
Circling back to the first question, if a binary search solution even does exist it would be slower than the intended solution for C (as shown in the editorial).
I was stuck at Verifying whether you are a human screen for more about 10 minutes. I tried giving the contest on mirror websites but for some reason, the problem statements weren't available. What is the point of having mirror websites if you can't access questions on them? By the time the page finally loaded there were already more than 7000 submissions on problem A
Such incidents of 1. Website not loading 2. Being stuck on the "Verifying if human" screen 3. Website crashing multiple times are getting more and more frequent.
MikeMirzayanov Look into this matter
How to solve G? Thank you
Note that you can go to K-father from a vertex, and the answer is contributed by any vertex and the path of K-father.
Let's define $$$dp_i$$$ means a vertex can go to its deepest son of $$$dp_i$$$ length, $$$cdp_i$$$ means a vertex can go to its the second deepest son of $$$cdp_i$$$ length(The paths do not intersect).
You can get a new array $$$len_i$$$ means the longest path that the father $$$u$$$ of $$$i$$$ can reach without passing through $$$i$$$. It's either $$$dp_u$$$ or $$$cdp_u$$$.
Now we want to know how long he could go. Note that $$$i$$$'s father $$$u$$$ contributes $$$len_u + 1$$$, $$$i$$$'s father's father $$$v$$$ contributes $$$len_v + 2$$$...
So if we design $$$len_i$$$ as $$$len_i - dep_i$$$, our mission is to get the $$$\max$$$ on the path from the vertex and its K-father. When get the maximum of the path, add $$$dep_i$$$ back. Remember we have another choice is to go to the vertex's son. Just take the maximum value. Then use multiplication algorithm to solve it!
This is my submission 287948215.
It confused me a lot. I thought my submission 287933697 is totolly $$$O((n+q)\log{n})$$$. Why I got TLE?
how did i do d,e,f but not c
How on earth is it possible? Problem D, TLE with std::unordered set but works all fine with std::set?
TLE-with-unordered-set
Okay-with-set
worst case time complexity of unordered_set is O(n) for insertion/ deletion.
thanks a lot, i thought hashing worked randomly, apparently they are hackable by finding a sequence of numbers that tries to insert at the same place
Hi till when can we expect the text editorial ? Thanks ! @FBI
Auto comment: topic has been updated by FBI (previous revision, new revision, compare).
Hello codeforces Headquarters, Vladosiya,
I received an email about a rule violation, specifically about the coincidence of C code. I was surprised that someone wrote the same code as me.
I can only explain this as a random similarity, because the way to solve the C problem is very limited and simple, I also did it in Python, a simple language so the random similarity is very likely to happen.
I commit that I did not violate the rules.
I really hope that there will be a fair assessment and treatment for me.
Hello, Codeforces Headquarters, Vladosiya ,
I would like to report a false accusation of cheating regarding my code for the last Div.3 E problem.
My code works by checking each unvisited index within a cycle, marking it as visited, and counting the cycle's length $$$(c)$$$ . If $$$c \ge 3$$$ , we need to perform swaps, as each swap reduces the cycle length by two. This results in $$$\left \lfloor \frac{c - 1}{2} \right \rfloor$$$ swaps being necessary.
(I think I've to make screencasts to avoid this ?) + (I've solved some similar problem somewhere)
Please take this into consideration
Thank you.
I once again , call for consideration , my code is even similar to editorial's one ? , and the code is already short .
MikeMirzayanov , I can see that even editorial's code is close to it .
I didn't wanted to ping , but no body gave attention.