Gamarjoba, Codeforces!
On Feb/06/2024 17:45 (Moscow time) will start Codeforces Round 923 (Div. 3), the next Codeforces round for the Div.3.
Lately, I've been coming up with problem ideas less frequently, but I don't want to lose this skill. Welcome to the round where all problems are my own creation! I hope you'll enjoy them.
A huge thank you to Vladosiya for preparing the majority of problems in Polygon. Also, thanks to pashka and KAN for helping with the discussion of problem ideas.
Thank you very much 74TrAkToR, CLown1331, EternalAlexander, Jostic11, Killever, KoT_OsKaR, LoveWX, MADE_IN_HEAVEN, dan_dolmatov, jnmtz111__, pedrolino, theRealChainman, yorky for testing the round.
As usual for the Div.3 rounds:
- There will be 6-8 tasks in a round.
- The round duration is 2 hours and 15 minutes.
- The round follows the ICPC rules, with a penalty for an incorrect submission being 10 minutes.
- The round is rated for participants with ratings up to 1600.
- After the round, there will be a 12-hour open hacking phase.
Remember that only the trusted participants of the Div.3 will be included in the official standings table. As it is written in the link, this is a compulsory measure to combat unsporting behavior. To qualify as a trusted participant of the third division, you must:
- Participate in at least five rated rounds (and solve at least one problem in each of them).
- Not have a rating of 1900 or higher.
Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.
Good luck to all!
I really like it when the round announcement includes a photo of the authors. I plan to add one if I can take a suitable photo.
UPD 1: I found great burgers in Tbilisi!
UPD 2: The editorial is published: https://mirror.codeforces.com/blog/entry/125597 (thank you, Vladosiya).
As a Participant, I would recommend to participate.
.
omg MikeMirzayanov round
for this I'm going to participate this round even though out of competition
.
fdgdfg
can people like you not to spam appeals everywhere to catch attention
ffdgf
jdfskkdfhj
can you shut up, your "main" account has nothing and you cheated twice in a row, lol.
dfsdf
then either not cheat on an account of "importance" or reach the admins of those groups and tell them how big of a cheater you are and beg for your second account to be on the group. Also, why would you cheat on codeforces anyways, the only benefit is rating which doesn't matter if you cheated for it. And having two accounts for submitting same solution doesn't make sence either, you will get same delta regardless. So don't cheat or don't exist in codeforces
sdjcndscd
Don't you know that one can also see your comment before the edit? lol
Guys the abcdef plan is cancelled, set goals on abcd
PS The questions mike comes up with are wonderful, mind challenging, and Unique
They aren't.
You've only solved 1 F'ing question Where you 99% copied it
My last rated Div 3
Good luck to you. By the way I'm from Afghanistan too.
Good luck for you!
My first unrated div3
Best of luck
A good example of haters gonna hate!
he's my bro
Nice
First time testing :D, wish you high delta.
This is the first time I participate in a contest. Hope to become pupil!
Even if you win the contest that is impossible.
yep, see MakaPakka which was the 1st in his first contest which also is a div2 not div3. (Just wanted to prove your point)
you'll need a few more contests before getting pupil. don't worry soon you will become a pupil. even if you don't you'll learn a lot
I think it's the 100th div3.
Woow, it really is!
good luck!
Good luck to everyone and hope positive delta for all. I wish i get +100 at least in this contest :)
GOOD LUCK ! everyone
MikeMirzayanov is a Barcelona fan
But I am a Real Madrid fan. So I must take part in this round to get cyan.
That t-shirt says "Barcelona University".
Seems like you really enjoyed the burger , cant wait to participate
hope reach pupil after the round
Did you use divide and conquer algorithm before eating ?
that burger looks yum
can i have a mikeburger and uhh 1 mike fries and uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuh 1 cup of mikeflurry please
Sir, this is a Wendy's
😂 😂 So you shifted from negative contribution farming to positive farming xD?
why do you care about contribution so much, that's all you ever talk about, well that and the cheaters
This account is designed / created for those aspects especially busting cheaters.
I thought the joke was unfunny but appatently you like it >:(
Wait, Mike is in Tbilisi? I live here! Hope you have a nice stay!
Time to farm some ratings. Hope to become specialist after this round.
gemrielad miirtvit, MikeMirzayanov
A Mike contest! Hope that I can get to expert this round
Hey! Hey! Hey! I am also a big fan of burgers as well, although you must try Adjaruli Khachapuri! If you have time maybe you want to meet up with the Georgian CP community? (If you have not tried Adjaruli Khachapuri yet, maybe we can go together?). Anyway, have fun in Georgia!
He should try Khinkali also :D
Can't wait to become an Expert
you will make it!come on bro
hope that will be my last rated div3 and also best wishes for you!
same to u bro !!
congratulation bro !
same to u haha
Good luck! Rating increase!
go georgia!
As a Participant , i love burger
as a burger, i love mike
I`m sigma
. All the newbies out there, Don't loose hope Never under estimate the power of a newbie, the newbies make history. Newbies are the real fighters, they fight even after loosing a lot, I am a newbie too, but history repeats itself, newbies become pupil then blue then eventually red.
Not today, not tomorrow, maybe not even after a month, but one day , mark my words, one day you gonna be happy for not giving up.
Let me tell you something-----> Once upon a time a newbie said "I'm gonna be at No.1 at the CodeForces", everyone laughed expert the guy who was at No.1 , cause he knew a warm blooded newbie can do what he says.........
LONG LIVE THE NEWBIES! DOWN WITH THE GRANDMASTERS!!!
I am a newbie fighter, most determined man on the planet earth. Mark my words!. I will one day reach my dream rating (800) , then I will reach spectralist rank , then glandmaster . I will beat Sundar pichai and become Ceo of Goggle and get $500 bullion USD wealth . Never give up!! (never gonna let you down)
Everyone was a newbie at once.
Except some veterans who got 1500 initial rating XD
how does codeforces know someone is a veteran and give them 1500 rating XD
GIGACHAD Mike Mirzayanov round HOLY PogU
time to become pupil!
n
Damn that Burger looks good!
what a juicy burger in this morning i woke up
what is the mean of burger ? I guess the original mean of word is changed by folks of codeforce. could you tell me ?
oh , I see! His burger is juicy ^_^!
I feel like all the Div. 3/4 rounds are inaccessible to US students, is this normal or are there going to be more Div 3/4 rounds that are at a good time for US students (afternoon/evening in Pacific-Eastern time)?
But the problems will definitely be great — thanks for writing the round! I will probably virtual participate or solve problems individually.
Then they would be inaccessible to European and Asian students.
Div3 by Mike and a delicious burger! Surely gonna be a round of all times.
Well, I've just found that Mike is also a Barcelona fan!
Look at Mike's T-shirt.
Barcelona can also mean a city, we can't be sure because it doesn't have Barcelona football team's logo on it.
As a Tester, I really like this round and recommend to participate. Happy Spring Festival!
My first unrated Div3
pedrolino GOAT
❤️
No way, 74TrAkToR comeback
Calling specialist.I need 14 point.
1400 — 1386 = 14
yep.it was my mistake. thankyou
The burger looks delicious
First rated Div 3. as a specialist! Hope to not lose rating!
Nice. I'm always worried that I'll lose points if I participate in div2, but I don't have to worry about div3.
A good day starts with seeing the game (did the author take this picture with permission)
I hope to get a good score.
hope i can reach pupil this time :p
Expecting some great problems as Mike Orz has prepared them! All the best, everyone!
hopefully this will be my come back contest
Трактор тащи
This is my 6th rated contest and I feel like lucky to be able to farm on Div.3 before all my 1400 initial rating is used up. If everything goes well this will be my last rated Div.3
I want to eat burger too.
Me too! I want fries as well as burgers.
(I had burgers for dinner last night.)
M I K E C O N T E S T
(Very excited, the first mike contest I'll participate in)
An interesting Div. 3 contest by Mike, sounds great!
I was waiting for this round. Because during 1 week was only round div2. And we have chance to improve our rating.
Eden Hazard round.
Burgerrr reference? Chelsea fan?
Football fan.
No one could stop me from eating a burger when coding!
This will be my first rated round.
THE LEGEND @MikeMirzayanov !! himself has set the questions...really excited to attempt the questions and enjoy the contest..
UPD: I found great burgers in Tbilisi!
So where? :) Bon appetit!
big sam's
Waiting to finish my round the next Div.3 round MikeMirzayanov
@ZettaByte
Yeah MikeMirzayanov Round!!
Thank you for a yet again amazing round! You look quite handsome, by the way wink!
DelayForces.
1 Refresh = 10 minutes delay
Ah shit, here we go again
DelayForces... Again
10 minutes delay?
whenever there is a delay, there is 74Traktor :(
Again and again and again.
fr!?
Beginning time 22:35 -> 22:45?
Delayforces again :(
delay:<
why delayed
Why the ten minute delay?
Not a 10 min delay again!
Wow, is the man who eating hanburgers MikeMirzayanov?
Delayyyyy
Anyways, hope to become a green lantern today
Nah, I'd win.
delayForces
Hahaha
wait what?? 40k participants??
The contest is going to be QueueForces
Does someone have a reason that why are they postponing for 10 minutes?
Tasty burgers :)
41k+ participation ?
Queueueueueueueueueueueueueue...
Is problem B not solvable in Python? Had to switch to c++ to get accepted with the same implementation. Got 7 tle :(
I'm the opposite lol, 6 tle with c++ but ac when switch to python
Same here. I got multiple TLEs with PyPy before optimizing my solution and getting AC.
Seems like time limit per test should've been 3 seconds instead of 2
omg you were in Georgia?
Good contest, Good Problems.
My rank will be updated or not since there are several participants above 1600 rating in contest?
It was a wonderful contest
cool contest with a cool problemset!! I felt D was easier than C, at least in terms of implementation.
E was easier than C and D
How E ?
What's the best way for construction E?
So the idea was that elements as i and i+k differ by atmost 1.
One way to do this was you put consecutive elements starting from 1 and take jumps of k, and wrap around to the array to start again from last unfilled index.
But the subarray sums would be increasing by 1 in each case.
Instead, we can alternate between putting elements from 1 onwards in increasing order, and in decreasing order from n the other time. This way the subarray sum differs by atmost 1.
Code
for $$$k = 4$$$ it always have to be either
$$${x, y, z, w, x - 1, y + 1, z - 1, w + 1, x - 2, y + 2, z - 2, w + 2, ...}$$$
$$$or$$$
$$${x, y, z, w, x + 1, y - 1, z + 1, w - 1, x + 2, y - 2, z + 2, w - 2, ...}$$$
How to solve E ?
For Problem E
(overexcited because first E solve in 3yrs)
observation: elements $$$a[i]$$$ and $$$a[i+k]$$$ can differ by only 1. Now, this means $$$a[i+k]$$$ can be bigger or smaller than $$$a[i]$$$, but only by one.
Reason: if this is not maintained, then the sum of two immediately neighbouring permutations itself goes out of constraint, let alone thinking about the relationship about relations between all such permutations.
Proof-ish: If we say $$$S(x)$$$ is sum of permutation starting at position x, then $$$S(x) - S(x+1) = a[x] - a[x+k]$$$. Thus, all $$$a[i]$$$ and $$$a[i+k]$$$ must not differ by more than $$$1$$$. (Also, they can't differ by zero because we only have one available occurrence of any integer. So, that means they must differ by exactly $$$1$$$).
Construction: For all $$$even$$$ positioned elements: maintain $$$a[i] - a[i+k] = 1$$$. Similarly for all $$$odd$$$ positioned elements maintain the opposite, i.e $$$a[i] - a[i+k] = -1$$$.
We can see that doing so, means the sums of permutations will keep alternating by $$$1$$$. That is the list of sums of permutations will look like $$$(A),(A+1),(A),(A+1),\ldots$$$
Helpful Explanation.
I solved $$$G$$$ but couldn't solve $$$F$$$
I solved F but couldn't solve E
I solved E in 10-15 minutes but couldn’t solve D
Why does Mo TLE for D ?
What? The solution is just to form rle array and binsearch it for each query. There is no complex structures needed.
Yeah i know that. Even Binary search is not the best approach as you can do it in $$$O(n)$$$ using stack.That's not the point.
Wait what? Stack? It is much simpler: Define $$$nxt_i$$$ as the smallest number $$$j$$$ such that $$$i < j$$$ and $$$a_i \neq a_j$$$. If there is no such $$$j$$$ then $$$nxt_i=n+1$$$. Figuring out array $$$nxt$$$ is trivial and can be done in $$$O(n)$$$. Then for a query with $$$l$$$ and $$$r$$$, if $$$nxt_l$$$ is higher than $$$r$$$ then the answer is -1, otherwise the answer is $$$(l,nxt_l)$$$.
i instinctively used stack to calculate $$$nxt_i$$$ but yea that was unecessary.My bad
What? The solution is just storing index of the last not equal element. There is no binary search needed.
Oh yeah, you are right. Sorry.
how to look for that stored index fast without binary search or map or set ?
create an array $$$nxt$$$ of size $$$n$$$, initially filled with $$$-1$$$ values. $$$nxt_i$$$ will store index of the last element which is not equal to $$$a_i$$$
Transition looks like:
we can calculate it in $$$O(n)$$$ .
for $$$[l, r]$$$ query, if $$$nxt_r >= l$$$ answer is $$$[nxt_r, r]$$$ , otherwise answer is $$$[-1,-1]$$$
rle array, whats that? I used 2 segment trees lol
I also tried Mo on D... I learned it today so when I saw the problem I immediately thought of it, though it seems there was a much better way :(
It doesn't TLE, the problem is that you are using a map to store the elements of the current range, and as you make $$$O(n\sqrt n)$$$ insertions and deletions on this map (because mo does $$$O(n\sqrt n)$$$ updates), your code ends up being $$$O(n\sqrt n\ log\ n)$$$ which is too much for $$$n\leq 2*10^5$$$. In fact, there exists a solution with mo for this problem, which got AC in 1528ms, here it is. Tell me if you want me to explain the idea behind that solution (the key is to keep updates in $$$O(1)$$$ and you can still do queries in $$$O(\sqrt n)$$$, as there are only $$$n$$$ queries).
speedforces
The contest was too easy, especially D with a simple segment tree implementation
You could also solve it using binary search over the indices where the next element is different.
I tried implementing this but my code fails somewhere, would you mind taking a look and telling me where I might have made a mistake? Thanks in advance. Here's the submission
I made the same mistake. :)
diff might be diffs.size() in the case when l is greater than all the values in diffs[], lower_bound would return diffs.end() here
Welp, my previous submission tried to address that problem, but It's funny I still couldn't get it right, take a look here. And here for the accepted one. I just combined two incomplete submissions into a single good one >:D
You can also solve it in O(n) time by calculating the closest non mathing pair for all indices
waste an hours on D for messing with segtree (TLE) and ask for help to cheageepeetee with no gain until realize it's simple two-pointer problem 💩
i used two pointers but got TLE
for each position i save the first index j (i < j) where a[i] != a[j], then it's O(n + q)
same wasted 1 full hour implementing segtree(was implementing segtree for the first time in contest and 4-5 times otherwise ) where as i could just store all unique indexes and do binary search or something like that
:<(
The contest was too easy, especially E with a simple observation
I could find the pattern and prove why it works too.
But I finished my implementation a couple of minutes after the contest. But, thankfully it was WA on test 2. Some implementation bug maybe. Submission
UPD: AC
F.
How to find the edge with the smallest weight that can be part of a cycle? If an edge is not a part of a cycle, then it must be a bridge, and vice versa. So we have to find the edge with the smallest weight that's not a bridge. Bridges are explained here
After choosing the edge, we can just use DFS (BFS can be used too) to find any cycle that contains this edge, by DFSing from one end of the edge and setting parent as the other end so it won't come back immediately.
You can just sort the edges in decreasing order and unite with DSU. To check whether there exists a cycle containing an edge, check whether the endpoints are in the same component just before adding this edge.
Bruh — I started writing exactly that, but then I thought it wouldn't work for some reason... yea your solution is much better
Yeah, I came up with that about 5min after reading the problem but later on I realized, "what if the order of edges matters?" because perhaps other edges of the same weight would be needed to complete the cycle.
But actually it doesn't matter, because such a cycle will be found when considering the last of these edges in the sorting.
after finding the optimal edge how did you construct the simple ycle where the edge exists?
Same as drdilyor mentioned, you remove the edge then run BFS to find a path.
Thanks bro ! Appreciate it.
drdilyor, I have one doubt if you can please help.
Can the problem F can also be solved using binary search. Predicate : Can we find a cycle in the graph in which the minimum edge weight atmost x. And delete all the edges weight greater than X and then consider the remaining graph.
I think it will also follow monotonicity.
If you can reply please reply will be very helpful. Thank you
Unfortunately that won't really work, it's asking the minimum of the weights in cycle to be minimum. Consider this graph
We want to find the cycle with weights (1, 4, 4), and not (2,2,2). So you see, this doesn't fit the "minimum of maximum" pattern of binary search. We would need predicate to be able to find if there are cycles that have smaller minimum weight than $$$X$$$, which I think is just as hard as the original problem.
drdilyor, Thank you very much for your help and explaining so much clearly. Thanks again for devoting your time to solve the doubt.
You can find an edge with the smallest weight that sits on a cycle with 1 DFS in $$$O(m)$$$, no concept of bridge necessary. If you track visited time you can figure out that you encountered a cycle when
ins[child]<ins[x]. Keep a countC[u]of when the nodeuformed a cycle and the number of cycles currently not closed by dfscycle_count. When you leave a nodexin dfs, you check if any cycles were opened on itC[x]and if so, you close the cyclescycle_count -= C[x].Now if the
cycle_count > cycle_count_when_node_was_visitedyou know that the edge fromxto its parent needs to be considered for the minimum weight edge.https://mirror.codeforces.com/contest/1927/submission/245472637
For Div 3. do we get rankings on no. of problems solved? coz I can't see any points for problems
it might be based on penalty. for ex: you have 200 penalty and I have 246 penalty.
this is an ICPC-style round. The rules are so: if participant 1 solved more tasks(no matter their order) than participant 2, he will be higher. If they solved equal N of problems, the one having less penalty, will be placed higher. Penalty is given based on sum of time of submissions
The participants are sorted in descending order of number problems solved, in case of a tie, the participant with lower penalty comes before.
Do I have to find all bridges in the graph for Problem F? It would be a ton of code if I have to use DSU and LCA for judging bridges and I have been working on it for 70mins.
Edit 2: RecursiveCo has proposed a simple solution and it seems to be a div.3 standard sol
You need 1 DFS to find the smallest edge on a cycle and 1 DFS to recover the path. DSU is not necessary, not even sorting.
https://mirror.codeforces.com/contest/1927/submission/245472637
How to solve E?
A constructive. My solution was (and i guess Mike's one was the same) noticing that iterating on array of sums, elements keep +1 and -1. So we may distribute permutation's numbers this way: first, we fill all elements on positions 0, k, 2k, ... . Second, we fill elements on positions ..., 2k+1, k+1, 1. Repeat while we have empty places in permutation. We fill with numbers starting from N to 1. (look 245191801 if my explanation was messy, the code is quite understandable)
What I did was alternating between values I could "shift" up and down (basically increasing or decreasing by 1) for the initial k elements, so that when a value exits the range sum I can calculate another one that replaces it so that the sum alternates between 2 sum numbers with a difference of 1 between them.
For example if n = 13 and k = 4, I would always first set n as the first element in the permutation and then 1 as the second, then for constructing the initial k elements range I would calculate how many times the previous element that shifts in the same direction of the current element would appear in the resulting permutation, so if I have
13 1 ? ?The next element would be then 9, since 13 would shift down 3 times in total in this permutation:
13 1 ? ? 12 ? ? ? 11 ? ? ? 10For elements that shift up it's the same process, but in this case 1 does shift up only 2 times in total in this permutation:
13 1 ? ? 12 2 ? ? 11 3 ? ? 10So the next number must be 4, at this point you will have:
13 1 9 4 ? ? ? ? ? ? ? ? ?From here is just matter of sliding the range through the array and the next element will be the element that last exited the range increased or decreased by one depending if it shift up or down. So if we were to do this operation for the next 4 elements we would have.
13 1 9 4 12 2 8 5 ? ? ? ? ?One way I use to determine if a number shifts up or down is checking if the position is even or not.
Hope this helps you understand the process behind solving the problem :).
Didn't do as well as I wished, but I enjoyed the problems.
Solution to D: It's easy to compute prefix sums like: If A[i — 1] != A[i] then prefix_sums[i] = prefix_sums[i — 1] + 1 Else prefix_sums[i] = prefix_sums[i — 1]
Then for each query we compute the value: prefix_sums[l — 1] — prefix_sums[r — 1]. If its 0 then obviously there is no pair of different elements so the answer is -1. Else there is a pair with different first element and second element so we take l as the first element in our answer and when prefix_sums[l] is smaller than prefix_sums of some index j (j > l) this means there was a pair of different elements so we just binary search for first j.
how to solve F and G? G looks like n^3 DP.. Don't know how to implement though
G Solution:
Define the dp state to be $$$dp(i, j, k)$$$ which holds the minimum number of paint moves we can make from the first $$$i$$$ cells such that the $$$j$$$'th cell is the leftmost unpainted cell, and the $$$k$$$'th is the rightmost painted cell. Transitions are trivial, and it runs in $$$O(n^3)$$$.
What is the meaning behind these states?
Let's say we perform moves in increasing order of their positions. It's never optimal to paint to the left, if the current moves left painting range doesn't paint the currently leftmost unpainted cell. So, this is why we store the position of this as a parameter in our state.
As for the rightmost painted cell, we store this because some moves cover cells to their right. If the rightmost painted cell $$$k$$$ is $$$> i$$$, then all cells in $$$[i, k]$$$ will already be painted, so its suboptimal to paint to the right if we dont paint beyond $$$k$$$.
245121073
Why is that so? If $$$k$$$ is the rightmost painted cell, doesn't that mean all cells between $$$i$$$ and $$$k$$$ are unpainted?
We perform moves in increasing order of cell position. If cell $$$k$$$ ($$$> i$$$) is the rightmost painted cell when we reach cell $$$i$$$, this means that the cell $$$k$$$ was painted due to us performing a "right paint" move at some cell $$$l$$$. $$$l < i$$$ must hold because of the increasing order restriction. This means that $$$min(n, l + a_l - 1) = k$$$, and we painted the range $$$[l, k]$$$. Since $$$l < i < k$$$, all cells in $$$[i, k]$$$ must be painted.
.Can we do that in O(N^2)? dp(i,j) is the answer for the first i cells such that you don't need to care about the last j cells ( it's already painted by some magic).
F Solution : It's obvious that we check for each edge if it is contained in any cycle. Then take the minimum.
Here's how to find. Sort the edges by descending order of weight. Then using DSU. If u and v are from same component, edge u -> v will be contained in a cycle. Just take the minimum of all edges and do a simple DFS.
Very nice G, thanks for this problem!
Could anyone please explain how to do problem D? Is it a segment tree problem, or there is another way to solve it?
kind of "prefix sums" is the way to go. I iterated thru array, saving last element before ith which is different from ith. (remember: you do not need a segment tree 99% sure UNLESS you have problem in which there both change and ask queries.)
one idea is to pre-calculate the 'nearest distinct' left and right element for every index 'i'
Only calculating distinct rights is enough. Then, for L to R query. check if the right[L] is <= R. If yes then you got your answer at a[L] and a[right[L]]. Else, -1
Consider forming an array $$$s$$$, where $$$s[i]$$$ represents the starting index of $$$i$$$'th segment of input array with all same sequential numbers. Then, for each query binsearch $$$l$$$ and $$$r$$$ in $$$s$$$, to get the segments in which this indecies are located. Let the starting positions of our segments be $$$li$$$ and $$$ri$$$. If $$$li = ri$$$, there is no different elements in this range and the answer should be
-1 -1. In other case, we just take positions $$$ri-1$$$ and $$$r$$$. This will guarantee us to choose two different elements.So for example for input:
1 1 2 1 1This array should be:
0 2 3can you provide a code for the binary search approach
245165324
so distance with vector iterators works in o(1) right ?
yes, O(1) for vectors
u can use mono stack to calculate the nearest greater and smaller element from right for every element then u only need to pick l and nearest greater element for l or l and nearest smaller element than l from right (if possible)
In problem E I saw that we have to make arrange in following way:- at ith pos place x and at i+kth pos place x+1 but how do we implement this? am i thinking in the right way?
if you want just code, heres mine (quite readable i think) 245191801.
thanks mate
Don't want to say it but todays CF Site was crashing so badly, the lag was too much.
Can someone explain why my D submission is getting "Idleness limit exceed"? 245216005
245143604
Segment Tree
Mo's Algorithm
I dont understand why WA on C??? Gosh!!
void sol() {
}
Your code seems to be incomplete hard to tell what's wrong. What is ha? A hashmap?
yep, I use ha[i] to note down whether i has appeared in the a sequence, and then i use the siza/sizb to count the numbers of the elements ranging from 1~k that appeared in the a/b sequence. sizq is the tot number of the appeared 1~k. I think this would work:(
Your code will fail in this test case.
The result comes to NO, I think this is not a hack, I still dont understand why my code will fail:(
You don't update the ha[b[i]] so it may be add to sizq more than once.
For example in this test case your code will assign sizq = 7 but the correct value is 2 so your code will print NO but the correct answer is YES....
to solve this problem only you need to update ha[b[i]]
OH! got it! thank u so much!
Why my solution of D didn't pass , its time complexity was (N^3)*Q , which would be 10^19 operations , which i think can be performed in 5 seconds ?
You could perform around 10^8 operations in a second
OMG
Even if your pc could perform $$$10^9$$$ operations per second, it will be computed in around that many years:
username checks out
Solved F at 20:02 :(
my solution for G:
First I call dp[i][k] is the minimum number of charges we need to painted all cells from 1 to i without using charge in k_th cell
dp[0][k] = 0 (k in range(1 to n)), and I calculate dp from left to right
Suppose that we are considering position i , there are two cases :
*. We using charge in this current cell i:
the answer for this case is min(dp[j][k]) <for j from min(0 , i — a[i]) to i-1 ,and for any k>
this answer contribute to any dp[i][k] with k!= i
*. We not using charge in this current cell i:
The final answer is min(dp[n][k]) with k from 1 to n
This is one of the wonderful div3 rounds ever!
A possible solution for F.
The edge we're looking for is the lightest edge not in the maximum spanning forest.
can u explain your solution for problem F please?
The main idea is that if you put in an edge into a tree then you would create a loop. Try to greedily create a forest using the heavy edges so that you can "put in" the light edge after to create a loop.
Great contest! But unfortunately I struggled with problem F because I wasn't familiar with finding bridges using biconnected components. As a result, I couldn't solve problem G, which required a complexity of $$$O(n^4)$$$ for interval dynamic programming during the contest.
Using DSU to enumerate the minimum edge and reconstruct the entire graph would provide a better approach to determine if a specific edge is not a bridge.
Can anyone give an upper bound on total number of cycles in a graph if number of nodes are 2e5 and edges are also 2e5?
a complete graph on $$$\sqrt {2 \cdot 10^5}$$$ vertices with about $$$2 \cdot 10^5$$$ edges, number of simple cycles will be something like $$$\sqrt{2 \cdot 10^5}!$$$ i guess
And what would be an upper bound on total sum of length of all simple cycles?
every cycle has length $$$\le \sqrt {2 \cdot 10^5}$$$, and the average lenght is $$$\frac{\sqrt {2 \cdot 10^5}}{2} = \sqrt {5 \cdot 10^4}$$$, so i think it will be something like $$$\sqrt {2 \cdot 10^5}! \cdot \sqrt {5 \cdot 10^4}$$$
Got it, thanks.
Problem C sucked.I did a solution with O(k) which K can be min(n,m) and it gave time limit.
I think your solution got TLE because you init a vector of size 1e6 for every test case
That's usually not a problem
Well, it should be, if you have $$$10^4$$$ test cases and in each one you're initializing a vector of size $$$10^6$$$, that's going to be about $$$10^{10}$$$ operations in total. Way too much!
Oops, my bad, there's usually a constraint along the lines of: The sum of k over all test cases does not exceed 2e5, and it seems like that is not the case in problem C
Actually it's not about that constraint at all, even if k = 2 for every test case then his code will still get TLE
In his code, he is using the constant 1e6 to init a vector of that size
downvoted for being correct ?! my condolences
Can G be solved with linear dp in O(n ^ 2)?
Yes it can be just check my submission
are you sure that it's correct?
Well this is something I get know once hacking phase will be finished(cross fingers ) .
hacked.
Can you hack all mine too?
hacked all 3
ok, thanks
Sir, Can you please hack again . I submitted my solution of linear DP with O(n^3) complexity
yes, my submission is O(n^3) but easily optimizable to O(n^2)
can you please explain your idea?
Problems were too easy lol
Code for Problem-B using (PyPy 3.9.10 (7.3.9,64bit)) gives TLE but The same code using (Python — 3) gets Accepted
PYPY -> https://mirror.codeforces.com/contest/1927/submission/245228008
Python3 -> https://mirror.codeforces.com/contest/1927/submission/245231853
It happened during the Contest. Could someone please explain?
The Pypy interpreter is probably copying your answer when you write
ans +=Submitting with list and join at the end gets accepted.
Thanks for sharing the working code. You are correct, after a bit of GOOGLING found this
Python strings are not mutable as in C++, so an operation like s += t for string s and t in a loop creates a new string each time leading to quadratic complexity. So a TLE is the expected result.Was mad triggered yesterday, but now I know something new :)
Problem C has a similar issue:
PYPY 3 TLE — https://mirror.codeforces.com/contest/1927/submission/245369079 Python 3.8 AC — https://mirror.codeforces.com/contest/1927/submission/245369237
I'm not doing += on strings though
You just got lucky that no-one had tried the dictionary TLE hack for python3 (https://mirror.codeforces.com/blog/entry/101817).
didn't know that, thanks
This contest was awesome!
Is this round rated or not ?
It is very nice round for me. I want there to be more such rounds. MarkMirzayanov you made the best platform for coders.
Can't Figure out why my solutions failed in test 34 in G :"
IF anyone may helppp
Thank you for the round, and all youve done for CP. The questions were great, solved 5 out of 7. Hopefully ill expert after this round. ;)
Glad to see you in our city!
I wonder why I was not marked as "qualified" participant. I participated in at least 6 rated rounds, solved at least one problem in each of them and yet this round is not rated for me. Why is that?
Why K is even in E?
Ignore.
Not impossible exactly but not always possible
$$$[1,6,3,2,5,4]$$$ $$$k=3$$$
The constraint was probably put to make it suitable for Div3 E
Can you give example of a impossible case?
$$$n=7$$$ , $$$ k=3$$$
Ahh , now i get it for odd length 2 increase will come consecutively , where in even length +-+-.... will continue.
to make sure equal amount of elements come from each array
One Burger versus many potatoes
If I succesfuly hack a submission made after the contest finished, will the testcase be used for testing later ?
I think this is true.
yes
i liked this round a lot.
Timing! I'm visiting Georgia with a friend next month. That burger indeed looks delicious! Any food/travel suggestions Mike? What's that burger called by the way? The place/ restaurant name?
Mike, please Consider one suggestion. Earlier codeforces was very good in terms of no. of contests per week but now it is becoming close to 1 contest a week. please improve this. we want 3 contests per week atleast....please... this would also increase the participation of many users on Codeforces. Kindly consider this suggestion and do the needfull
The contest was as great as Mike
题目很好，下次继续
C:Choose the Different Ones!
If I don't add 'for(int i=1;i<=k;i++) a[i]=b[i]=0;', I will encounter the error 'Time limit exceeded on test 2'.I am a beginner, and I would like to understand the reasons behind it.Thanks.
Generally, there may be some optimizations from the compiler that can make the code run much faster
In this case, I'm guessing that in the AC version of your code, the compiler doesn't allocate new arrays
aandbfor every test case (It allocates once, then uses them for every test case)And in the TLE version of your code, the compiler does allocate new arrays for every test case
In my opinion, to avoid this kind of issue, you shouldn't do
int a[N],b[N];for every test case, but rather just allocate it once first (Before the while loop), then at each test case, you just need to initialize the arrays, from index 1 to kI got it.Thank you for your guidance.
I have an approach for F but I've been unable to prove/disprove it... Can somebody please help me out?
My idea is to first negate all edges and find the Minimum Spanning Forest using Kruskal's algorithm. After that, I go through the edges with maximum negative weights (i.e. min weight edges of the original graph) and check if both vertices of the edge lie in the same component or not (using the disjoint sets resulting from Kruskal's)
Is this correct? I intuitively feel it's right but I'm unable to mathematically prove this.
You are actually doing the same thing as the approach mentioned here
The proof is based on the idea that if the edge you are adding to a component already has both of its endpoints, then it must be part of a cycle. Since, we want the minimum weight edge to be in a cycle, we go over the edges in decreasing order of their weights.
I solved abcd. I hope to become specialist in this round. Fingers crossed.
I solved abcd and I'm afraid to not become pupils
Wait I have just missed a MikeMirzayanov round?
Problem G was fantastic problem!!!
TestCase for D were really not good. During contest my q*n solution got accepted. And after that someone hacked it. I didn't realise during the contest that what I was coding was q*n, if I would have got TLE, it would have been fairly easy to code up O(q) solution.
try binary search next time,that will give you good luck ^v^
One useless assert case in my code make me unable to AC problem $$$F$$$ :( poor me forget to not check for assert when there is no cycle.
RTE submission
AC submission
What's the approach for G?
is that coffee ?
look at those lemons are so juicy
Hello my friends Since the contest does not have a tutorial yet, I am very curious to know What's in MikeMirzayanov's cup? He is drinking coffee with hamburger!!! Should we use dp or data structures to solve this problem?
Can someone answer for me: why do I get the wrong result in problem F by determining whether the points of an edge are on the same edge-connected component after ordering the edges by their weights?
Here is my code: https://mirror.codeforces.com/contest/1927/submission/245298631
Rating update when ?
For D, we can report the index with the minimum value and the index with the maximum value as a general answer. If the values stored at both these indices are same we report (-1, -1). We can maintain two sparse tables to answer queries in O(1) time (just like range minima queries). Overall time complexity would be O(nlog(n) + q)
There exist a much easier linear time solution using dp.
Let dp[i]:= minimum index j such that j>i and a[i]!=a[j].
Now transitions are
If a[i]!=a[i+1]
dp[i]=i+1
else dp[i]=dp[i+1].
Now to answer each query just check if dp[l]<=r then answer is {l,dp[l]} else {-1,-1}
Yeah bro your approach is great. :)
Mike, I suggest you to taste 'Khinkali', really amazing Georgian dumpling.
who can help me with problem B plz !! i need source code :<<
you can maintain an array b[26] of length 26 for each alphabet a-z and initialize it with 0. This will contain the frequency of the alphabets till now.. for every new a[i] you need to find the first alphabet with the a[i] frequency and add that alphabet to your answer. then you need to increase the frequency for the alphabet in the array b. Doing this for all i 0-n, you will get the required answer. (sorry for bad English. Hope you understand.)
here is my solution for problem B
https://mirror.codeforces.com/contest/1927/submission/245106024
me too barcelona fan.
My first rated competition. I have solve A~F problems. It's a good experience for me.
u funny
whats?
How I envy you! At first, I thought I could solve all A-F too, but my D question was FST because of my carelessness about time complexity.
Oh, in fact, my F has been hacked beacause I used a segment tree and it's to slow/
My solution to problem B was accepted during the contest but now it says "In Queue" why is it?
its going to be judged again against more test cases, its a normal thing
how long until its done testing?
for now its already taking much longer than the usual but you can see the percentage done if you entered the contest page
Too much slow system testing
Yes bro like its taking years.
Maybe it's because there's too much Hacks in the problem D.
Can you please tell me the name of the place you got the burger?
Slowest System Testing in the history of codeforces?
why there is no rating change even after a day of the contest? is this normal or there is something wrong?
There is system testing after the contest. And it will finish in a moment.
but normally system testing takes an hour or something why it is taking so long this time?
why there is no change in rating even though the system testing is done?
seems there are multiple users above 1600 rating so it might be a reason that rating changes is taking time as they are not going to be considered.
Can someone tell me the solution of problem G. After a busy day and solving the first A-F, my mind stop working and I didn't got any ideas for it.
There is an solutions of all tasks here
https://mirror.codeforces.com/blog/entry/125597?locale=en
Can someone Explain F?
The key point is that: How to judge if an edge is in (at least) a cycle.
Firstly, we sort all edges by there weight, descending. And we suppose that there is no edge in a graph.
DSU is also used. At first each vertice's father is their own.
Then, we add the edges to the graph one by one. As we have sorted it, lighter one will be added later. And each time we add an edge to the graph, we use DSU to judge if the two vertices have been belong to the same unit. If not, unite them, or we know that if we add this edge we will build a cycle.
Once we build a cycle, we record this edge. As we sort all edges descending, after we doing this to all of the edges, we will record the lightest edge in a cycle. The edges have less weight than it are not included by cycle so we don't need to consider them.
After this, using dfs to find a cycle. It's easy.
Sorry if my explain is bad.
Thanks Mike, my rating increased a lot
it is hard for me！
Why my rating is decreased although I solved 2 questions(A,C)
Your performance is below that expected for a contestant at your rating
But someone has also solved same questions. Also my rating is less than him and his rank is lower then me
мне пришло письмо от системы что мой код похож с кодами многими другими участиками раунда и что я якобы списал код (задача D). как и говорилось в письме я пишу комментарий.
в моем коде можно увидеть что сперва я писал дерево отрезков и данный код я скопировал у себя тоесть ранее я писал данный код что бы решить задачу в секций EDU(ITMO курс, дерево отрезков часть 1, шаг второй, первая задача) , подумав над решением задачи я не смог разобратся с решением с использованием ДО и решил отвлечься от данной идеи что привело к правильному решению
я уверен что решил эту задачу я сам, поэтому прошу не блокировать мой аккаунт.
I received a message and it states that my solution was same with the some other participants. I have used ideone as I recently changes my browser from "GOOGLE CHROME" to "BRAVE BROWSER" and I didn't change the status public to private. I use many functions so that when the code of others may not be similar to mine but I don't know how my code matched with them. But I am sure I can explain the code that I have written and very confident about it. So, I request to not block my account or penalize my rating. I am very confident that I can explain my every line of code I have written and every method I used.
So, I kindly request to dont block my account and dont give a penalty. I can give my word that again I dont use ideone anymore in my entire life.
thank you
I recently received a message stating that my solution matched with some other participants', likely due to inadvertently leaving my code's status as public on Ideone after switching browsers. Despite this, I am confident in my code's originality and can explain every aspect thoroughly. I kindly ask not to have my account blocked or receive a penalty, as I assure you of my commitment to avoiding similar incidents in the future. Thank you for your understanding.
hello i just got a message from codeforces that my solution matches with my friend.I just want to clarify that we have studied from the same course (https://vimeo.com/channels/demuxwinter21/page:3) offered by a startup named demux academy where we have studied the logic of oredered map and lower bound and discussed similar examples in theroy while being in same class...but now as the startup has been closed i cant share the class videos but we have same notes..so thats why our solution matches somewhat i guess...plz look forward in this matter as it really affects me.
MikeMirzayanov plz consider it
Hello! I recently received a message stating that my solution(E) matches with some others. I can assure you of the originality of the solution and can explain every part. It might be possible that the flow of my solution is similar to others' but as you can see with my account all my codes are my own creation. I kindly request to not block or impose penalty on this account as I really love giving contest here! (Plus My other solutions are good to go; why these are skipped?)
Hi MikeMirzayanov
I am using OnlineGDB common compiler source that why I recieve a cheat submission please help and get rid of this I will keep in mind next time i use that platform
It will release my code to public
thanks
I am my friend ambaliyashovardhan wrote from the same template but it says that they have detected from the plag check. I insist that we have have not done the same code and it has to be a pure coincidence please look into it. I really love giving contests here and i didnt not want to be flagged for this as i can explain each part of the code as it mine and i can strongly say that it is just a complete coincidence. Ill make sure to change the template and all thank you
Why my DFS in F TLE in Test19 https://mirror.codeforces.com/contest/1927/submission/245777873
[contest:923]Recently, I received a notification indicating that my solution matched with another participant’s. This likely occurred because I unintentionally left my code’s status as public on Ideone after switching browsers. However, I want to emphasize that my code is genuinely original, and I can provide a thorough explanation for every aspect of it. I kindly request that my account not be blocked or penalized, as I am committed to avoiding similar incidents in the future. Thank you for your understanding.
Where is my rating?? :(
Why #251324802 gives memory exceeded limit in Problem F
At a glance, I think passing
pathby value (instead of referencing) intosearchPoints()will cause the vector to multiply itself massively in deep recursive calls (specifically if the graph is a very long chain), causing MLE quickly since at worst memory consumption would quadratically rise.Thanks please answer my new query
Why just a dfs gives TLE on Test#35 since in test 35 the answer is 2 66666 that means i just have to find one cycle . https://mirror.codeforces.com/contest/1927/submission/251404664
I'm sorry to bother you, in the round 934(div 2) my rating is abnormal. Specifically, my C problem was missed in testing. I sent a private message for Mike, but it seems he didn't see it. So I published this comment hoping to get attention. I may not be very familiar with the evaluation mechanism of CodeForces. I don't know any other ways to solve that. excuse me, thanks. >_<
hey MikeMirzayanov what is this partial behaviour towards flagging solutions.
This user -> sjy is out of competition for the solution: https://mirror.codeforces.com/contest/1974/submission/261826313 but i also noticed the solution of this user -> frank11_sjy who is not out of the solution even having a very similar solution just variable name changed and some comments added and even submitted later; this is his solution https://mirror.codeforces.com/contest/1974/submission/261825867 the entire nested for loop is same with same indentation. Man he needs to get out of contest, you are doing very wrong and people's trust will reduce from this platform. Please get him out of competition.
This kind of thing happened and I hope 945div3 doesn't give me a rating, but no one seems to care about this game anymore