We invite you to participate in CodeChef’s Starters 164 aka Shaastra Programming Contest conducted by Shaastra IIT Madras and sponsored by KLA, this Wednesday, 11th December, rated upto 5 stars (i.e. for users with rating < 2200).
Time: 8:00 PM — 10:00 PM IST
Joining us on the problem setting panel are:
Contest Admin and Statement Verifier: Shreyan Dominater069 Ray
Text Editorialists: Nishank IceKnight1093 Suresh
Tester: Apoorv TyroWhizz Kumar
Setters: Ved Ved prakash, Shanmukh Scintillator_Sha Raj, Varun Tide Koushik.
Register here and also please fill out this form to be eligible for the offline finals where prizes worth 120K INR await!
All competitors who solve at least one problem will be entered into a raffle for winning exciting Shaastra's Merchandise!!
Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest. The video editorials of the problems will be available only to Pro users.
Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here. Hope to see you participating.
Good Luck!
Do we need to solve problems that are unrated for our division as well for the Shaastra ranklist?
No. You are not required to solve the unrated problems for your division.
Alright! Thanks for the info
What are the prizes?? And How can someone know if he is selected for any prize??
fuck permutations question. its always some stupid pattern guessing. Also what a joke of an editorial for construct perm question. I dont get how fucking 800 people solved it in div2, was it gptable ?
Seriously, it took me 1h+ and several simulations to get the pattern. Didn't have time for the simple Connecting Wells problem because of it. It's crazy that this is the second most solved, even more than the xor one.
Shit problems in Div1
in construct permutation i had that if all prefix sum of permutation modulo $$$n + 1$$$ is unique the it is valid, then construct pref sum modulo $$$n + 1$$$ as $$$pref = $$$ $$$[1, n, 2, n - 1, 3, n - 2...]$$$
and then for each $$$i$$$ find a number $$$x$$$ which when placed at index $$$i$$$ will give $$$pref[i]$$$
but i don't have a proof that we will always find such a uniqe number $$$x$$$ everytime
also if the above solution valid then we can solve the problem in $$$O(n)$$$ so i wonder why $$$n \lt = 10^3$$$
I solved since I saw many participants solved (even more initial B) , then I said let's guess bro xD.
because the problem setters are incompetent cucks that should not be setting questions. Just look at them. Barely experts. I dont understand why codechef would allow these people to conduct the main contest. If a college wants to hold a contest let them do it separately.
Construct permutation is one of the 2 only problems i created for the round.
doesnt make any difference. Constructive algorithms are supposed to have some basic logic involved in the construction, it should not be pattern guessing through brute force. pretty sure 90 percent of the people who submitted didnt do it by themselves. There was a similar kind of low quality question from the last div2 where you had to guess another random pattern through brute force.
It does make a lot of difference. Call the problem bad or good or whatever you want, honestly I dont care.
You called out the problemsetters for it and claimed them to be incompetent, i pointed out that the person was me. I have no issues with you keeping your same assessment of the problem, I just want it noted that the setters mentioned in the blog are not to be blamed.
bro stop allowing your friends in iit chennai to set crap questions while you deny questions proposed by other CM+ people from India. I will speak directly to the codechef admins if you keep doing this shit. Just because u r the highest rated person from India doesnt mean you can do whatever you want. Also another thing, stop putting math puzzles as coding questions. I know u r a math major, but dont let that influence coding competitions. If I wanted to solve random math puzzles I will go do a math olympiad question not competitive "programming".
I know 0 of the setters, and in general very few iitm people. Stop assuming things.
Yeah great argument. Put problems which suits your flavor , wtf?. If you just want "coding questions" for your practice go to hackerrank , leetcode or some similar CP websites.
non sensical math puzzles are not coding questions. It takes more thinking and time to set good coding questions which seem to be lacking in the current codechef team. Mooching off codechef money with the lowest of efforts. Its easier to just put some random math puzzle. Low effort.
What are some examples of "good coding questions" according to you (I'm not taunting you, I'm genuinely curious)?
https://codeforces.me/contest/514/problem/D. Its harder to create questions like this compared to copy pasting slightly modified questions from math books.
Is it? This is just a trivial application of two-pointers, and in my opinion, it is much more fun to solve some math or constructive problem instead of mindlessly writing two-pointers for the millionth time in my life. Of course, if there was some other idea in the problem, it could have been forgiven, but in this particular problem (and in most data structure problems at $$$r \le 1800$$$), there's no idea other than the data structure: the thinking part is trivial. Some examples of data structure problems I like: https://codeforces.me/problemset/problem/1942/D (of course, this is classical for anyone who prepares for interviews, but the reduction to that technique is enjoyable), https://codeforces.me/problemset/problem/1919/F1 (for some people, this may be trivial of course, but I personally enjoyed solving in contest, and same goes for the hard version), https://codeforces.me/problemset/problem/1904/D2 (one of the few data structures problems with $$$r \le 1800$$$ which I like). I agree that going too far (such as https://codeforces.me/problemset/problem/1916/D) is also not justified, but problems where the construction is motivated (you would be able to reach it without brute force) are fun to solve.
As I have mentioned already math puzzles are lowest effort questions one can set. Hence the reason why they do it. They get paid the same anyway so they just do the bare minimum, which is unfortunate.
Can you please explain how to arrive at the construction logically? I realized that the prefix sums array modulo (n+1) should have n+1 distinct values. How to construct after that instead of just generating permutations and guessing..
There is absolutely no intuitive way to do it. Just pattern guessing using brute force. One of the worst types of questions.
Interesting behaviour from your side. You remind of the this story. Anyways Problem becomes little bit intuitive after realizing the prefix sum observation. From there you just have to construct one such permutation which have all distinct prefix sums modulo $$$(n+1)$$$. one such way was induction. Try to find possible answer for $$$n=4$$$ and then try to induct from there.
while upsolving the problem i solved it like this 1 and n always add upto n+1,similarly 2 and n-1 and so on if n is even then they will all exist in pairs and become multiple of n+1.Hence n should be odd.if we keep 1 2 3...n then if n+1 can be sum of some sequences like 10 = 1+2+3+4. for n=9.then i just guessed 1 n-1 3 n-3 5 n-5... should work becoz observe it is adding upto multiple of n and will become a*n if a is even or an + k.and k >a hence it will not be divisible by n+1.
Shit Time constraints for Connecting wells Kruskal's doesn't pass...
I used DSU with Binary Search. The time complexity is (n^2 * log(10^9)). Basically for every mid you find with BS, Check if it makes a single component or not.
Hmm interesting, but I just changed my vector of vector to vector of tuple and it passed :(
Huh, that's surprising, seeing how Prim's passed
https://codeforces.me/blog/entry/137161?#comment-1227115
Is there a proof for the solution to CONSPERM or an intuitive way to get to the prefix sum permutations array without simulations?
Every platform passes through highs and lows , the starters 163 which I was the main author there , people seem to like it , but now people seem not.
It's normal , We cannot make a round enjoyable by everyone , starters 163 was kinda educational , so beginners love it , that's why .
Personally , The problems were good and as Dominater069 mentioned earlier
that's why C's constraints were tricky .
I'd like to say Dom and authors played a good job on making this round happen and we need to believe that it's a lack of our experience that we are not good enough in certain topics , so instead go and improve , because guilting others isn't good.
The point is it depends on the platform standards , reviewer standards and testers feedback mainly , So you cannot blame someone specifically as it's shame to blame the authors or the reviewers .
How are you allowed to author rounds when u r a newbie?
see Contributions section..
Did anyone manage to pass Div 1 problem C with DSU? For every pair of nodes, I find the time when they will connect and then I merge the nodes in the increasing order of times and break when all gets connected but I keep getting TLE even though the complexity is O(N**2)alpha(N) if I am not wrong.
Yes I have used Binary Search + DSU , which has time complexity of O(N^2 * log(1e9)) , It managed to pass though :
link to submission : https://www.codechef.com/viewsolution/1114263702
Edit: I converted this to C++ and got AC. So, I guess really tight constraints:(
Yes, I was also getting TLE on same approach. I converted local array to global array and it got AC.
I was also getting TLE many times using that, you can reduce the time complexity to $$$O(N ^ 2)$$$ using the fact that graph is dense and use prims algo to get the mst.
I got caught lacking on the previous CF round where you also had to brute force to find some pattern to construct a permutation, managed to solve it this time : )