Hej, Codeforces!
mesanu, SlavicG and I are very excited to invite you to Codeforces Round 937 (Div. 4)! It starts on Mar/28/2024 17:45 (Moscow time).
The format of the event will be identical to Div. 3 rounds:
- 5-8 tasks;
- ICPC rules with a penalty of 10 minutes for an incorrect submission;
- 12-hour phase of open hacks after the end of the round (hacks do not give additional points)
- after the end of the open hacking phase, all solutions will be tested on the updated set of tests, and the ratings recalculated
- by default, only "trusted" participants are shown in the results table (but the rating will be recalculated for all with initial ratings less than 1400 or you are an unrated participant/newcomer).
We urge participants whose rating is 1400+ not to register new accounts for the purpose of narcissism but to take part unofficially. Please do not spoil the contest for the official participants.
Only trusted participants of the fourth division will be included in the official standings table. This is a forced measure for combating unsporting behavior. To qualify as a trusted participant of the fourth 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 1400 or higher in the rating.
Regardless of whether you are a trusted participant of the fourth division or not, if your rating is less than 1400 (or you are a newcomer/unrated), then the round will be rated for you.
Thanks a lot to the testers: erekle, vladmart, nika-skybytska, Vladosiya, KrowSavcik, Dominater069, LucaLucaM, MADE_IN_HEAVEN, tvladm, nor.
We suggest reading all of the problems and hope you will find them interesting. Good luck!
UPD: The round is delayed by 10 minutes: https://mirror.codeforces.com/blog/entry/127616?#comment-1133556.
UPD: The editorial is posted!
i wish i could solve all problems glhf
Why no green/cyan testers in Div4 round?
Hope everything goes OK!
Ramadan Kareem
Ramadan Mubarak
Div 4 : The format of the event will be identical to Div. 3 rounds Div 3 : The format of the event will be identical to Edu rounds Edu rounds: The format of the event will be identical to Icpc rules
Is that a recursion?
Hope it isn't a div2.5 as last time
Ladies and gentlemen, finally I can say what I've always wanted to say at Div. 4 rounds announcements: My first unrated contest :")
Same
Hope the next Div. 4 will unrated for me after this one...
finally same >.<
so happy about it
please be a div 4 contest for div 4 people
Hopefully, My last rated div4
Boy, You have made it
Yes bro, but I was sad as I was unable to do some doable problems
Hope efforts pay and this will be my last rated div 4
You have made it man. Tadaaaa
Yes Bro finally
Hope to become Pupil with this contest :D
Solve more problems with less penalty
Managed to solve 4 without penalty today
and -6 on Q-E :)
Nice, keep practicing. I got 5 wrong submission, and all are on test 1. -.-
where are "one refresh costed me 10 minutes" comments?
Sorry, but I'm moving the round 10 minutes forward. The training session was very cool and long. I'm running to you from the gym!
sigma
The contest is delayed?
hoping this is not april fools now.
Hey guys, anyone have the problems for this div 4 so I can practice beforehand?
GUYS I WAS JOKING HOW YALL HAVE THIS HORRIBLE SENSE OF HUMOR
queueforces ?
queueforces this happens every first 10 minutes of a div4/div3 man
Seems like div5
I want to be your student
nice problem set , thanks to the authors
It's fun that due to the long queueforces (and my own laziness to open a proper local IDE) I would actually submit all problems in blind and fix them accordingly after every CE/WA/RTE/TLE/MLE...
ABC is ABC, not much to say. I do feel satisfied with a clean 1-hit blind AC on B.
D is okay, the core concept reminds me of a certain problem in a Div3/Div4 (I couldn't remember) a few rounds prior, cool for newbies to practice this approach.
E is... meh. Just a personal take from a higher tier contestant, I get why it's here but I can't really praise it much.
F is a bit lesser so than E due to the fact one would actually think a bit first.
G is cool. The strings killed me and ruined my flawless AK though, but that was on me being careless.
ABC: Do what you are told to.
D: Can we answer each test case in $$$\mathcal{O}(1)$$$?.
E: Imagine a string of $$$n$$$ characters
aaa...a. How many ways can you divide it into equal parts?F: There is a strict relationship between $$$a$$$ and $$$c$$$ in a valid tree.
G: Have you ever tried solving the classic Travelling Salesman Problem?
How to do F in one line
cout << (a != c — 1 ? — 1 : ceil(log2(c)) + (b — ((1 << (int) ceil(log2(c))) — c) + c — 1) / c) << '\n';
Looks pretty weird but got AC by the way =))
can you explain furtherly the thought process behind that?
Basically the construction idea is identical to the editorial, so you should read it first. I will summarize a little bit.
If a does not equal to c — 1, then there is no answer. Otherwise, we will build a full binary tree from top to bottom, using the nodes 2 and nodes 1. The height of this tree is p = ceil(log2(c)). After that we will calculate the number of "missing" nodes in the last level of the tree. It will be $$$2^p - c$$$. Finally, we will add the nodes 1 into the last level of the tree, level by level, as it will minimize the height of the tree.
Fast tutorial
do I have to participate in 5 contests to receive a rating? do all 5 contests have to be div.4??
Just 5 contests, the division does not matter
A -> just do what is asked ( i had 1 wrong submission in it, forgot take input a , b , c ;( )
B -> just do what is asked pattern printing
C -> standard question leetcode style
D -> here i generated all the possible product possible, then counted whether they exist in my set or not
E -> string hashing to check wether string are equal or not ( wasted lot of time in implementing string hasing i am stupid )
F -> ran out of time
G -> ran out of time
I don't think hashing is necessary to solve E
that's the reason I am stupid
You don't need string hashing in problem E.
The idea is
You just need to check lengths that are divisors of n (This will be a
O(sqrt(n))loop).Now for each of the length, it will be a linear
O(n)check to see if it's valid (I will leave the logic for you to think about...)The total time complexity is
O(n * sqrt(n))Bro thinks he's a red coder
does it matter, if i am red coder or not, if I share my thought process in comments
dont get offended kid
Why does these 253813411 gets tle even though it looks to me as O(n*2^n)
It seems like you are trying all possible routes, which I'm afraid would be $$$\mathcal{O}(n!)$$$.
Thanks for your reply,but why does the initution fail that at every vertex we have two possibilities either to take it in our path or avoid it hence total 2^n operations in recursion
Not quite. Assuming a complete graph of $$$n$$$ vertices, your DFS would function something like this:
dfs(1,0)->dfs(2,1)-> ... ->dfs(n-2,n-3)->dfs(n-1,n-2)->dfs(n,n-1)->dfs(n-1,n-2)->dfs(n-2,n-3)->dfs(n, n-2)-> ....You could guess it. It goes back to
nagain, but from a different parent, to seek a different path.Your intuition neglected a fact that ordering also matters here, and assuming a full path is required always, each path will be a permutation of those $$$n$$$ vertices, implying the actual order in the path.
Thank you very much!
Can you give a hack idea please 253831864
Hacked.
Correct answer should be
1, as we should only remove song15, and has the playlist in this order:16 1 2 3 4 ... 13 14However your solution would be too busy counting all the paths from
3to14, which is about $$$12! = 479001600$$$ cases at least.Cam ơn rat nhieu :)
I'm surprised you actually showed your appreciation in my native language.
आपका स्वागत है।
wholesomeforces
Good competition! Thanks flamestorm,mesanu, SlavicG, and the testers :)
interesting round and one of the best div 4's,keep it up.
Who approved g? Why?
A NP-hard problem. LOL
I submitted a n^2 2^n solution which later got hacked due to TLE. Any idea what was the intended time complexity/approach?
It was the intended complexity. I assume that you were hacked because of
unordered_mapinstead — this has something to do with hash tables' collisions.Oh my previous code was indeed the same code with
map. Which was hacked either. It was so dumb of me to retry the code withunordered_map. I'll link my solution after the system tests. But the idea was:1) Find all the subsets of the songs given.
2) Create a graph with vertices as the songs choosen and edges between them if they have a connection (common genre or song writer).
3) If the graph has a Hamiltonian path then that order can be choosen and we try on larger size subsets.
Update: I was able to locate it now itself: Submission
Wasted a lot of time in a dsu/graph-based solution in G, when it was such a straight bitmask dp :/ pain
about F, the only case answer -1 is c != a + 1 right...?
Good round, thanks mesanu SlavicG flamestorm and all testers.
in F can anyone explain the -1 case
Initially there is one spot for a leaf. Adding type A vertex takes a spot for leaf, but creates two more (+1). Adding type B vertex takes a spot for leaf and makes one (+0). Adding type C vertex takes a spot for leaf (-1). All leaf spots should be taken so there is $$$1+a-c = 0\rightarrow a+1=c$$$.
Right. Another way to see this is — for it to be a valid tree, number of edges should be equal to the number of vertices — 1, by definition. Hence,
2 * a + b = a + b + c — 1
a + 1 = c
Good round!
Here's my live coding + commentary during the above contest: https://www.youtube.com/watch?v=kQOWiTvgah0
Would be glad if some of you find it beneficial!
My submission 253708600 for E was hacked.
Can someone hack these as well:
253879443 (I don't understand how it's faster)
253879584
done
I request to disqualify the competition because they included the name "Taylor Swift" in the test cases :-)
Когда рейтинг обновят
Happy to finally get in DIV4 rounds :), and finally promoting to pupil. The problems were nice, sadly I had not beeing able to finish all 7 as I used to much time for E. Thanks to the writers and testers for creating this beautiful round.
Does code force hack by someone yesterday I successfully submit 3 questions and accept all but few moments ego it not show any questions submitted and suddenly showing only one question submitted why this happened does this happen with only everyone facing this issue and not get any rating yet
Is it hacked? Or the submission is in queue as the system testing in on.
This is normal when system testing is happening, just wait until it's over
I had only 5 jugs of lassi this time..... In next contest I will be mango lassi.... be tuned to see me there as well.
Yours Lovely Kesar Lassi
CONGRATULATIONS the system testing took forever
Has anyone got updated ratings???
No updates yet, I expect they will come out soon today
is this contest made unrated? Why it is showing unrated in my profile although I am having rating less than 1400
It will appear as unrated until the official rating changes will be out.
Oh okay...thanks
You're welcome!
when will the ranks get updated? I was 600+, solved two problems. Shouldn't my rank be changed?
Yes, your rank will be updated as soon as the new rating changes will be out. That will happen probably today.
When will ratings be updated?
They are out.
I think there is a bug with people rating changes for this contest
oops, I think it was a lag, codeforces was showing their previous rank names even though their rating changed (for example for 1405 it was still showing pupil). But now it is ok
Are you OK? This f**k E, I use map get TLE, but use unordered_map or add a return get AC, just because constant. This solution is like n*sqrt(n), why just give 1s?
On E I also used map but not got TLE, Here is my code: 253803164
mesanu SlavicG I got a mail stating:- Your solution 253808750 for the problem 1950E significantly coincides with solutions SahooBishwajeet/253808750, candidate_3_months/253813331.
I checked the solution comparison and most of the common part was use of same #defines and variable initialization. Though the approach looks quite similar, which is to my surprise, I can assure you that I've not cheated in any form. I've followed an article on GeeksForGeeks which has a similar problem to solve the problem in the contest.
The problem approach is quite similar to the problem : https://www.geeksforgeeks.org/find-given-string-can-represented-substring-iterating-substring-n-times/
Please check the issue as I've not used any unfair means during the contest period and honestly gave the contest.
Here are the comparison images for reference
Пользователь Alfar_ABI уже написал о том что произошло и как так вышло что коды получились похожими