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, SmartCoder, KoT_OsKaR, LoveWX, MADE_IN_HEAVEN, dan_dolmatov, JuanDav111__, 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
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
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.
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)
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.
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
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
Damn that Burger looks good!
what a juicy burger in this morning i woke up
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.
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.
As a Tester, I really like this round and recommend to participate. Happy Spring Festival!
My first unrated Div3
pedrolino GOAT
❤️
Calling specialist.I need 14 point.
1400 — 1386 = 14
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.
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
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!
Eden Hazard round.
Burgerrr reference? Chelsea fan?
Football fan.
No one could stop me from eating a burger when coding!
Waiting to finish my round the next Div.3 round MikeMirzayanov
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!?
Delayforces again :(
delay:<
why delayed
Nah, I'd win.
delayForces
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
Good contest, Good Problems.
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
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$$$
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 \lt 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 \gt = l$$$ answer is $$$[nxt_r, r]$$$ , otherwise answer is $$$[-1,-1]$$$
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
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
:<(
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.
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
How to solve E?
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 :).
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 $$$ \gt 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$$$ ($$$ \gt 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 \lt 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 \lt i \lt 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?
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
Don't want to say it but todays CF Site was crashing so badly, the lag was too much.
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
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?
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).
This contest was awesome!
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. ;)
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
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.
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 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.
Wait I have just missed a MikeMirzayanov round?
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.
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?
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
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/
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.
why there is no change in rating even though the system testing is done?
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
Why my DFS in F TLE in Test19 https://mirror.codeforces.com/contest/1927/submission/245777873
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.