Dominater069's blog

Invitation to CodeChef Starters 181(Rated for all) — 9th April
By Dominater069, 13 months ago, In English

We invite you to participate in CodeChef’s Starters 181, this Wednesday, 9th April, rated for all.

Time: 8:00 PM — 10:30 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!

UPD : Here are the number of problems in each Division:

  • Division $$$1$$$ : $$$6$$$ problems (and $$$2$$$ subtasks)
  • Division $$$2$$$ : $$$6$$$ problems (and $$$1$$$ subtask)
  • Division $$$3$$$ : $$$7$$$ problems (and $$$1$$$ subtask)
  • Division $$$4$$$ : $$$8$$$ problems (and $$$1$$$ subtask)

Congratulations to Top 5!

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

Comments Comments (19)
| Write comment?
»
13 months ago, hide # |
 
Vote: I like it +49 Vote: I do not like it

As a problem setter, the problems are cool. Strongly recommend that you participate in this round )

→ Reply
»
13 months ago, hide # |
 
Vote: I like it +21 Vote: I do not like it

Please make sure that no cheater get away in this contest .

→ Reply
»
13 months ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

ACed COSTSWAP 30s after the contest :( . Still enjoyed solving it.

→ Reply
»
13 months ago, hide # |
← Rev. 2  
Vote: I like it -16 Vote: I do not like it

I tried submitting an O(N²M²) solution for GOODMATRIX only to verify my approach (I was sure of getting TLE) and surprisingly it passed. Test cases were weak.

→ Reply
»
13 months ago, hide # |
 
Vote: I like it -15 Vote: I do not like it

For the problem of GoodMatrix. I have one confusion:

What would be the output for this testcase?
Generated Output from Passed Testcase
My Doubt
→ Reply
  • »
    »
    13 months ago, hide # ^ |
     
    Vote: I like it +5 Vote: I do not like it

    1. The given matrix does not satisfy both conditions of difference of adjacent cellz = 1, and average condition. No, division is not floor division.

    2. Nowhere was there a constraint on replaced values, only on the original values.

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

Anyone help in TREECOLOUREZ https://www.codechef.com/problems/TREECOLOUREZ

→ Reply
»
13 months ago, hide # |
← Rev. 4  
Vote: I like it +15 Vote: I do not like it

Can the Costly Swapping problem be solved in $$$O(N^2)$$$

My idea:

  • Swapping only (0,1) or (1,0) is optimal in the strings

  • Frequency of 0s and 1s should be same in both strings.

  • Lets consider positions of 0s in the strings, and lets try to match all 0s (if all 0s are alligned in correct positions in both strings, 1s be matched automatically).

  • Say $$$C_1 = \min(A, D)$$$ and $$$C_2 = \min(B, C)$$$ be the two types of operations we shall apply. Lets assume $$$C_1 \lt C_2$$$

  • I try to fix the number of times $$$C_1$$$ and $$$C_2$$$ to be applied to make the two strings equal. Say $$$x$$$ be the number of times $$$C_1$$$ applied and $$$y$$$ be the number of times $$$C_2$$$ be applied.

  • So $$$2x + 2y$$$ positions have 01 or 10 pairs. rest $$$n-2x-2y$$$ positions have $$$s[i] = t[i]$$$. Now lets choose these $$$2x+2y$$$ positions out of $$$N$$$. Lets deal with these positions from now on....

Visualisation of this problem as bracket sequence

  • This problem reduces to finding number of bracket sequences of length $$$2x+2y$$$ such that longest regular bracket subsequence is of length $$$2x$$$. This longest regular bracket subsequence refers to $$$C_1$$$ operation (the cheaper one $$$C_1 \lt C_2$$$)

  • The opening brackets refers to $$$s[i] t[i] = 01$$$ and closing brackets refer to $$$10$$$

  • This could be visualized as inserting any number of balanced regular sequences of total lengths $$$ = 2x$$$ anywhere between $$$)))))... .... ((((($$$ of length = $$$2y$$$

  • I need to allocate some balanced bracket sequences to $$$2y + 1$$$ places such that total length of bracket sequence is $$$2x$$$

  • This can be solved with catalan convolution described by an simple formula

in this blog https://mirror.codeforces.com/blog/entry/87585

My Submission: https://www.codechef.com/viewsolution/1151130441

→ Reply
  • »
    »
    13 months ago, hide # ^ |
     
    Vote: I like it +10 Vote: I do not like it

    I had an N^2 solution too, which uses the idea that the number of )( brackets we have to choose is equal to the minimum prefix sum of the sequence.

    I believe the above lemma should be true, but i did not test it. After that, you can bruteforce on the minimum prefix sum and it becomes a path counting problem, standard with reflection technique.

    → Reply