Hej, Codeforces!
mesanu, SlavicG and I are very excited to invite you to Codeforces Round 937 (Div. 4)! It starts on 28.03.2024 17:45 (Московское время).
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, nskybytskyi, 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://codeforces.com/blog/entry/127616?#comment-1133556.
UPD: The editorial is posted!
i wish i could solve all problems glhf
Good luck!
As a participant,I would like to thank for new Div 4 contest
Dominater069 orz
Dominater069 orz
Dominater069 orz
hope to reach CM
Are you stupid or something, how are you planning to reach cm.
Why no green/cyan testers in Div4 round?
Hope everything goes OK!
Ramadan Kareem
Ramadan Mubarak
Hope this will be the best Div.4 ever
Good Luck for every parcipicant!
U2 bro)
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?
Yes, it is 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
Same. Hope the next div 4 will come soon...
My second unrated div 4 contest :-)
Eagerly waiting for some "lovely" div4 questions , Cyan is on!
please be a div 4 contest for div 4 people
You seem like you got stung by the last Dev 4 ":
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
Just try to not be like me...
what's wrong about you ?
Idk, just look at my graph it's horrible :(
I hope to reach specialist one day.
You have made it man. Tadaaaa
Yes Bro finally
Congrats !!!!!
The first unrated div.4.
GL&&HF
my name is nate higgers
why do codeforces change time? i got email that contest will start at 14:35. Now it will be 20:35
No,it starts in the usual time
Thursday, March, 28, 2024 14:35 (UTC)they send it like thatFor ex: My country's in (UTC+4) that's why it starts at 18:35
In your country, it will start (UTC+6)- it starts at 20:35
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. -.-
Рейтинг дают за участие? Откуда можно узнать как рейтинговая система работает?
Why there isn't any gray,green or cyan tester?
I hope I can go green after this game.
you can
the ratings arent added yet for yesterday's contest ....how much time it usually takes?
within two days
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
delayforces
The contest is delayed?
yep by 10 minutes
yes
hoping this is not april fools now.
.
.
Hey guys, anyone have the problems for this div 4 so I can practice beforehand?
thats called cheating if u wanna know
GUYS I WAS JOKING HOW YALL HAVE THIS HORRIBLE SENSE OF HUMOR
and i was thinking why i am not able to see problems
why it was delayed? :O
Aiming for puple, wish me luck guys!!
The first contest after registering my account many years ago.
queueforces ?
queueforces this happens every first 10 minutes of a div4/div3 man
Seems like div5
I want to be your student
Let's go (5000 dollars per month)
today I broke my record. solved 3 problems :)
A,B,C,D,E Screencast: https://youtube.com/live/n4f4htV009w
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?
Wow only me ig, average python user
bro thinks he is on leetcode
lmao, leetcode comment are influencing me. Apologies for the comment, kinda new to cf :)
What was the idea behind F?
Build a full binary tree
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.
Thank you man! :)
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
if I do 5 div4/div3 is my rating going to be more accurate/ higher? What do you recommend?
In the time converter problem, latest input data can't be a coincidence. I wish I could know what was the inspiration behind this particular input data. 4 problems solved, but stared late today, I hope for a green field.
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 can solve E without hashing first the upper bound for number of divisors will be (n ^ 1/3) then all u need is to try all divisors of n for each divisor you can check if k is valid in o(n) by grouping indeces(i, i + k, i + 2k , ...) for each i <= k then you its easy to check wither its valid or not thats overall complexity o(n * n^ (1/3))
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))somehow i thought that listing all the possible binaries in D and then using dfs was a good idea i am stupid
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 :)
Hey guys, I solved 4 problems, A, B, C, E. I see that each of my solutions got accepted bu only with one test. So, how can this be? How can a solution be right with only one test. Will it be counted as wrong later?
of course, if after contest you WA in another test, you will get red -1 and drop rating
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...?
How to do hacking this div-4 round?
Good round, thanks mesanu SlavicG flamestorm and all testers.
Is this an unrated contest? (Actually I'm just starting with CP and this is my first contest and I just checked my participated contests and it says this is an unrated contest but, here it is mentioned as rated in the description.)
no babe, rating will update after (avg 1 hours -> 1 day), you can try extension browse Carrot or CF-Predictor to get rating now
sir same happened with me i don't get any rating
don't worry, we same too, so waiting
Able to solve first 4 !! My greatest contest ever!!
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!
If I become the green man after this contest, I will dance samba!
You cant bro.Your rating is less now. Give 5 more div4.
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 solved 3 questions in this contest yesterday but there is no change in my rating. current rating -> 774
The contest is still in hacking phase. Ratings should be updated by today
It will first test the system for checking the solution of all participants.So it will take upto 24 hours after the contest timing.
Why is my name not in common standings and where should I complain ??
I request to disqualify the competition because they included the name "Taylor Swift" in the test cases :-)
I hope testing period doesn't take so long ☺
Why is the contest showing unrated for me in my profile graph? I'm still 700~ newbie
just wait for a while.
i dont get any rating sir can anyone told why this happend and how to get rating
Did u get it?
Когда рейтинг обновят
Guess it's time I stop giving div4's . Div 3 and 2's go very well for me, I always get f*ed in div 4s. Don't know why.
what happened this time
Did upto D. I'm very bad at working with strings in cpp, so wasted a lot of time. Did E in Python just after it was over.
Waiting for rating change be like
the worst feeling tbh
When will the ratings come
So when will the ratings be updated?
after system testing probably
On some div1/2 contests, it is as immediate as lightning once the round ends, rating updates. On other hand, for other contests, it delays. This delayed lot.
well i haven't seen it update immediately, i think it depends on hacks and new tests
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
Ok sir it's my first time in CP on codeforce
So who will I see first? My children, Or The Rank??
My friend solved 5 questions and green mark shows during contest but today is show again then only show 3 question are solved and submission section remaining 2 are in queue status how it possible!?
system testing is going on. Check this on dashboard page: https://codeforces.com/contest/1950
Ok
i got 3 questions correct yesterday, now it is showing only that i only attempted two and one of them is still inqueue and the third one shows like i didnt even attempted it why is that?
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
Wow! That lassi looks delicious
CONGRATULATIONS the system testing took forever
Still no rating changes tho...
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 ratings be out
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
Finally, I can change my profile picture :)
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 уже написал о том что произошло и как так вышло что коды получились похожими
I used Ideone in public mode as I was not aware of this and my code was copied and distributed online. I will keep this in mind from the next contest. Please do not give me any penalty. This was my first contest :(
mesanu SlavicG I got a mail stating:- Attention!
Your solution 253771024 for the problem 1950D significantly coincides with solutions omkargho78/253756793, Codebind_hp/253758181, Nayan23/253767879, Fuck_BIT/253771024, BitWix/253774128, bdn_iitm/253791189, r1ashwin/253791530, onkar.jondhale/253810321.
| i have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition and i don't even know all of these, 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.. please recheck and do not give me penalty. mesanu SlavicG
Dear Codeforces Team,
I recently received a notification regarding my solution (253819542) for the problem 1950E, indicating similarities with other solutions. Upon reviewing the mentioned solutions, I acknowledge the logical similarities. However, I would like to clarify that my approach was derived from a publicly available resource, specifically an article on GeeksforGeeks (https://www.geeksforgeeks.org/find-given-string-can-represented-substring-iterating-substring-n-times/). I further would like to clarify that I did not utilize any third-party IDE platforms like ideone, ensuring the integrity of my solution.
I understand the importance of maintaining originality and uniqueness in submissions, and I assure you that any resemblance was purely coincidental. Moving forward, I am committed to ensuring that my solutions remain distinct and reflect my own understanding and effort.
I kindly request that my solution be reconsidered in light of this explanation. I value the opportunity to participate in such amazing contests and strive to uphold the standards of integrity and authenticity.
Thank you for your attention to this matter. Please feel free to reach out if further clarification is needed.
my this id and kalpesh_2495 is operated by me so unknowingly my solution where same for the contest with that id and this id.so,i am sorry for this and i will not repeat this.
Hi Codeforces Team!
I have recently received a message stating that my solution to one of the problems (1950D) matches significantly with that of some other contestants. In my solution, I have checked if the factor of a number is binary decimal or not. This part of the code coincides because it is a publicly available article from where I had previously learnt it — https://www.geeksforgeeks.org/check-if-the-given-decimal-number-has-0-and-1-digits-only/
After this, if the number is a binary decimal, then we recursively call it on the number divided by the factor itself. This is a very straightforward approach and the loop will obviously run only upto sqrt(n) because we are checking for factors. So, the only place where code match can cause suspicions is due to an online resource.
I also write code on an online c++ compiler so I am not sure if it is picked up from there.
This conclusively proves that there is no code copying involved. Even though the approach is similar, the question is pretty straightforward so it must be taken into consideration that it is indeed possible. Thanks, hopefully this will get resolved and result in an unfair penalty for me