### antontrygubO_o's blog

By antontrygubO_o, 6 weeks ago, translation,

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:

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.

• +163

 » 6 weeks ago, # |   +79 As an author of 2 of the problems, I can confirm that the problem set is well balanced and interesting!
•  » » 6 weeks ago, # ^ |   0 orz !!
 » 6 weeks ago, # |   0 I won't be able to participate because of T20 world cup. :(
•  » » 6 weeks ago, # ^ |   +352 Which country are you playing for?
•  » » » 6 weeks ago, # ^ |   -49 How does this lame joke have so many upvotes lmao
•  » » » » 6 weeks ago, # ^ |   +68 Because mocking you for these stupid "oh no there is an important sports thing I should watch" is fun.
•  » » » » » 6 weeks ago, # ^ | ← Rev. 2 →   -19 Fair enough. I was wondering whether fireblaze777 is actually stupid or has a collection of lame jokes.
•  » » 6 weeks ago, # ^ |   +7 India lost because you didn't give Codechef October Cookoff today :(
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   +16 Pain. Week is ruined already :(
 » 6 weeks ago, # |   +4 Reminder: Contest starts in 100 minutes.
 » 6 weeks ago, # |   +31 How long is the contest? Codechef website says 2:30, and your blog advertises 3 hours.
•  » » 6 weeks ago, # ^ |   +25 Edited, thanks
•  » » » 6 weeks ago, # ^ |   -21 You're welcome. Looking forward to your lunch consisting of sweet cakes only :)
 » 6 weeks ago, # | ← Rev. 2 →   +13 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?
•  » » 6 weeks ago, # ^ |   +25 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.
•  » » 6 weeks ago, # ^ |   +8 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.
 » 6 weeks ago, # |   +11 D was simply (k*n — 1) mod n = n — 1 .. I love how the solution uses such a simple and a clever idea :)
 » 6 weeks ago, # | ← Rev. 4 →   +16 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.
 » 6 weeks ago, # |   +65 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
•  » » 6 weeks ago, # ^ |   0 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.
 » 6 weeks ago, # |   0 In problem RECHEND Can anyone tell me where my solution fails? SolutionMy 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.
•  » » 6 weeks ago, # ^ |   0 1 5 1 2 2 3 3 1 4 5 5 4 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.
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » 6 weeks ago, # ^ |   +1 It should be "No".. "Yes" is a wrong answer
•  » » » » » 6 weeks ago, # ^ | ← Rev. 2 →   0 oops, my badthanks for pointing out.I forgot to set my ok to false
 » 6 weeks ago, # |   0 How to do 'Can you reach the end' and 'Find Modulus' problems ?
•  » » 6 weeks ago, # ^ | ← Rev. 3 →   +19 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.
 » 6 weeks ago, # |   +1 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 :(
 » 6 weeks ago, # |   0 Enjoyed from contest. Thank you
 » 6 weeks ago, # |   +20 Idea used in (Problem E) was similiar to this problem.
 » 6 weeks ago, # |   -73 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
•  » » 6 weeks ago, # ^ |   +87 You can start by turning off CAPS-LOCK. 3 in next contest guaranteed.
•  » » » 6 weeks ago, # ^ |   -24 Nice komedy
•  » » » 6 weeks ago, # ^ |   +43 Maybe he's competing on SQL, who knows.