kalpitk's blog

By kalpitk, history, 6 months ago, ,

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.

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.

There are prizes worth ₹30K to be won.

Problem setters and testers include vntshh Seven kr_abhinav pushpendra1997 gi_sha dc99 and kalpitk

• +80

 » 6 months ago, # |   +12 Do "prizes" mean Codechef laddus?
•  » » 6 months ago, # ^ | ← Rev. 2 →   +3 I don't think so. It should be cash prize.But still lets will wait for official reply from organisers.
•  » » 6 months ago, # ^ |   +27 Codechef laddus are a "proper subset" of the prizes :PWe do have cash prizes for overall winners.
 » 6 months ago, # |   +3 How to Solve "Optimal Splitting" ??
•  » » 6 months ago, # ^ | ← Rev. 2 →   +17 My idea (untested):two cases if one cut is a parent of another. 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.
 » 6 months ago, # |   +9 How to solve "Misplaced Signs" ?
•  » » 6 months ago, # ^ | ← Rev. 3 →   +19 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.
•  » » » 6 months ago, # ^ | ← Rev. 2 →   +6 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.
•  » » » 6 months ago, # ^ |   +3 Thanks , the addition and subtraction of the a^2 term wasn't very intuitive. But the solution is pretty clean.
•  » » » » 6 months ago, # ^ |   +11 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).
 » 6 months ago, # |   +12 Nice contest guys , also could someone explain how to solve longest xor sequence question
•  » » 6 months ago, # ^ | ← Rev. 3 →   +1 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
•  » » » 6 months ago, # ^ |   0 Thanks a lot , got it
 » 6 months ago, # |   -18 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.
 » 6 months ago, # |   0 can someone please explain the idea for subset numbering problem?
•  » » 6 months ago, # ^ |   +4 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.
 » 6 months ago, # |   0 Can someone explain how to approach and think about Optimal Splitting Problem https://www.codechef.com/COME2019/problems/OPTSPL Thanks in advance :)
 » 6 months ago, # | ← Rev. 2 →   +3 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
•  » » 6 months ago, # ^ |   +3 Can you explain your edge construction? Not sure I quite understand
•  » » » 6 months ago, # ^ | ← Rev. 2 →   +3 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).
•  » » » » 6 months ago, # ^ |   +6 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 | ------------------------------------------------ 
•  » » » » » 6 months ago, # ^ |   +16 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! :)
•  » » » » » » 6 months ago, # ^ |   +6 Glad that you enjoyed the contest :D
 » 6 months ago, # |   +29 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?
•  » » 6 months ago, # ^ |   0 Will I be able to make it to 5 stars ?
•  » » 6 months ago, # ^ |   0 Probably in a few days, once plagiarism checks get over.
•  » » » 6 months ago, # ^ |   +2 Cool
 » 6 months ago, # |   +20 Sir, when the codechef ratings will be updated ???
 » 6 months ago, # |   0 It was a great contest, can someone provide some insights on how to solve "Some Impact".