We invite you to participate in CodeChef’s October Cookoff, this Sunday; 24th October from 9:30 PM — 12:00AM IST.
The contest will be 2.5 hours long. There will be 7 problems in Div 1/2 and 8 problems in Div 3. It will be rated for all three Divisions.
Joining us on the problem setting panel are:
Contest Admins: Ashish Ashishgup Gupta and Anton antontrygubO_o Trygub
Head Admin: Alex Um_nik Danilyuk
Tester: Danny Tlatoani Mittal
Setters: Jeevan JeevanJyot Jyot Singh, Anshu _runtimeTerror_ Garg, Rahul sapora Kumar, Prasant prasant21 Kumar, Shiva Agnimandur Oswal, Sandeep dazlersan1 V, Anton antontrygubO_o Trygub, Utkarsh Utkarsh.25dec Gupta, Lavish lavish315 Gupta, Ashish 7KIRA1999 Kumar
Statement Verifier: Trung Kuroni Dang
Editorialist: Nishank IceKnight1093 Suresh
Video Editorialists and Translators will be added a bit later
Problem Submission: If you have original problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.
Prizes:
Global Rank List:
- Top 10 global Division One users will get $100 each.
- Non-Indians will receive the prize via money transfer to their account.
- Indian users will receive Amazon vouchers for the amount converted in INR.
Indian Rank List:
- Top ten Indian Division One coders will get Amazon Vouchers worth Rs. 3750 each.
- The rest in the top 100 will get Amazon Vouchers worth Rs. 1500 each.
- First-time winners in Div 2 who make it to the top 200 for the first time will get Amazon Vouchers worth Rs. 750 each.
- First-time winners in Div 3 players who make it to the top 200 for the first time will get Amazon Vouchers worth Rs. 750 each.
The video editorials of the problems will be available on our YouTube channel as soon as the contest ends. Subscribe to get notifications about our new editorials.
Good luck and have fun!
P.S. Seriously, try it, I think problems are interesting :P
UPD1: Sorry for confusion, the duration is 2.5 hours.
As an author of 2 of the problems, I can confirm that the problem set is well balanced and interesting!
I won't be able to participate because of T20 world cup. :(
Which country are you playing for?
How does this lame joke have so many upvotes lmao
Because mocking you for these stupid "oh no there is an important sports thing I should watch" is fun.
India lost because you didn't give Codechef October Cookoff today :(
Pain. Week is ruined already :(
Reminder: Contest starts in 100 minutes.
How long is the contest? Codechef website says 2:30, and your blog advertises 3 hours.
Edited, thanks
You're welcome. Looking forward to your lunch consisting of sweet cakes only :)
In SRTGAME, can Alice always win if all cycles in the permutation satisfy $$$\sum_{i \in cycle} {v_i} \geq 2 * (|cycle| - 1)$$$ ? Or is the winning condition more precise?
If that is the condition, how do you generate an optimal sequence of operations? I was thinking of something like this, but it felt too complicated to implement correctly:
Initially choose an $$$i$$$ such that remaining $$$v_i$$$ is minimal over all $$$p_i \ne i$$$ .
If for $$$j = {p^{-1}}_{i}$$$ , we have $$$v_j \gt 1$$$ , then directly swap them, otherwise, push this up to $$${p^{-1}}_{j}$$$ , and keep going like this till we get a set $$$x$$$ of elements such that $$$\sum_{y \in x} {v_y} \gt 2 * (|x| - 1)$$$ or reach an element equal to $$$p_i$$$ and close up that cycle.
Am I roughly on the right track?
You are almost done, you can choose the one which is minimum among those $$$p_i \ne i$$$, and among multiple minimums choose the one whose parent (the one on the side of incoming edge) is maximum and move this element to its correct place. You can prove this construction by looking at separate cases — When the cycle has some vertex with potential 1 (in that case we will always move vertex with $$$V_i=1$$$ to its correct place and it can be proved that potential remains at least $$$2 * (sz - 1)$$$ afterwards) and when no vertex has $$$V_i=1$$$ we can make any swap to move some element to its correct position and we will be having enough potential.
Yes, the winning condition is exactly that.
Let's first decrease some $$$v_i$$$ values so that the condition is strict: $$$\sum{v_i} = 2 \cdot (|cycle| - 1)$$$. Now, as long as the cycle length is more than $$$2$$$, it can be proved by induction that there will always be a cycle member satisfying $$$v_i = 1$$$.
You just have to repeatedly keep finding an element $$$v_i = 1$$$ and deleting it by swapping it with the previous element in the cycle. This can be done with queue to store all candidates + set/linked_list to find a previous element.
D was simply (k*n — 1) mod n = n — 1 .. I love how the solution uses such a simple and a clever idea :)
Btw, just out of curiosity, is there a reason the input format in RECHEND is not just a single permutation? It feels like the input is unnecessarily more complex and heavier than needed, especially since there would already need to be at least $$$10^6$$$ integers.
English statement: "During their turn, officers will have to move to an adjacent unoccupied cell one by one, in any order they want"
Russian statement: "During their turn, all officers move at the same time", in bold
Did the English statement say one by one at the start or was it updated in-between? I don't remember one by one being there when I read the statement. However its possible I just missed it since I also missed the word "only" later on in the statement.
In problem RECHEND
Can anyone tell me where my solution fails? Solution
My idea was to find the block in the first row and block in the last column, then from the location of both the block I was checking its diagonal till the first column or last row and if in both the cases at least one cell doesn't contain block then answer would be YES else NO.
For the above testcase, the answer should be "No", your solution gives "Yes".
You have to do the same check for the block in the last row.
Yes I am handling the case for last row by considering diagonal started from last column and ending on last row. And my code works fine for the test case you have given, printing YES only.
It should be "No".. "Yes" is a wrong answer
How to do 'Can you reach the end' and 'Find Modulus' problems ?
Find modulus:
Print any $$$x \geq 10^{18}$$$ in the first query, you will get a remainder $$$r$$$ back.
Clearly $$$x = n \times k + r$$$ for some $$$k \geq 1$$$ since $$$x \geq 10^{18} \geq n$$$.
Subtract $$$r + 1$$$ from both sides of the equation.
We then get $$$x - (r + 1) = n \times k - 1 = n \times (k - 1) + (n - 1)$$$
So querying $$$x - (r + 1)$$$ gets you back the value of $$$n - 1$$$.
Reach the end:
It is unreachable if there is a diagonal that cuts the board into two parts.
This diagonal will either be from the left column to the top row $$$[(1, x), (2, x - 1), \ldots, (x, 1)]$$$ or from the bottom row to the right column $$$[(n, n - x), (n - 1, n - x + 1),\ldots, (n - x, n)]$$$, you can clearly check both by iterating from the first column and last column and checking the rows progress as expected till you reach the first / last row respectively.
Very interesting problems. Thanks!
one thing: Very tight TL in https://www.codechef.com/COOK134B/problems/RECHEND.
Had to replace map with vector to pass :(
Idea used in (Problem E) was similiar to this problem.
GREAT CONTEST ABLE TO SOLVE ONLY 2IN DIV2 ANY TIPS HOW TO GROW AND PLEASE TELL PATH FOR GRAPHS AND DP THESE TOPICS SEEMS SCARY EVERY TIME I START I SIMPLY GIVE UP AS I DONT COME UP WITH APPROACH TO PROBLEM PLZ HELP THNX IN ADVANCE
You can start by turning off CAPS-LOCK. 3 in next contest guaranteed.
Maybe he's competing on SQL, who knows.
Anyone received prize or confirmation for this contest
Did anyone receive the Voucher for this contest? I got the confirmation on Jan 5 but have not received the voucher after that.
Received