IceKnight1093's blog

Invitation to CodeChef Starters 196 (Rated till 5-Stars) — 23rd July
By IceKnight1093, 14 months ago, In English

We invite you to participate in CodeChef’s Starters 196, this Wednesday, 23rd July, rated for 5 star (i.e. for users with rating < 2200).

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

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 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
  • +26
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
14 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

I am the only one who feels Beauty in everything(DIV2C) is quite tough??how come this many participants able to get this?it took almost 70-80 minutes of my contest time to get AC

→ Reply
»
14 months ago, hide # |
← Rev. 7  
Vote: I like it 0 Vote: I do not like it

Div1 C: My idea: DP problems can be solved by matrices (similar to matrix expo), so maintained segment tree of matrices , and stored product of matrices for each node.

Div1 D: I fixed last 3 numbers, K,X,Y where gcd(K,Y) > gcd(X,Y) and just random shuffled rest all numbers (100 trails), luckily it passed.

Div1 E: I misunderstood the whole problem, I thought operation was to cyclic shift a (unsorted) subarray left / right.

Thanks for the contest, Good problems :)

→ Reply
  • »
    »
    14 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    did I misunderstand or isnt $$$f(P)$$$ always $$$\le 2$$$, just pick first $$$[1...i]$$$ where $$$p[i] = 1$$$, and bring $$$i$$$ to the back, then sort and bring $$$1$$$ to the front?

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

    by div1 C you mean swap AB one? can you explain a bit more what was your dp state and transition?

    thanks

    → Reply
    • »
      »
      »
      14 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      dp[i][0] = score obtained from the suffix part of array (i ... N) where A, B aren't swapped.

      dp[i][1] = score obtained from the suffix part of array (i ... N) where A, B are swapped.

      We can write transitions of these DP s.

      DP and these transitions can also be expressed by the product of matrices. (Prerequisite: Matrix Exponentiation)

      Now the problem boils down to finding product of matrices and doing point updates, which is well supported by segment tree.

      → Reply