antontrygubO_o's blog

CodeChef October CookOff 2021
By antontrygubO_o, 3 years ago, translation, In English

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.

  • Vote: I like it
  • +163
  • Vote: I do not like it

Comments Comments (32)
| Write comment?
»
3 years ago, # |
  Vote: I like it +79 Vote: I do not like it

As an author of 2 of the problems, I can confirm that the problem set is well balanced and interesting!

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I won't be able to participate because of T20 world cup. :(

→ Reply
»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Reminder: Contest starts in 100 minutes.

→ Reply
»
3 years ago, # |
  Vote: I like it +31 Vote: I do not like it

How long is the contest? Codechef website says 2:30, and your blog advertises 3 hours.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

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?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    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.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it +11 Vote: I do not like it

D was simply (k*n — 1) mod n = n — 1 .. I love how the solution uses such a simple and a clever idea :)

→ Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it +16 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it +65 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    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.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to do 'Can you reach the end' and 'Find Modulus' problems ?

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 3   Vote: I like it +19 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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 :(

→ Reply
»
3 years ago, # |
  Vote: I like it +20 Vote: I do not like it

Idea used in (Problem E) was similiar to this problem.

→ Reply
»
3 years ago, # |
  Vote: I like it -73 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +87 Vote: I do not like it

    You can start by turning off CAPS-LOCK. 3 in next contest guaranteed.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +43 Vote: I do not like it

      Maybe he's competing on SQL, who knows.

      → Reply
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Anyone received prize or confirmation for this contest

→ Reply