Hello! Codeforces Round 826 (Div. 3) will start at Oct/11/2022 17:35 (Moscow time). You will be offered 6-8 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.
The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks.
You will be given 6-8 problems and 2 hours and 15 minutes to solve them.
Note that the penalty for the wrong submission in this round is 10 minutes.
Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory 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, then the round will be rated for you.
Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of our work. Problems have been created and written by ITMO University team: MikeMirzayanov, myav, Gol_D, Aris, Gornak40, senjougaharin and Vladosiya.
We would like to thank: Mangooste, Ormlis, oversolver, Be_dos, IzhtskiyTimofey, Stefan2417, ace5, BledDest, AbsurdMan, toxabuk, Kniaz, goncharovmike, YTatarin, pashka and great_fortune for testing the contest and valuable feedback. List of testers will be updated.
Good luck!
UPD: Editorial
As a tester, I will not participate in this round
As a contestant, I will participate for sure.
As a non-tester,I invite everyone to participate in the contest. Good luck
You put Div.3 contest on Tuesday and then Div.4 contest on Thursday... unbelievable. But why?
div. 4 especially for turquoise who will not be able to perform well at the div. 3 and will become green
When you see that one of the problem setter is MikeMirzayanov, the excitement goes on another level ;)
good contest!!
What are the problems?
.
Mom, I am on TV!
Hopefully it’s fun!
As a toaster, I tasted this round
tree!!
If you are over 25 and own a computer, you must try this game
give me the link to downlaod it abto
You are not over 25
you are 15
14* and I don't play this game. I am eagerly waiting for my 25th birthday
if i was on whatsapp i will give you a like
Thanks
sir can you give the hint for the third question of contest how to think for the problem and the basic apporoach should come in our mind it will be greatful if you give me some guidance. Hope for the reply sir thank you
BTW I like the cat in the profile picture of Vladosiya.(◠‿◠)
Me too(^_^)
looks like a dog to me lol :)
Don't make fun of that cute little kitty.
It was a compliment :))
ismail-but-noob I hope we finally reach pupil
:(
Please put strong test cases, I hate to get hacked in div3/4 contests.
Then make stronger solutions?
Best of Luck everyone!Hoping for a positive delta
Glad to see Div. 3 again after a month.
Thanks Vladosiya to arrange a lot of Div3 contest for beginner. Hopefully this contest will be more interesting);
According to the rating was rolled back, so I participate in this round will be rated or not?
As a pupil, I'm hoping for the Specialist in this round
hopefully,I'll become green in this round :)
Best of luck everyone
Me after solving E
Is E really that easy for 2700+ (I am sure it would go above 3000 by the end of the contest) people to solve?
I can't think of anything at this point :')
maybe memoization will help you
Lol 😂 😂 its simple dp problem why r u so dumb
for tourist all problems are easy but for most of people it isn't, i am also too dumb to not able to solve E
Do I need to know dp to be able to solve E ?
It would be much better to solve E with dp. I don't think greedy could solve this problem.
Great contest!Congrats to authors!
Problem E can be solved with DFS.
my solution: 175655607
Am I the only stupid one who was trying to solve C without considering the elements should be next together and wasted half of them time on that
How to solve the problem C?
Brute Force O(n*n*logn)
Note that the sum of each segment needs to be same. So given the total sum as $$$S$$$, we must partition the array into $$$P$$$ segments with sum $$$\frac{S}{P}$$$. Now we can bruteforce by iterating $$$P$$$ from $$$1$$$ to $$$N$$$. (remember to skip when $$$P$$$ cannot divide $$$S$$$)
i did same but still failing, could you please let me know where i was wrong update:- https://codeforces.net/contest/1741/submission/175632745
int main() { int t=1,i,j,k,n,m,q; cin>>t; while(t--) { cin>>n; int mx=0,ans=0,count=0,ans1=INT_MAX; long long totalsum=0; vector v(n); for(i=0;i<n;i++){ cin>>v[i]; totalsum+=v[i]; mx=max(mx,v[i]); } j=n; long long ch,sum=0; while(j>0){ ans=-1; sum=0; if(totalsum%j==0){ ch=totalsum/j; if(mx<=ch){ for(i=0;i<n;i++){ count++; sum+=v[i]; if(sum==ch){ ans=max(ans,count); sum=count=0; } else if(sum>ch){ ans=-1; break; } } if(sum!=0){ ans=-1; } } } if(ans!=-1) ans1=min(ans,ans1); j--; } cout<<ans1<<endl; }
}
Check my submission — 175591036.
Dichotomous answer and O(n^2)check. So it is O(n*n*log(n))
175601238 — $$$O(n\cdot log(n))$$$
Perfect Div.3 round. Congrats.
Great problems! enjoyed D and F the most!
how to solve E ?
You can use DP.
Video Solution explaining the DP Solution.
Define $$$dp[i] = 0/1$$$, if array upto index $$$i$$$ can be completely made using segments i.e. is it encoded valid?
My God ,solved E in the last minute
how to solve E?
https://codeforces.net/blog/entry/107823?#comment-961906
Same for me here, but with F. Got my submission accepted after the contest had already finished. It was tense.
How to solve F can you please explain. Thanks
Not sure I'm gonna be capable of providing a better explanation or solution than the editorial, but here is what I did:
1) I sorted all the segments by their left coordinates (their starts)
2) On the sorted sequence, I grouped all the consecutive segments of the same color
So using this as an example, after my grouping we would have the following array: {{1,3}, {2}, {5}, {4}}
3) I looped through every group of segments and for each segment calculated the smallest distance from it to another segment of a different color, for this I checked two things:
First: The distance of the end of the segment to the start of the first segment on the next group (the segment of a different color with the closest start)
Second: The distance of the start of the segment to the end of the segment of a different color of a previous group (previous group = starts before the current one) with the furthest end
To do the second part you have to always keep track of the furthest end so far, which is easy, but for each segment you want to compare it with another segment of a different color, so you have to keep track of the segment with furthest end so far and the segment with the furthest end that doesn't have the same color as that one, doing that you are good and can always apply the method above to calculate the answer for any segment.
Missed my first Div3 Ak by 30seconds T_T
How to write question E? I have no idea
look carefully , every element of array may/maynot have the potential of being the right/left endpoint indicating the length of a segment so from each element we can have at most 2 probable segments, so we can get highest 2*n segments ,then the problem comes down to figure out whether you can build an array of n elements using some of these segments which are non-intersecting ; you can do that through dfs which I did
For every element just check if it can cover the area to it's left and right. If it covers the area to it's left then update the value of that position (dp[i]) with dp[i-left-1] and if it covers the area to it's right then update the value of dp[i+arr[i]] with dp[i-1]. And check for dp[n] at the end. Here is my submission 175628640
Loved problem G, but failed to implement during contest.
Hi can you please explain your approach of problem F. Thanks
If you want, just have a look at my code. It is very readable. (I just solved it. https://codeforces.net/contest/1741/submission/176072445
Difficulty-wise, which Div3 problem is equivalent to Div2 D?
probably the last one
Yea, I have 75% chance of solving Div2C, never solve Div2D. I never solve Div3F for the past two contests.
F or G
Yea, I have 75% chance of solving Div2C, never solve Div2D. I never solve Div3F for the past two contests.
Was thinking dp for E but each state of my dp has a loop so thought time complexity will be n * n. Saw some solution has passed which have done the same.
you have miscalculated the complexity, it's not n * n
Two nested loops is a naive approach and yeah too slow at O(n^2). But if you think about how updates to your dp table are happening there, you can massage inner loop's updates into the outer loop and have just a single loop for O(n) runtime.
Alternatively think of it as a graph problem, two edges at each index going back/forward, determine if start is connected to the end.
Really cute problem btw with cute simple solution.
problems were cool! thanks to the authors!
Pretty Nice Contest! Btw, what is the test that makes solutions for E fail?
just try setting n to 2e5 and all values to 1.
Yeah, I tried that. I think the only solutions that are hacked that way are the ones with no memorization.
yeah many of them are n*n
Got WA in problem E using memorization during contest.
But just after the contest got AC with the same code only after removing the memorization part
why did it not exceed time limit??
submission
upd: hacked
Felt like was giving ABC, so yeah nice contest ^_^
The cheaters are gonna cheat. There were many videos on YT and many codes where shared among various groups on discord and telegram. This ruins the original rankings and rating of fair participants.
That's Why No of Accepted Submission Increases for Problem C-D
can anybody hack my E ?
your code editing is a little bit ugly
my hand writing was ugly in school too , same goes for my code writing
I use dfs to solve E.But it looks like can be hacked.Can anyone show me the way to hack these solutions?
why do you think it can be hacked?
I have saw some these solutions had been hacked
ok mine is hacked ,forgot to do memoization lol
I did memoization.But may be it can be hacked too.
ok let's find out , can anyone hack this solution of E :
https://codeforces.net/contest/1741/submission/175667416
?
It seems that c++14 is much faster than c++20.May be I will use c++14 the next time.
I wrote a dp solution using python and so far so good, don't really see how it could be hacked...
cool F. Really disappointed about not solving it in time(
Problem Statement of problem C was bad. For literally around 2 hours and 15 minutes I tried to figure out whats wrong with me. To the author of this problem, you could have written subarray instead of segments. For around 2 hours and 15 minutes I just thought I thought about subsequence. I know it was not completely authors mistake. I should have been more careful. But still you should have avoided the confusing words. Rating goes rrrrrrb :(
The statement is perfectly clear, and illustrated with examples. I have also failed to read questions properly in the past and paid the price, but that is not the fault of the author.
F is too easy for its position
Do not agree with that honestly.
Kinda cringe tbh
Yes, clearly.
Maybe you're just too good? Lol. There's only 351 solves atm
Is the contest going to be unrated after this?
https://codeforces.net/blog/entry/107879
Kudos to authors for clear problem statements.
Problem E was a perfect 1D dynamic programming question and the best problem for div3 E.
Overall Great questions. Congrats to authors.
another great contest by these legends
Can someone can give a small hint for D I have enough time but still couldn't make it
you can split the array in 2 parts every time. and you have to check that the elements in first part is always less than second part for every subtree. if not, increase the count and repeat the same process till the leaf of the tree.
Use recursion for solving the problem.
You can take reference from my code-> https://codeforces.net/contest/1741/submission/175603313
Just complementing, recursion is a good path, but also not the only one
In one way, if you know merge sort, you basically know the solution for this problem.
Would recommend you to learn the idea of merge sort from GFG or someplace else and try it on your own.
Just for reference 175631361
Think of divide and conquer technique.
Did anyone else use min cost max flow on G? I think it works in $$$O(km\log m)$$$.
That's insane, do you think you can describe your approach?(I only managed to solved it with bitmasks)
For a vertex $$$v$$$ in the original graph, let there be an entrance node $$$2v-1$$$ and exit node $$$2v$$$ in the flow graph. The source is vertex $$$1$$$ (the entrance node for vertex $$$1$$$). Let $$$2n+1$$$ be the sink. The edges are:
The answer $$$k$$$ plus the minimum cost flow of this graph. (Or maybe I'm wrong and you can hack me.) Stop at $$$k$$$ units of flow instead of a maximum flow because the minimum cost will be reached within $$$k$$$ units. Otherwise, the time complexity is $$$O(nm\log m)$$$, I think.
Sounds nice, if I got it right it is computing the "maximum cost maximum flow" to find out the maximum number of friends that can be driven and then subtract this from K to get the answer. The transitions are also pretty logical, I don't know if I can find any counter-example. Anyway, I would have never thought of modelling it with a flow chart, gg:)
Hi, Can someone help with F? I saw some solutions with segtree, but they were difficult to understand.
Try think this way: there is no colors in this problem, task is the same but without segment colors.
let's assume that the segments are sorted in increasing $$$l$$$. You can split the problem into two parts -
i) find the greatest $$$r[j]$$$ ($$$j$$$ < $$$i$$$) among all $$$l[j]$$$ which are less than $$$l[i]$$$ and with different color than $$$color[i]$$$
ii) find the least $$$l[j]$$$ ($$$j$$$ > $$$i$$$) among all $$$l[j]$$$ greater than $$$l[i]$$$ and with different color than $$$color[i]$$$
Let's see how we can solve the first part. We can store an array $$$mx$$$ where $$$mx[k]$$$ indicates the greatest $$$r$$$ value for a given color $$$k$$$. Store this $$$mx$$$ array in a segment tree so that we can retrieve the maximum value of $$$mx$$$ with updates. Now, for this case, you may wonder why you would actually require a segment tree and not just maintain a set or something similar. The thing is, if we are at the $$$ith$$$ segment, the maximum $$$r$$$ value of any segemnt $$$j$$$ ($$$j$$$ < $$$i$$$) might be of color similar to that of the $$$ith$$$ segment. In which case, we have to find the max $$$r$$$ value of a color which is not that of the $$$ith$$$ segment color. Say the color of the $$$ith$$$ segment is $$$k$$$. We can do this by updating $$$mx[k]$$$ in our segment tree to some very small number and then finding maximum in segment tree and later resetting $$$mx[k]$$$ to what it was initially. Ie make sure that $$$mx[k]$$$ is ignored in our max segment tree.
Now, as we move through all $$$i$$$ in increasing order of $$$l$$$, we can easily figure out the maximum $$$r$$$ value of a different color using our segtree (explained above). Once we find this maximum $$$r$$$, we we can update the answer for this segment to $$$max(0,segment[i].l-max_r)$$$
The second part of our problem can be solved in an almost similar way, except we would require a minimum segtree to find the minimum $$$l$$$ value of a segment $$$j$$$ ($$$j$$$ > $$$i$$$) of different color. Alternatively,we could use the same segment tree (max segment tree) except store values in the segment tree as (-(actual value)), now, the abs of the max value will be the least $$$l$$$ value. Once we find this minimum $$$l$$$, we can update the answer for this segment to $$$max(0,min_l-segment[i].r)$$$ We'd also have to make some minor changes like redefining $$$mx[k]$$$ to minimum $$$l$$$ value for a given color $$$k$$$
submission
Thank you so much!
Awesome round!!! Keep it up creators! ^D
Great round
Someone please hack my submission for E. 175641835
Can someone explain DFS approach to solve problem E.
I think DP solution much easier to understand
But DP idea almost like DFS solution. So let me tell you the DP idea first and then DFS
1) DP solution. Let $$$dp_i$$$ be the True, if the array $$$b[1..i]$$$ can be build by array $$$a$$$ and False otherwise. Our base is $$$dp_0 = True$$$. Then, if $$$dp_{i-1}$$$ is True that means we can build array $$$b[1..i-1]$$$, that we have to do with $$$b_i$$$? Let's say it's the count of numbers in next subarray, we set the $$$dp_i+b_i = 1$$$. And if $$$b_i$$$ was the counter in previous subarray we need to check if we can build array $$$b[1..i-b_i]$$$. The answer is in $$$dp_n$$$ now.
2) DFS solution. Let's now say from index $$$i$$$ we can go to indexes $$$i+b_i$$$ and $$$i-b_i$$$. Because $$$b_i$$$ is count of numbers in next or previous segments. Let's call this edges and $$$i$$$ as nodes. We have to be able to move from node $$$1$$$ to node $$$n$$$. The answer is $$$dfs(1)$$$ or $$$dfs(n)$$$ now.
We can use the visited array to our advantage in the DFS solution, we can simply start DFS from 0 and then check $$$vis[n]$$$ (basically right after the last cell). If the string is valid $$$vis[n]$$$ will be true, otherwise it will be false.
Great problems but weak test cases for E killed me.
Nice contest, thanks! I think d and g are pretty nice.
I was originally kind of annoyed by F but i looked at some other people's submissions after contest and they're pretty cool, so that was mostly my fault for being an idiot.
How to approach D anyone?
Its a MergeSort problem, you just have to keep track of the left and right part for each segment using a 2d array and then on each iteration see if you can merge i and i+1.
Also you can track the first element of the left and right subsegment and swap them if left is greater than right. You don't have to swap the whole array, and this way you get an $$$O(n)$$$ time complexity due to $$$\Sigma_{k=0}^{n-1}{2^k} = 2^n-1$$$ and $$$n$$$ was in the form of $$$2^k$$$. If the absolute difference of the two elements are equal to the difference of the indices for each step, the tree is valid. otherwise the answer is $$$-1$$$
Why E no was with so weak pretest? Forgot to use memorization.
You can survive only by using dp.Memorization is also not enough if you use dfs.
I think your dfs got TLE hacked because the time complexity was $$$O(V^2)$$$ due to scanning for segments on every index. You can enumerate segments beforehand, this will lead to a maximum of $$$2V$$$ edges, and worst time complexity is $$$O(V)$$$ if you do this
Why for E, my dfs + memo got hacked as TLE? https://codeforces.net/contest/1741/submission/175640727 method is called getCanSent the memo map has at most 2n entries.
Well, I can't exactly know where the hack happened. But your code will (and did) work very slow, due to multiple reasons. Reasons may include hash tables being simply slow, and the recursion leading to a deep copy.
Your transition can potentially take O(N) time. And you have N states, so it's actually a O(N^2) solution.
I find G easier than F and I've hacked my friend DitaMirika and another participant ha___il for their carelessness.
detail: Their time complexity can be as large as $$$O(2^n)$$$
Why for E, my dfs + memo got hacked as TLE? https://codeforces.net/contest/1741/submission/175640727
method is called getCanSent
the memo map has at most 2n entries.
F is too hard for me :(
why this 175643343 n^2 solution is passing for problem E?
I tried to submit it again and it is giving TLE now but in standings it is an accepted solution even after system testing :(
SysTests aren't done yet as far as I know. Been looking for hacks and Systests didn't go off since hacking phase ended, it probably will start soon.
Oh yes, my bad. That solution will get caught in system tests then.
when will system test start?
Most likely soon, maybe an hour or two later at most. As far as I have seen, it doesn't take much longer usually.
Usually its written there that "system test pending". but its not the case for now.
I have noticed it in previous rounds with hacking phases as well. In Div2/1/Global rounds it gets 'Pending' status but not in the Div3/4/edu as far as I have noticed. It might change a minute or two before the SysTests start, but it's marked as completed mostly.
Hey i can only message 1 time in 10 minutes. but it looks like this is not the case for you why?? and i think some things should be common in all the contest not like this happens in this that happens in that
I guess because you got -73 contribution, so CF is trying to revoke your 'privileges'.
Well, it def should be, but I guess there are some technical difficulties, like this one isn't pending in SysTests yet, but analyzing hacks to add in SysTests. Once it's analyzed, it will be SysTested. I definitely am not the best person to ask this to, but this might be the case.
If my interpretation of this experience is correct, it's definitely not a direct correspondence to contribution. I believe it is some "rate limit" happening, sometimes it goes to 4 messages every 60 minutes. Getting it down to 4/60 had nothing to do with contribution for me though.
May I ask whether I would be rated for this round or not? By the rules stated in the announcement, I am not a trusted participant yet(since I took < 5 rated rounds). But according to this line "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.", I assume I should be rated for this round. Thanks in advance to your answers
As far as I know, it should be rated for you.
But it appears in the unrated contests in my profile page haha
It's because the rating changes isn't out yet, so it's marked as unrated for everyone yet. It probably will take a few more hours to update.
Does hacks improve delta in div3/div4/educational round ? if yes, how ?
As far as I know, in Edu Div2 rounds you get +100 points for successful hack and -50 for unsuccessful. So yes, in Edu Div2 you improve your score.
In Div3/4 I don't think that is the case, since it's not based on scores but amount of solved problems.
EDIT:
Well, I guess I messed up with Div2 edu and standard Div2 round, but downvoting instead of correcting and answering the question isn't really helping a lot.
How do people target solutions for hacking? Is it random?(just look at people's solutions and try to find vulnerabilities) or it there some other way?
I think they find a general case which might hack some of the approaches, then check for that specific problem if it's implemented via the approach you know how to hack. Not certainly sure tho.
Yesterdays contest was good Though I am going to get a negative But it was fun :) :) :) :)
As a Competitor, I competed this round.
My rating is 935 and i participated in Codeforces Round #826 (Div. 3) but its showing unrated for me and i haven't got any ratings. Can anyone please help me out because in notice its also written that " 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."
Ratings didn't update yet, so it's marked unrated until SysTests finishes. Once SysTests will be finished, ratings will be calculated, updated and then marked as rated.
The ratings haven't changed yet, so it shows unrated for everyone.
My rating has still not changed yet, is it not updated for everyone or is it only me.
Wait for sometime it will be update for sure
As a newbie, I tried to implement the bitmask idea in problem G but fail in test 3.
I am really desperate. Would you please debug it?
https://codeforces.net/contest/1741/submission/175747503
Codeforces Language Picker -- chrome extension to fix codeforces language picker.
hi can anyone tell me what's wrong with my approach for the e problem, i have written a recursive dp code for that . https://codeforces.net/contest/1741/submission/175681998
Take a look at Ticket 16315 from CF Stress for a counter example.
thank you
When ratings will be updated?
When will the rating points will be added to our accounts? Thanks.
Why the rating not update yet ???
Is it just me or you think it's taking more than usual for ratings to change ?
My rating has not changed after this contest . Any reason why ?
waiting for the updated rating
MikeMirzayanov Vladosiya senjougaharin
I am sorry for commenting this , but my solutions were skipped because I used a code that was published on geeksforgeeks from 2 months ago , and the code is found in my template , used it with some modification to solve C , and it wasn't the first time to use the same code to solve similar problems during practice
link of this code
link of my submission
Using reference code for template and directly copy pasting solutions are different bro. I don't think your punishment should be rolled back. Even it is a common problem you are supposed to do at least the solve part by yourself.
as i mentioned bro, these functions in my template are the ones that i learn during practice, i didnt say that i copy paste solutions, i only use functions from my template if i wrote it before, or i write a new one and add it to my template, i dont see that both functions(from the webstie and the one in my template) are the same 100%, i did the modification for this problem, but when i add it to my template i add the non-modified one
I know you are not a cheater. Mike can consider your case specially if he has that much time. But in general most of the cheaters would give this excuse that code was already public on many sites bla bla... Plagiarism checker is only run over the codes that are submitted in contest time. So not in this contest but also in big contests like OI or others if you get caught for this reason I don't think you would be forgiven. So practise to code yourself even if the whole code for the problem already exists!!
When will the rating update?
Cheaters are being caught now, so should be fairly soon, within the hour is my guess.
When will the ratings roll out? :(
not today
how do you know ?
well, last my div3 round rating update was after 2 days. They are searching cheaters as far as I know
why Div 3 unrated Until now
Why it is taking to much time to update ratings?
It is better if more time is needed to update the ratings. My rank for this contest has been steadily rising due to the removal of cheaters.
Rating is now updated! Congratulations to myself
dlt
Nice job!
Why are Common Standing Seat and Rating Changes seat different? Example- Common standing 3600 Rating changes 4300
Common Standings include only trusted participants, whereas there are more rated participants than that
Can someone tell me why this code Time limit exceeded on test 40? https://codeforces.net/contest/1741/submission/176144895