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:
Contest Admin, Statement Verifier and Text Editorialist: Nishank IceKnight1093 Suresh.
Tester: Sushil SmolBrain Raaja.
Setters: Nishank IceKnight1093 Suresh, Sushil SmolBrain Raaja
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!
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
ya it was kinda difficult, took me 25 minutes.
the idea in itself was simple, longest segment without 1100,1001,0011,0110 as a subsequence.
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 :)
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?
ok I am stupid?
by div1 C you mean swap AB one? can you explain a bit more what was your dp state and transition?
thanks
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.