Hello all!
We are proud to invite you to CodeCraft-21, which takes place on Mar/29/2021 17:35 (Moscow time). It is rated for all Div2 participants (rating under 2100).
This contest comes under Threads'21, as a part of our annual techno-cultural fest Felicity, IIIT Hyderabad. We have special prizes for Indian participants!
You will be given six problems to solve in a duration of two hours.
We have tried our best to keep clean statements, useful samples with good explanations, and strong pretests! We have written step-wise editorials, and will also release video editorials!
We would like to thank these amazing people for helping make the contest happen:
- BledDest for great coordination of our round
- ninja_28, dixitgarg, ltc.groverkss and myself for amazing problemsetting
- madlad, AnimeshSinha1309, shash42, nikhil_c for contributing several important problem ideas
- TheOneYouWant, amnesiac_dusk, awoo, SleepyShashwat, gaurav172, adedalic, amul_agrawal, vasu0403, d_shi, Horcrux1729, RajMaheshwari, menavlikar.rutvij, Arpanet, spashal, Tinkidinki for testing our problemset, and providing very valuable feedback to improve problem statements, sample cases, and pretests
- gaurav172 and shaanknight for giving valuable advice on contest creation
- ahish9009 and harshita_gupta for excellent poster and tshirt design
- And finally MikeMirzayanov for the amazing platforms, Codeforces and Polygon.
There will be an interactive problem! You are recommended to read the corresponding guide.
We hope you enjoy the contest as much as we did preparing it! Good luck!
Update: The scoring distribution is 500/1000/1750/2500/2500/3000.
Update: Editorial is up! Video editorials available on our YouTube channel.
We are sorry for the sudden increase in difficulty from C to D. Nonetheless we hope you enjoyed the problems! :)
PRIZES: The following twenty lucky participants receive a tshirt:
- top 10 Indian participants
- random 10 from top 100 (ranks 11-100) Indian participants
These ranks are determined from the combined unofficial ranklist. We are coordinating with the CF team for the tshirt design, and we'll update the blog post when it is finalized. We also have INR 7K worth prizes exclusively for IIIT-Hyderabad students!
Hope I remain a specialist after this Round;)
Good luck :)
I understand the pain sir, upvoted !
Prolly the community didnt feel the pain of get downvoted lol, people downvoted :/
Wishing all Indians as well as all members of codeforces community " A very happy holi(Festival of colors celebrated in india) in advance.
Although the contest will clash with holi celebrations nevertheless will try to give it. :)
How you decide if a participant is from India or not.
Scrapping the leader board and applying simple script where data-field of country is India for a participant. As it is public for every user.
Hopefully I'll reach Green after this contest! I love bright colors, not this Grey :(
I hope too :)
Hope I become expert in this contest
video editorials ! hmmmm.... NICE =)
I can vouch that the clean statements, good samples with useful explanations and strong tests part is definitely true. This is also one of those rounds where basically everything seems to be contest-ready (statements, tests, sample explanations etc) more than 48 hours before the contest, which is good (not having this is more common than you would think, sadly...). Kudos to the Codecraft team. I would recommend participation.
wtf!? no "As a tester ..."
its new method ig
I second that.writers have really worked hard and have prepared a beautiful problemset.
Your graph is cool! T_T
As a tester, I found the problems to be very interesting and I had a lot of fun solving them..... Don't miss this contest!
chal jhoote
what about score distribution?
Video Editorials. Excited. I wish there is more of it in codeforces.
High hopes with this round
What if there is less than 10 indian participants in the rank range 11-100?
It is random 10 from top 100 Indian participants, and not random 10 Indian participants from top 100 :)
Got it
CodeCraft is a new way to learn to program by constructing things in a virtual 3D world => Google's Definition
What a deep meaning :)
Hey guys i want to wish you all a happy holi. Discord is full of copypasted holi messages, that people don't even read and just forward to other servers. I don't like that. I like to write what i deeply wish and what comes from my heart. Our friendships, from the most deep ones to the most virtual ones are very important and will never be represented by a simple message copied from elsewhere. This being said I would like to thank all of you. You are the best hockey team i've ever played with.
Hockey team?
No offense, but ironically your new year message was the same except "holi" in it lol.
That hockey team sarcasm is so good!
Hey guys i want to wish you all a happy holi. Discord is full of copypasted holi messages, that people don't even read and just forward to other servers. I don't like that. I like to write what i deeply wish and what comes from my heart. Our friendships, from the most deep ones to the most virtual ones are very important and will never be represented by a simple message copied from elsewhere. This being said I would like to thank all of you. You are the best hockey team i've ever played with.
Posts that are so sarcastic that they return to normal!
How do you know if a participant is Indian or not? On CF it is very easy to change the country. And some participants don't even include country name in their profile.
We will post the relevant details after the contest is over (when standings+rank deltas are finalized). So keep following this blog for future updates!
Hope I can add a new colour to my CF account ( Specialist :: Cyan ) in this festival of colours :)
+
Hopefully, I will try to sit and make efforts till the end of the contest and won't give up in between :)
Forgot to mention earlier, there will be an interactive problem! You are recommended to read the corresponding guide. Good luck! :D
interactive, you mean binary search problem? :p
Or segment tree maybe.
Hope I become expert in this contest.
Finally India's contest. i challenge any non-indian to win the contest
Kuch bhi xD?? Show me a single global/div1 contest where an Indian was the winner(Rank1)
Doesn't matter yr!
Aapna kya lena dena
Are you weed on high ?
Please announce the scoring distribution of the contest!!!
Upd: Announced
Done, please refresh. Thank you.
Kudos to IIIT-H, hoping for small and clear problem statement
Another Div 1.5 is coming :(
after seeing score distribution i'm like my limitation is up to problem C
make it 16:40 please,, eating my lunch :D
Whatta jump between C and D :'(
test cases are very limited in C where k=1,2,3 and then direct 250 fuck me up !!
the k = 250 is actually good tho since if you pass that test case then the chance your solution is wrong is too low. Stop whining and go improve instead
If your div2B is harder to prove than your div2E then miss me with that shit
Seriously though, I felt the necessity for a proof, otherwise I would've solved that. How does one prove that the greedy thing works?
It is allways better to place a piece in a row instead of not using the free space.
Then, we can allways put two of a shorter length where we can put a longer one.
So, if we simply put allways the biggest possible piece into the remaining space of the current row, then it is optimal.
Good sample cases :)
India is an actually a good country :D
A= An Easy Problem
B = Bad Statement
C= classical DP
D/E/F ---> Sorry Don't want to kill myself.
Weak pretests in D (:
what is pretest 8 in problem E?
My notebook just went full as I tried to solve Problem C with a diagram for the big K value.
How to solve Div2 E ?
was there any special algo for problem D ? or just looping and bruteforce like sieve ?
Can't believe I passed 40 pretests on E. If I do not get FST, that problem is better suited for the April fools contest. I didn't even understand the problem correctly IMO.
What did you do ?
random solution which I thought would fail within the first few pretests. I can't even explain my solution because I have no idea why I did it. 18 mins left, I just wrote something.
I wish i could write something like you sir . xD
Haha, okay. I tried thinking of some random solution too...Didn't work !
Same thing here — I took a gut-shot: while there is a city with 0 incoming roads, remove it and decrease all other values of K by one. Then take the max remaining K and min remaining K as your answer, unless you end up with no array left, in which case there never was a strongly connected component.
Let's think about why this works. Suppose every road has >= 1 incoming road and >= 1 outgoing road
If we are at node X, and we perform DFS, every time we reach a new node, we will be able to continue, because no city is an end point
The graph is connected, so we will reach every city, and use every road
Therefore the remaining graph is strongly connected
This means that once we've removed the cities with only outgoing edges, we can just take largest remaining K value and the smallest remaining K value.
EDIT: I am clearly missing something — my solution should have failed according to uphacking.
EDIT 2: The above is wrong — all nodes must either be part of a strongly connected component, or they must connect other strongly connected components. So the correct approach is actually to sort all pairs by the absolute differences in k-value, and if the smaller k-value city is reachable from the bigger k-value city, that's the correct answer.
I somehow missed this line — There is exactly one directed road between every pair of houses" even though it was in bold. Now I understand why this works. Just now I received a message that my solution has been uphacked so system tests were weak.
My code failed the same test yours did as I just managed to hack myself with it! So I must also have missed something.
Same for me. I didn't even understand why I am writing the solution but alas, it passed all the test cases. !!!
Can someone explain Problem E? I sorted it by descending |ka -kb| pairs and queries a b if a>b and b a otherwise until I get a match. I did not expect it to work but somehow it passed test cases.
I think it's because the structure is that you can group houses into groups of biconnected components (which are also cliques). Then the meta-graph on these biconnected components form a total ordering, where all edges between two biconnected components all go in the same direction. Any house in a lower rung in this total ordering must have strictly more incoming edges than any on a higher rung.
I did the same thing after removing all nodes that do not belong to a cycle, failed on pretests :(
Well I used the pigeonhole principle — Say we have two vertices A and B and $$$k_B > k_A$$$, then we know that there are $$$n-k_A$$$ edges outgoing from A and $$$k_B$$$ edges incoming to B. Now by the pigeonhole principle we know that if the some of the above two quantities is greater than the total vertices apart from A and B, and if there exists a path from B to A, then we have a A and B in a directed cycle — and notice by choosing $$$k_B > k_A$$$, $$$n-k_A+k_B > n-2$$$ is true by default. Therefore if we query
? B Aand getYesas response, then we have A and B in a directed cycle — which is what we want. I'm still little sus about this being sufficient.Nooooo I was like 1 minute away from solving E! Was it just to loop through all possible combinations of A and B where B has more incoming edges than A, in order from best to worst according to the cost function, and if A is reachable from B then it's the answer?
Yeah, I think that's it. I feel ya man, I've been there before.
any one tell me how to solve div2 b?
Greedily fill using the largest possible rectangle.
If no such rectangle is possible, stack above (height++).
Repeat until no recatangle remains.
111372831
I am not a native Indian, but one by heart. Do I get a t-shirt too?
Makes me wonder, if a participant changed his country of origin in the settings to Indian as of now (or maybe prior to the contest), does the system consider that participant to be an Indian? Now that's just a scam if possible right...
Change your country tag to INDIA. As simple as that
How to solve C ?
2-D DP. One for the index other for k.
can u please tell more of the solution and can attach your code link as well thanks
https://codeforces.me/contest/1498/submission/111375468 have a look at this also
let f(k, n) be the count of multisets with "k" decay age and n planes available in its direction.
Reflecting on a particular plane, we get another ray with N — n planes (direction inverted) and k — 1 decay age.
The original ray continues to travel with n — 1 planes remaining.
so, f(k, n) = f(k — 1, N — n) + f(k, n — 1)
Simple TOp Down DP.
Am I the only one who thinks that the time limit for problem E is too tight for Java 8/11 ?
Sorry to hear that! We've a AC submission in Python on our side.
Thanks for the confirmation. I might have to optimize my solution more if it doesn't pass System Test Cases. !!!
Just an FYI for the future, Java often runs slower than Python in interactive or output heavy problems. For example, during the testing of 1451E2 - Bitwise Queries (Hard Version), the limits on $$$n$$$ had to be reduced from $$$2^{17}$$$ to $$$2^{16}$$$ as Java couldn't pass it without using PrintWriter or custom IO classes instead of the default System.out functions, while Python easily passed.
Similarly, while setting a problem on Codechef (which usually has a much faster judging environment, especially with respect to IO) that required a large string to be printed, Java failed to print $$$5 \times 10^{5}$$$ characters in 2 seconds while C++ and Python easily managed to print $$$10^{6}$$$ characters in the same time, all without any fast IO.
Then I guess the time limit should be a bit more, else the solution with CPP/Python having the same Java logic gets passed and Java solution gets TLE.
It may seem unfair.
HAAPPY HOLI EVERYONE !!
I am afraid of system test :(
Well, even if I sadly bugged my C (actually I just realized I was doing useless transitions lmao), I really enjoyed the round ! Problems were nice, statements clean, sample useful... I hope you'll do more CodeCraft rounds !
It is much easier than Div2 i think. But anyways problems were well framed with very short codes for all. But i personally feel that problemset is too easy or the problems should be shifted one level back for DEF , D->C, E->D, F->E. Thanks for the contest.
It's very sad, when tasks are sorted out of order of increasing difficulty...
fst :(
btw i believe F is easier than D and have less solves just because it is on position F
No way. It miiiiight be easier for those who memorize random algorithms but can't think. And even then it is dubious.
Somehow, I didn't think of a dynamic programming solution for C. I just ended up counting the number of particles with decay ages from i=1 to i=k and obtained that by using prefix sums.
Same here
And you are violet. What a shame!!!
Lol, why does having an alternate solution have to be shameful, if anything its a good thing — reading aliters is a good way to develop thinking.
Please help in this submission of C : https://codeforces.me/contest/1498/submission/111405668
Try to reduce the for loop inside the recursive function to one or two recursive calls.
Okay Got it. Thanks...
Can anyone tell how to solve C using iterative dp?
Have a look at this submission: https://codeforces.me/contest/1498/submission/111377465
Thanks.
Can you explain your approach.
i solved it iterative dp too but yours look eaiser
Consider some DP where the state is represented by:
$$${hits}$$$: The number of planes in front of the particle
$$${age}$$$: The age of the particle
And our answer for the state is the total number of particles that are produced during this state.
So, formally: $$${dp[hits][age]=}$$$ number of total particles produced when we shoot a particle with age $$${age}$$$ towards $$${hits}$$$ planes
So how to calculate the current state from previously calculated states? It seems tricky at the first glance but it's actually kind of simple.
When we shoot a particle towards $$${hits}$$$ planes what happens?
A new particle with age $$${age−1}$$$ gets reflected by the first plane in front of the current particle and it will now face $$${n−hits}$$$ planes, which is the state $$${[n−hits][age−1]}$$$.
The same particle goes through the first plane in front of it then continue to face $$${hits−1}$$$ planes (obviously it's age won't change), which is the state $$${[hits−1][age]}$$$
So now we know the transitions from our current state, the recurrence becomes:
$$${dp[hits][age]=dp[n−hits][age−1]+dp[hits−1][age]}$$$
Of course, this can be optimized to get rid of the second dimension since we only need the information from states with $$${age}$$$ and $$${age−1}$$$, this improves our space complexity to $$${O(n)}$$$, Code
I had to read that many times to understand it but worth
great solution, Thank you!
My submission of E is still "Pretests passed". I'm very confused by this crazy verdict.
I'll fix it!
Thanks!
To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!
I get "Accepted" only now after rating changes (on E, which I solved on contest), hope you will fix this.
Wow rating changes came so fast
sigma_g please have a look at my submissions for problem E with the same source code.
1. Submission during contest — It gives TLE.
2. Submission after contest — It gets Accepted.
Please have a look over this issue and do update the ranking if possible.
Can we solve c using prefix sums and iterations for each k??plz tell ..i think we can do this..but am not able to get correct ans using modulo
Yes, I did the same
i think this is something similar to what you are looking for
Could someone pls help me on what is wrong with this submission for D ? Also I defined int as long long and double as long double.
https://codeforces.me/contest/1498/submission/111408649
I did the old fashioned dp solution. But it seems to fail on test 12. Is it due to the fact I am using long double (precision error) ?
I think it's precision error. Actually there's no need to use double in this problem.
Can anyone please tell me why this solution 111375843 for problem B is wrong. I solved using 2 pointers. Thanks in advance :)
test: 1 6 7 1 1 2 2 4 4
Etdiroail is too good :}
<3
MikeMirzayanov
These two codes are exactly the same, but the first code was submitted during the contest got TLE on test 15 but the other code submitted after the contest got accepted.
The code, getting TLE: 111380434 The code got AC: 111417474
Due to which my rating got affected. Please have a look at it. Thanks
Your accepted code also passes in 982 ms and there is usually a +- 50 ms difference during execution times on different runs.
Also, avoid using
long longwhen unnecessary. It takes longer to read integers intolong long. For instance, this is your exact code with the line "#define int long long" removed. It ran under 600 ms which is significantly faster.https://codeforces.me/contest/1498/submission/111420403
Yeah, thank you for your explanation. I Will avoid using it next time when unnecessary. But can nothing happen this time? As the code is correct only, even the judge is giving accepted sometimes. So, during the contest, it is difficult to think of such a reason for a new coder even though it passes all the pretest. MikeMirzayanov
Don't worry, these things average out with time. There'll be another time when you'll get lucky. Everyone goes through such issues.
Problem Explanation was very poor for Problem C, D. It could have been better. I understood it only after reading sample input output.
Problem Writers should participate in Codeforces contests to understand how problem statements are written. It looked like problem setter was deliberately trying to confuse participants. If you can't write problems upto standards of codeforces, at least you can keep the contest private to your college, Don't make it Div2 contest.
When will t-shirt prices be announced ?
Ideally, it should not take more than a week to finalize everything and announce the results.
Awesome
Python doesn't support too deep recursion for problem C, even though I changed the limit.
Yes, that is why the editorial solution for Python is iterative.
When solving problem B using the binary search method, we select the height of the box and check whether all rectangles will be included in it. I cannot figure out how to account for the space that has already been used. How this formula works from the analysis ci = ci + 2 × ci + 1 + 4 × ci + 2…. Where does this formula come from? Explain someone. Thanks.
One block of width $$$2^{i+1}$$$ occupies the same space as two blocks of width $$$2^{i}$$$. Therefore, to account for space used by the $$$i+1$$$-th block, we add $$$2\cdot c_{i+1}$$$ to $$$c_i$$$. The same reasoning can be extended to larger blocks.
When will problem ratings for this contest be updated ?
You guys are not able to make a random generator in two days which can decide 10 from 11 to 100 ranks lol.
As clearly mentioned in a comment above, we will finalize the results and announce within a week ideally.
MikeMirzayanov please update problem rates for this round. It's been a week.
Congratulations to winners of CodeCraft-21 and Codeforces #711 (Div. 2)!
We will soon contact you regarding prize distribution.
Thanks!!
Wow, Thanks!
Thank you. Feeling lucky!!!
Thanks, feeling lucky with 9 others.
Feeling unlucky with 79 others.
Same :(
Thankyou, feeling lucky !!!
Thanks !!
Now that more businesses are gradually reopening, we can finally distribute the tshirts. We have sent out the form link to all the 20 winners (as well as the testers and the writers). The design of the tshirt is:
(credits to victorknox for the design)
We hope you like it! :) We will try to send the tshirts as soon as possible.
Cheers! :D