kalpitk's blog

Invitation to Code Mélange V (Rated for All on Codechef)
By kalpitk, history, 6 years ago, In English

Hey all!

We're glad to announce the 5th edition of Code Mélange, a 4 Hour algorithmic contest to be hosted on Codechef organized by IIT Indore and sponsored by Arcesium.

Code Melange V

The contest starts on 9PM IST, 14th April, 2019, and ends on 1AM IST, 15th April, 2019. Check out the timings for your timezone here. The contest is ACM styled, will consist of around 10 problems of varying difficulty, and will be rated for both div 1 and div 2 participants.

Link to the Contest

There are prizes worth ₹30K to be won.

Problem setters and testers include vntshh 7dan kr_abhinav pushpendra1997 gi_sha dc99 and kalpitk

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

»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Do "prizes" mean Codechef laddus?

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

    I don't think so. It should be cash prize.
    But still lets will wait for official reply from organisers.

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

    Codechef laddus are a "proper subset" of the prizes :P
    We do have cash prizes for overall winners.

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

How to Solve "Optimal Splitting" ??

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

    My idea (untested):

    two cases

    1. if one cut is a parent of another.

    2. if two cuts are separate.

    fix one of the cuts.

    for each of the case we can maintain a set over subtree sizes of relevant other cut.(use dsu on trees for this maybe simpler thing exist but dsu on trees is straight forward).

    Now if we try to open the modulo signs , we have 8 cases. I will explain for one case and rest similarly.

    Now we have only one variable in the equation, and we get some restrictions on that variable based on the three signs we assigned. now after opening the signs we get something like ax+b with p < x < q. x must be in the defined set. we can do a lowerbound or upperbound query and find it. take min among all.

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

How to solve "Misplaced Signs" ?

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

    My solution (untested):

    so it is a+bc = ab+bc. now c = (a-ab)/(a-b).

    So (a-ab)/(a-b) must be integer. Now (a^2 — ab — a^2 + a )/(a-b) must be integer.

    a + (a-a^2)/(a-b) must be integer.

    (a-a^2)/(a-b) must be integer.

    a-b must be factor of a^2 — a. And for every factor we get a unique b.

    So now we need count of factors of a*(a-1).

    Now gcd(a,a-1) = 1, hence ans is 2*factor_cnt(a)*factor_cnt(a-1) (the 2 is to consider the sign of the factor Thanks aryanc403).

    Maybe handle some cases like a=b separately.

    Edit: I forgot to add about calculating factor cnts. there is a blog on cf about it.

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

      Thats correct. People who got AC told me this soln. ans is 2*factor_cnt(a)*factor_cnt(a-1) . Only handle a=1,a=0 => -1.

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

      Thanks , the addition and subtraction of the a^2 term wasn't very intuitive. But the solution is pretty clean.

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

        Above solution is correct. I rather converted the equation to (b-a)(c-a) = a(a-1) Now the answer is number of ways to distibute the divisors to (b-a) and (c-a) which turns out to be 2*divisors(a)*divisors(a-1).

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

Nice contest guys , also could someone explain how to solve longest xor sequence question

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

    Here is my approach:

    The key idea is that we can store all $$$n^2$$$ pairs of xors, and for each index $$$i$$$ we store all xors ending at that index (meaning $$$a_i \oplus a_j$$$ for all $$$j < i$$$), along with the length of the largest non-decreasing subsequence with the last two elements being $$$a_i$$$ and $$$a_j$$$ (so for each index, we have a vector of pairs).

    Suppose that we are at index $$$i$$$ and we have to find these pairs for all indices $$$j < i$$$. We want $$$a_i \oplus a_j \ge a_j \oplus a_k$$$ where $$$k < j$$$. Recall that we have all such xors stored for index $$$j$$$, so we use that information. We consider all pairs in the vector of index $$$j$$$ wherein the first value (the value of the xor of last two elements) is less than or equal to $$$a_i \oplus a_j$$$... we take the one with the maximum second value of the pair, and we add $$$1$$$ to that to obtain the new longest non-decreasing subsequence with the largest element being $$$i$$$ and the second largest being $$$j$$$.

    $$$\displaystyle dp_{i, j} = 1 + \max_{k \lt j, ~ a_i \oplus a_j \ge a_j \oplus a_k} dp_{j, k}$$$

    To speed this up, once you're done with computing all $$$dp_{i, j}$$$ values for a particular index $$$i$$$, sort them by the xor-value, and replace pairs $$$(x_i, mx_i)$$$ by the prefix maximum. So now, the second element of the pair denotes the longest increasing-subsequence for all xors that are $$$\le x_i$$$. Now to compute $$$dp_{i, j}$$$, take $$$x = a_i \oplus a_j$$$, then binary search in the $$$j$$$ array for the largest entry that has its xor-value $$$\le x$$$. Since we already have computed the prefix maximum (the longest increasing-subsequence ending at $$$j$$$ with xor-value $$$\le x$$$ instead of exactly equal to $$$x$$$), we simply take the second value of the pair and add $$$1$$$ to that.

    Here is my code: https://www.codechef.com/viewsolution/23986152

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

People passed the problem A small array with wrong solutions, no action was taken, not even rejudging even after informing at a very initial stage of the contest.

Disappointed.

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

can someone please explain the idea for subset numbering problem?

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

    Major idea:

    Build a graph where each node represents a possible remainder modulo N. Build edges from node $$$x \rightarrow (x*10 + dig)\mod N$$$ whee dig is one of the possible digits. Now, do a bfs on this graph and find the shortest number of edges required to state 0 for each node. In another pass, pick the next number greedily using the above information, and if there is a tie, pick the smaller number first.

    Official editorial will be released in a short time.

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

Can someone explain how to approach and think about Optimal Splitting Problem https://www.codechef.com/COME2019/problems/OPTSPL Thanks in advance :)

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

Can someone help me out in problme SUBNUM?
My approach was to make a graph of numbers and add edge from i to j when
j = (n*d) + (i/10) for (d = 0 to 9) and (j%10) is in required set.
First node i push in my queue is 0 and continue till i reach a node with value x such that all digits in x are from required set.
I am getting WA.
Link to my solution : https://www.codechef.com/viewsolution/23993965

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

    Can you explain your edge construction? Not sure I quite understand

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

      I am trying to create the answer ensuring all the digits are from given set and maintaining the multiplicand. At the end i use smallest multiplicand to find the answer.
      When i have a number N and multiply it with M having digits (abc). First N is multiplied by c (evaluates to say x), the last digit of x will propgate to answer (at units place) and (x/10) remains, no we multiply N with b and add x/10 to it (say we get y), the last digit of y propagates to answer (at tens place) and y/10 remains. Continuing this approach i stop when all the digits in remaining value are from given set. (The logic is more intuitive if we try writing the multiplication as on paper using school multiplication method , multiplication digit by digit).

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

        The issue lies within the mark array. For two different multiples, you might come across the same leading value, both of which are divisible by N. There does not seem to be any guarantee in your code that the first occurrence of a certain leading value would result in the smallest possible solution.
        I ran your solution across some random values and it did show up once, results of my simulation:-


        ------------------------------------------------  
i | check(nxt) | mark[nxt]     | nxts          |    
1 | 111166     | 0             | 1248393158361 |  
1 | 111166     | 1             | 6421327058361 |  
------------------------------------------------
        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +16 Vote: I do not like it

          Thanks alot! I figured out that error and started storing the min distance in the mark. Getting TLE now but hope to figure a way out. Thanks once more :D Amazing contest! :)

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

April Long Challenge has been over for almost 24hours now, the ratings have not been calculated yet? When will the rating-change effectively take place?

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

Sir, when the codechef ratings will be updated ???

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

It was a great contest, can someone provide some insights on how to solve "Some Impact".

→ Reply