Hello! Codeforces Round 874 (Div. 3) will start at May/19/2023 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, Aris, Gornak40, senjougaharin and Vladosiya.
We would like to thank: pavlekn, KoT_OsKaR, natalina, vladmart, Phantom_Performer, Be_dos, ctraxxd, diskoteka, lunchbox, kzyKT, MODDI, molney, FEDIKUS, Nickir, 74TrAkToR, kamishogun, KseniaShk, Sokol080808, NintsiChkhaidze, Asad5059, heon for testing the contest and valuable feedback. List of testers will be updated.
Good luck!
UPD: Editorial
Hoping for the delta ++ ^..^
hey, your cat is looking at the blog's contribution.
And your pony is looking for the negative contribution.
Hoping for positive delta
But the contest isn't rating for you. :/
Finally, an unrated div3 for me!
For me too
XDD, so true
wishing a good div for one piece fans
haha, I couldn't solve D and E but F was pretty easy. Hoping +ve delta
Can you give me a hint?
For problem F
here are few observations, 1. Since we can only choose dancers with different levels and exactly m dancers with each pairwise dancers level difference be be strictly less than m.
First, Sort the array then store count of each different level dancer, second, use unique of array to get only unique level dancers, then iterate over it now for dancer i with ai level can be paired with dancers having level less than ai+m, so in the same array look if i+m-1 < n and a[i+m-1]-a[i] <m , n is the unique dancers, and if above condition is true then we can have all pairs that exist from number of dancers of a[i] level * number of dancers with a[i+1] level uptill number of dancers with a[i+m-1] level this can be achieved by using prefix product array.
hope this help, my submission
nice, thanks bro. I thought that the difference was between each 2 adjacent numbers in the subsequence idk why
As a tester, i'm highly recommend to participate in this round. I think, one of the best div.3 round.
In my opinion every round goes good but when some unrated participants make fake id's and participate in the contest, the contest is ruined for programmers like us i hope we don't face any external problem in this contest .Good luck to all!!
Please provide hints and proofs for the problems along with editorials It helps in upsolving and understanding concepts for beginners instead of directly jumping to solutions :)
hope to be a wonderful round and end up with a big postive delta:)
if i do not register for contest and do not solve any single sum, can i still hack others solutions ? And will there be any rating decrease for unsuccessful hacks if i dont give the contest ?
yes and no
Div3 or educational round has no hacking points.You can hack any other solutions. See for details Hacking GUID
As a tester, I would highly recommend this round! The problems are very interesting with neat solutions! Statements are also pretty short!
Short statements. Sounds Good!!
"Statements are short", Visible Happiness
who is MikeMirzayanov? CF community tell me about the living legend.
who is Mike Mirzayanov
Hoping for a smooth contest and great problems.
As a tester, I would suggest participating in the contest :) Problems are cool and challenging.
Feeling this will be an hard round
As AI Bard, I will be participating in this round. Hey newbies, it would be a shame if you lose to Bard.
LLMs aren't aimed to humiliate others including newbies. You ain't one.
FREEDOM! I will give, if no one before.
P.S: what we do is erasing 'L' in 'LLM' and inserting instead 'G'.
How to lose to someone who has not solved a single problem and have 3 incorrect submissions in a contest?
XD
Hoping for a balanced and interesting problemset :)
Hoping for no cheats :{
how ironic
Hoping to score a chance to AK this competition!
nice contest
If you want to watch me spending 15 minutes on problem D, here is a screencast. (It is unable to be viewed until the end of the round.)
div4 or div3 contest?
3.5
Really good contest to return to Codeforces after a month of exams! Looks like it will also take me back to specialist :) I didn't have time to do F, was it some nCr + binary search?
Not really (at least not my solution). The observation was that since the difference between any two levels is strictly less than m, then the selected dancers must form a permutation of [a, a+1, ..., a+m-1] for some a. I just did a sliding window with modular inverse on each contiguous range with length greater than or equal to m, using a map to keep track of occurrences.
Hm, my initial idea was to sort the array and binary search the greatest possible value that could be included and then add how many ways you could choose m-2 numbers from the set of numbers between the first number and the greater number to the asnwer.
Similar here. But I sorted the array, remove duplicates then do sliding window of size m.
Same here. Except for I didn't have time to write modular inverse:(( Would've become expert. Here's my submission: 206546474
i just made the logic quickly that i have to cnt the frequency and store in the vector of pair but i couldn't remember i have to change size also i was looping for n all the time after 40 minutes I realized then suddenly change the size and submitted at the last sec then realized didn't comment the extra printing variables and then contest is over and submitted after a sec of the contest and accepted :)
Am i the only one who struggled with recursion in E?
I did a simple DFS + handshaking lemma to make for easy counting
How did you use the handshaking lemma. Isn't this lemma for undirected graphs?
I'm not really sure, I just observed that any component with edges equal to vertices must be counted. So I just used DFS and added the size of the adjacency list of each node visited then divided by 2 to check if edges equaled vertices visited.
how to find the minimum no in the problem is you can explain some thing
Recursion? I did it with DSU.
at first i used some kind of DFS but it didn't pass because of max recursion depth i suppose
Nope, I did a simple DFS to count the total components and the cyclic components.
Submission link
Of course you didn't have a such problem cause you've solved it using c++. Im using python which has a very restricted max depth of recursion and therefore i couldn't solve it the way you solved.
I think a good solution to your problem would be switching to C++ :)
It's not a problem, i don't care about my rating anymore. Besides, almost problems that i saw on cf are solvable by python (including this problem) so it's definitely not a big deal
lmao gonna lose some rating because I didn't even check restrictions of D for quite a while
Same, I really tried to force an O(n) with casework until I just gave up and bruteforced every array starting with the best possible number.
How to do D?
For permutations starting with the max number, you can generate all possible arrays starting with max-1 in n^2 time. For permutations not starting with the max, you can generate all possible arrays starting with the max in n^2 time. Then just sort all the arrays you generated.
You always want to keep the highest integer at the start. Since it's permutation, you only care about putting the highest as left as possible, because otherwise a lesser number will be placed to its left and will result in a lexicographically smaller array.
To do this, you should find the highest element and that's n. If n is the first in the array, you can't keep it there, so you should try to solve it for n-1.
If it's not the first,(Let r be the index before n) you try every [l, r] for every 0<=l<=r and pick the lexicographically biggest from that.
I didn't realized the restriction of D is small until I saw your comment lmao. Luckily it didn't take me too much to come up with a $$$O(n)$$$ solution.
I had some kind of solution for O(n) but it received runtime. Not sure why, will check that later, but damn, it took me hella time to notice that.
Yep, I am even not sure currently what would O(n^2) solution for D look like. I noticed that in starting but all my intutions were just suggesting O(n) solution.
Does anyone's code for F was failing on test case 4 ?
Yep, it was because of integer overflow for my case.
Can you help me in debugging mine ?
I think you got it :)
Yupp thanks :)
I couldn't implement it, but is this idea correct for E?
a = # of connected components, b = # of cycles
Get the number of connected components and if it is a cycle then b++.
so if a == b min and max value is same, otherwise min = b + 1, max = b + a.
Plz confirm this, thx.
Almost correct. (I made a similar mistake). Cycles of length 2 can be merged with each other. To be fair, it wasn't very clear from the statement and you had to have implemented it incorrectly to see the mistake.
You find cycles which have >= 3 vertices. Yes, A is the number of connected components, it's true. B is the number of cycles (>= 3) and if you have some vertices which are not in these cycles B++.
Another way is to count the number of components where the number of edges is equal to the number of vertices. I noticed the pattern quickly because it felt similar to a USACO silver problem I had seen before.
Yes I forgot to mention that the size of cycle should be >= 3. Should I find a and b by union-find?
Union-find is a perfect fit for finding cycles in this graph!
max should be just a instead of b + a (because otherwise you would count every connected component that is a cycle twice) , but your idea is correct if we disregard this small mistake.
That is true. I appreciate your helpful comment!
I use DFS to find the connected components, which is the maximum value.
A connected component is a cycle if every person in it knows two neighbors.
The minimum value will be the number of cycles, plus 1 if there is at least 1 connected component (which is not a cycle), since all of them must be connected into a cycle.
206539377
Problem D was so MESSY for me, but maybe I'm just stupid
I do think that D and E are super hard to implement.
D is purely an implementation problem I guess. E was not that hard to implement, if you use some DSU implementation. (Assuming DSU implementation is directly available).
Implementation without DSU is relatively easy. Here you can check out mine 206530050
I think that implementation wasn't hard at all, but in D maybe just many cases and small things to think of was hard to handle for me.
E absolutely easy to implement — just straightforward DFS.
the $$$O(n)$$$ solution is really short and neat if you think it out on a piece of paper first
Please explain me someone why i can't solve fast easier problems like D, but i solve G in 15mins
can someone tell me how to find min no. of dance round in E ??
Connect each pair of dancers with a DSU and count the number of connected components. Notice that, for every connected component, if there exists at least one dancer that does not know both of its partners, it can be merged with another connected component.
Thank you for the great contest. Really liked problem E and F. Although, I got 2 mins late while submitting F. I guess F was easier than E. It was just a combination of binary search and segment tree.
if you used segtree you super over over killed it
That was the first thing that came to my mind. I wanted product of frequencies in range [l, r]. There must be some easier way. But it was fastest for me (as I have segment tree template).
You can use a prefix product array since the array is static :)
You don't even have to do that. Just maintain the product as you traverse with a window
Why not just do a prefix multiplication with modular inverse?
I'm maintaining a 2 pointer approach with unique array elements and map for frequencies.
Can someone tell me what's wrong with below code? Instead of division, I'm multiplying with modInverse. It is working without modular operations for given testcase in question.
yep, preprocess with sliding window after sorting them.
STLforces
Waiting for editorials^_^
lol for D, N<=2000. I noticed it but somehow continued trying O(N) solution and I don't know why...
D is doable in O(n).
Exactly, but after getting the necessary observations to solve D, my brain automatically forgot about N<=2000 and tried doing O(n) since it was doable (and I was too lazy to impl it so I went to E instead).
Can you share some insight on how to solve D in O(N) instead of O(N^2)?
Suppose a[0] != n (otherwise we can do something similar with n-1). Let i denote the index of n in the permutation. We want n to appear at the beginning, so we need to choose a segment ending at i-1. We must include the suffix starting at index i.
We need to include index i-1 in the segment, so the new permutation is [n, a[i+1], ..., a[n-1], a[i-1], a[i-2], ..., a[j], a[0], a[1], ..., a[j-1]], for some index j. (Obtained by reversing indices j through i-1). To determine whether to extend the segment to index i-2, compare a[i-2] to a[0]. If greater, it's better to include it because otherwise a[0] would necessarily come afterward, which is smaller. Otherwise we should stop the segment and append the prefix (since we care about lexicographical maximality). If we extended the segment, we compare again for index i-3, and so on until a[j] < a[0] at which point it is optimal to end the segment. This takes O(n) time and it's not hard to see that it produces the correct answer.
Note that if n is the last element in the permutation, we can also reverse the whole permutation, so we should take that into account. Also, you are allowed in this case to move n in front of all other elements.
Thank you for sharing!
It's possible but it's tricky due to the edge cases that arise from the fact that empty prefixes and suffixes are allowed, but the middle portion (that is reversed) must be nonempty. I'd definitely recommend the more brute-force O(N^2) solution instead: faster to code up and less chance of errors.
Fortunately, the sample input contained a lot of the tricky cases already.
I don't think my solution was really tricky.
206488860
That's a nice solution but I think it's still quite tricky with all the conditionals. Honestly I think that's more complicated than the O(N) solutions to problems E, F, and G.
By the way, I'm not sure if you know that Python compares lists lexicographically by default, so instead of this:
You could write this:
Except there seems to be a weird edge case for N=1, where you construct a1=[1,1] and a2=[1], so you need to handle that somehow.
Yeah, I feel like it is solvable in O(N) but all the case work just make it not easy to organize, then I noticed the problem constraint allows O(N^2) solution.
someone please help me with problem D?
First let's say maximum element={n if a[0]=n else n-1} Let indexMaxi=index of maximum element. fix r once as indexMaxi and once as indexMaxi-1. iterate over all l and choose the best answer. O(n^2) simple ,for O(n) you have to consider cases (I was getting frustated figuring out each edge case)... Solution
why are we considering two indexMax? what's the intuition ?
One case is that when the maximum element which is n is not on the index 0.In that case you can bring n to index 0.The other case is that when n is on the index 0.Then whatever operation you perform n can't remain on index 0.So then we will bring n-1.Instead of doing casework for the 2 cases separately,we check both and take the best answer.Hope it helps.
solved E after contest finishes. using simple dfs and some edges cases
D consumed lot of time for me:(
Vladosiya problems E and F were in the wrong order in my opinion because problem E is converted to a graph problem and requires graph knowledge which is harder than a brute force problem. (You have to convert it to graph and solve it) but F was very easy. In the last hour of the contest i read task E and got stuck on it, but in the last 10 minutes i read F and solved it in less than a minute but i wasn't able to code it in 10 mins and i upsovled it 10 mins after the contest ends:(
I feel like E was more classic, I thought of the solution almost instantly due to studying some USACO this year. Granted I only had 20 minutes for F and I believe I saw the idea, but I couldn't put together a solution for it in time.
Yeah USACO has some graph problems like problem E in many silver and gold divisions
My solution for F was failing for test 3 and I cant understand why. I was using long long so I dont think it should be because of overflow. My idea was to maintain maintain the count of dancers with some value v , sort this and do a sliding windown to find m consecutive numbers. Maintain their product. Use modular inverse for division. Would have become ab expert had this not happened :< .
You were trying to access out of bound, there will be less than n elements in your vector v incase of duplicates.
Can somebody explain how to take care of pairwise distinct in problem F?
you can group the same number together and maintain their frequency to count how many ways
you just need m consecutive values.
I forgot to handle the special case of n=1 in Problem D, causing me to get it wrong 5 times.
LOL...n = 1 is even in the sample test!!
Actually, I couldn't understand the statement of problem E, even after about 3 and 4 times reading. However, I figured out the solution only by drawing the graph of all test cases and guess. A bit lucky for me.
Hello Everyone, In problem G, in am trying to use queue and traverse along minimum indegree to it's parent and find answer accordingly and update the queue, but somehow i am getting WA , here is link to my submission , any help will be appreciated.
Why many Java solutions of B are getting hacked? What's the tc?
I guess because Arrays.sort() on primitive type array in Java has a known performance bottleneck and will TLE. A corresponding wrapper class should be used instead. At least my own solution was hacked because of that, sadly :(
Can you elaborate? What's the known performance problem? Isn't it O(N log N) as one would reasonably expect?
e.g. https://codeforces.me/blog/entry/7108 — in Java, if array is of primitive type, then Arrays.sort() will perform a quick sort under the hood, which is n^2 in the worst case for arrays that are almost sorted.
it is stable nlogn only from java 14
i hacked 134 submissions, where 133 was java sort error.
For those who are interested in the solution for the problems of this round, feel free to check out my video of me solving and explaining them :)
Why O(n^3) solutions in D got accepted
Because the maximum $$$n$$$, 2,000, is not very large. A naive solution for D, which constructs each possible flipped permutation and compares it to the maximum found so far, will use around $$$n^3/2$$$ operations to construct the permutations, but each operation is quite simple, just a 32-bit load and store, if you use
ints to store the permutation. If the compiler can optimize by chunking these together into 128-bit loads and stores, this means you have to do just 1 billion of these operations in 1 second, which is possible.do you mean it is possible in just codeforces compiler not in local compiler?
No, it could also be possible on your local computer, if it's not too slow.
I got stuck on problem G in test 3 (I passed 157 test cases on it), but I don't understand my mistake. I used BFS, and I know the other idea of DFS, but I want to understand what went wrong with my BFS implementation.
Here is the link to my code submission : https://codeforces.me/contest/1833/submission/206574785
Could anyone please help me?
Just come back after a year, better creating a new acc for the fresh start!
A very interesting contest. I've solved 2 problems for the first time!!. Lets go!!
Could someone help me solve problem of my code for C problem. I got TLE on test 11,which n is 2000000 but the another 2000000 is passed in less tham 100 ms. Thanks.
My idea is to anlysis whether this number can become odd or even num by a_i-a_j,so I sorted the array to reduce the time using.And if allow num can be odd or even output yes,either no.
Since there can be up to 200,000 array elements, it's probably too slow to do another pass through the array for each element to determine whether there is a smaller odd element. It would be faster to reorganize the parity checking so that you know this immediately.
Thanks for your reply. ❀❀❀
Can someone help me solve the B problem? Sorting the b array directly using Arrays. sort() will timeout, but shuffling the b array and sorting will not timeout. AC code: https://codeforces.me/contest/1833/submission/206582027 TLE code: https://codeforces.me/contest/1833/submission/206582200
Reason
Problem F is fantastic
Can anyone share your approach for G?
When will the ranking points update (sorry i'm new here)
Just wait.It will be updated in several hours.
Tutorial?
why is it so, my answer was accepted yesterday and today they are in queue ??
It is called system testing which occurs after hacking phase in div3s is completed and the submissions are rejudged with the new added testcases
Nice contest. Was able to solve till D. Can someone explain me problem E? I didn't understand the samples for minimum round of dances.
If there is group A-B-C-D-A, it can't be minimized. But if you have E-F, G-H, I-J, you can connect them into one group. Each dancer may have 1 or 2 partners, no other variants, so you can count dancers with 2 partners and with 1 partner. Those with 1 partner may be minimized:
please add the rank list in the blog :'(
There are WhatsApp groups available that offer solutions to contest problems while the contests are ongoing. Please get them blocked if possible.
said a man with a lot of skipped solutions : )
Said a man who is probably already a part of that group. Btw all the skipped solutions are from only 2 contests that too from first 10 contests. I have already given more than 100contets now. So plz shut up. Spend your time doing something valuable.
Is it rated?
I just received an email tells that my solution is matched with another solution.
I have another account which has rate 1700 (Div3 is unrated to it), So when i solved the problems in this account, i just submit the solution from my other account (and its not rated to it).
Should System Skip my participation in this case? If not, Can you let this round be rated for me, I don't think that i made rules violation at all.
System
MikeMirzayanov
This is my other account Ismail_Alrifai
my submission from this account 206533710
my submission from other account 206536131
1833F - Ira and Flamenco
Codeforces Round 874 (Div. 3)
Thank you.
your solution is getting judged even you are rated or not .
All the questions in this round were simple enough for plagiarism to occur, it's so stupid to impose plagiarism for A and B. My solutions have been found similar to someone, that's totally possible because of the simplicity of questions. I obviously did all those questions by myself and there is no sharing involved at all. I request to give me back my rating changes.