yash_daga's blog

By yash_daga, history, 16 months ago, In English

We invite you to participate in CodeChef’s Starters 97, this Wednesday, 5th July, rated till 6-stars Coders (ie. for users with rating < 2500).

Time: 8:00 PM — 10:00 PM IST

Note that the duration is 2 hours. Read about the recent CodeChef changes here.

Joining us on the problem setting panel are:

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 for all users for 1 day as soon as the contest ends, after which they 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!

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

| Write comment?
»
16 months ago, # |
  Vote: I like it +15 Vote: I do not like it

hope to reach 5*

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to reach 5*

»
16 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Reminder: Contest starts in 3.5 hours.

»
16 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Hope to reach expert in this contest 💀

»
16 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Hoping for 5 star. This may be my last ever cc contest. Finger crossed

»
16 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Hurray...!!!A contest made by alumni of my college.... looking forward to a great round and hope to reach 5 star.

»
16 months ago, # |
  Vote: I like it +1 Vote: I do not like it

great round

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

CodeChef_admin Hi, on the official website the editorial is pointed to START86 instead of START97.

»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i wasted an hour on "Triplets Min" as I have used unsigned long long instead of long long because the constraints given are Ai>10^-9. But there are negative integers in test data

»
16 months ago, # |
Rev. 2   Vote: I like it +54 Vote: I do not like it

I managed to solve Disappearing Domino Game in contest in $$$O(n ^ 2)$$$ with an incorrect greedy solution.

I found who wins in a normal game (where $$$D = \infty$$$) simply using Sprague-Grundy. Then I implemented how the game would go and counted its duration (by checking if xor of independent games becomes $$$0$$$). If there were mupltiple choices for a move, I just selected the first one. If the duration is $$$\ge D$$$, this is a draw, otherwise output what Sprague-Grundy says.

I then tried to stress-test it, but it passed all the random cases. I bruteforced small testcases and found that the smallest one which makes it fail is the following:

Spoiler

My solution only managed to finish the game in $$$7$$$ moves, while it is apparently possible to do that in $$$5$$$. I didn't find any failing tests with an advantage to Bob, so maybe it is always optimal to choose the first move if you're losing (which seems kinda logical, because you wanna prolong the game as much as possible), but maybe it is just a matter of size.

I also found the smallest tests for $$$k = 3$$$ and $$$k = 4$$$, but they are all simular:

Spoiler

UPD: I also found a test where Bob wins from the beginning. Alice can force a game to last $$$12$$$ moves, but making the first possible move can only achieve $$$10$$$.

Spoiler