Invitation to CodeChef November Long Challenge 2018 sponsored by ShareChat!

long-contest
nov18

#1

Hello CodeChef Community!

It’s time to gear up for CodeChef’s November Long Challenge sponsored by ShareChat! 10 days of coding fun plus opportunities to work at ShareChat! More details can be found on the contest page.

Joining me on the problem setting panel are:

  • Admin: mgch (Misha Chorniy)
  • Problem Tester: pupiler (Zhong Ziqian)
  • Editorialist: taran_1407 (taran_1407)
  • Problem Setters: wxh010910 (Xiuhan Wang), bciobanu (Bogdan Ciobanu), altruist (Denis Anishchenko), teja349 (Teja Vardhan Reddy), melfice (Alexander Kulkov), smelskiy (Danya Smelskiy), Shivam Gupta, hmrockstar (Himanshu Mishra),
    sshhhh (Sumegh Roychowdhury)
  • Statement Verifier: xellos0 (Jakub Safin)
  • Russian Translator: gomelfk (Fedor Korobeinikov)
  • Mandarin Translator: huzecong (Hu Zecong)
  • Vietnamese Translator: VNOI Team
  • Hindi Translator: Akash Srivastava
  • Bengali Translator: Mohammad Solaiman (Mohammad Solaiman)

Contest Details:

Time: 2nd November (1500 hrs) to 12th November 2018 (1500 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

Contest link: www.codechef.com/NOV18

Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.

Prizes:
Top 10 performers in Global and Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. First to solve each problem except challenge - 100 Laddus. Know more here: https://www.codechef.com/laddu. (For those who have not yet got their previous winning, please send an email to winners@codechef.com)

Good Luck!
Hope to see you participating!!
Happy Programming !!
It shouldn’t be like Oct Long!!

EDIT - Contest Highligts can be found here


#2

Warning - Weak TC ahead. xD


#3

If someone just attempts non-scorable problems, then will the contest be rated him?

I mean if I just solves div2 problems not part of div1, will the contest be rated for me?

@admin @vijju123


#4

@admin Request to extend Long challenge by atleast 2 days
due to diwali holidays in india, most of the indian students went their home to celebrate diwali and its quite difficult to get time in between diwali festival at home. After diwali festivals, students started solving long challenge but now only 1 and half day left.

So @admin plz extend ongoing long challenge 1-2 days so that one can give full effort.


#5

Hello Guys. I hope you all had a fun solving problems of November Challenge. So, time for Editorials, Editorials for problems other than RECIPES, MAXDTREE, CHEFEQUA, and BINSTR has been posted (will be available as soon as moved to public by admin). I’ll try to complete these editorials too, as soon as I can. For now, I am sharing brief setter’s notes for these problems.

RECIPES

Click to view

The solution is based on a Monte-Carlo false-biased algorithm, an algorithm which always answers correct when the answer is false, but it has a probability of failure when the answer is true.

For each base recipe we’ll asign a random vector from F_{2^{64}}. The other recipes will be written as the sum of R_1, R_2, … R_{p-1} and R_p’s vectors.

In a query we’re interested if the set of vectors is linearly independent. This can be done with gaussian elimination in O(K^2) time.

For K <= 15 a single run of this algorithm suffices, whilst for K <= 30, in practice, the algorithm must be run 5-10 times.

MAXDTREE

Click to view

Firstly, I want to solve this task:

You have number 1 <= N <= 10^1000 and you have to find out if it’s belong to max digit sequence or not. Let’s define function dp(md, ld, len) = y, where y is the difficult thing. Let’s consider some process - you have number of kind 10000…(ld), where ld - is last digit of number with length len, first digit is 1 and other digits are 0. Let’s increase this number (let’s denote it by the curr) on value equal to max(md, maxDigit(curr)), where curr - our current number, md - parametr from dp(md, ld, len). In some moment we will have number with length equal to len + 1 and looks like 10000…(y), where y = dp(md, ld, len). How to calculate y, it’s very easy. Let’s consider you have counted all states with length <= len - 1 and now you want to calc dp(md, ld, len). Firstly, we will forget about first digit at the moment, we can look at state dp(max(md, 1), ld, len - 1) = y2, it’s obviously that on some moment of iterations that add to our number max(md, maxDigit(curr)) curr will be equal to 2000…(y2), after that we will look at state dp(max(md, 2), y2, len - 1) = y3 and go on. So, dp(md, ld, len) = y10 and will be calculated in 10 operations.

After we calculated all states of our dp, we have to check if N belongs to max digit sequence. We can do it in same way that we processing our dp, firstly we will first member of max digit sequence which length equal to len(N), it looks like 100…ld. Let’s fix ld, after that, we can jump over states of dp. Firstly, we will consider dp(1, ld, len(N) - 1) = y2, after that we will consider dp(2, y2, len(N) - 1) and so on while md not equal to the first digit of number N, after that we will turn to dp(N[0], y10, len(N) - 2) and do same things. In the end we have to compare last y10 digit and N[size(N) - 1] digit, if they are equal, then the number belongs to the sequence, otherwise there is no. So we have O(N * 1000) solution.

We can solve main task using supporting function dp(md, ld, len).

Let’s denote function f(v, len, md, fd) - cnt of members of max digit sequence, which satisfy all these conditions:

  1. We made decision about all vertices u such that tin(u) < tin(v) if we take vertex of this kind in our subset or not (now we are making decision about v)

  2. md = maximum digit of all taken digits

  3. We will still make decision for exactly len vertices

  4. last len digits of this member is equal to 000…(ld)

We will send current state to other states of our dynamic programming. (index[v] - index of vertex v in asceding tin array, order[] - tin asceding array).

f(order[index[v] + 1], len - 1, max(md, digit[order[index[v] + 1]]), X) += f(v, len, md, fd), where X is result of jumping over dp(md, fd, len - 1) = y_2, dp(max(md, 2), y_2, len - 1) = y_3 to y_k where k = digit[v], so X equal to dp(max(md, k - 1), y_(k-1), len - 1). (We considered case when we take next vertex in order array). If we wan’t to take it, we have to skip all subtree to satisfy condition if we take i we have to take p_i, it’s obviosly that subtree is subarray of order array, so we should go to order[index[v] + size[v]] where size[v] is size of subtree with root v. In this case we will have this addition:

f(order[index[v] + size[v]], len, md, fd) += f(v, len, md, fd). The answer is sum f(v, 0, md, digit(v)) where v and md can be arbitrary. So, we have (N^2 * 1000) solution.

I know it might seem a bit complex for now. I’ll try to simplify this in editorial

CHEFEQUA

Click to view

consider generating function of C: C(x) = \sum \frac{b_i}{1-a_ix} = \frac{\sum b_i \prod_{j eq i} (1-a_jx)}{\prod (1-a_ix)}

let P(x) = \prod(1 - a_ix) , then C(x)P(x) = \sum b_i\prod_{j eq i} (1 - a_jx)

let Q(x) = C(x)P(x), x = \frac{1}{a_i} then Q(x) = b_i\prod_{j eq i}(1 - \frac{a_j}{a_i})

use multipoint evaluation to calculate Q(x) for each x = \frac{1}{a_i} then what we need to do is calculating \prod_{j eq i} (1 - \frac{a_j}{a_i}) , we can do it using a method like multipoint interpolation

the time complexity is O(n\log^2 n)

BINSTR

Click to view

Let’s create a new array B of length N - a permutation of numbers from 1 to N. Let pos (i) be a number j such that B [j] = i. Then, if pos (X) < pos (Y), then A [X] <= A [Y].

Let’s get the function to solve (L, R, L, R, bit, X) that will solve the next task. Let’s for all the numbers in the array A and also for the number X remove all bits that are older than the bit bit. Then you need to find a number C (L <= C <= R) such that L<= B [C] <= R, and A [B [C]] XOR X is maximally possible. If there are several possible options, then among them it is necessary to choose a number with a minimum B [C]. This function assumes that all bits higher than bit a bit are equal for all A [B *] numbers (L <= i <= R).

How will our function work?

If bit = -1, then all the numbers in the segment L…R are equal, and we need to find a number i (L <= i <= R) such that B *> = L` and B * is minimal.

We can do this with a tree of segments.

Otherwise, it is advantageous for us to choose the number for which the value of a bit is bit back to the value of a bit bit in the number X. If there is no such number, then choose the same bit. Then, if we want to set the bit 0 here, we need to choose the maximum number K (L <= K <= R), such that the bit bit of the number A [B [K]] is 0. Then you need to check that on the segment L …K there is at least one number i, such that L <= i <= K and L<= B * <= R. Otherwise, select bit 1. If we want to set bit 1 here, we need to choose the minimum number K (L <= K <= R) such that the bit bit of the number A [B [K]] is 1. After that you need to do the same checking that with bit 0, if it is not correct, then select bit 0 here. Thus, we go either to solve (L, K, L, R, bit-1, X) or to solve (K, R, L, R, bit-1, X).

How to apply this feature to our solution? We have two options.

  1. All numbers from the segment L…R of the array A have a record length not greater than the length of the record of the number X. Then the answer to the query is

solve (1, N, L, R, record length of the number X, X);

  1. There is at least one number from the segment L…R of the array A, which has a record length greater than the length of the record of the number X.

Note that in this case such numbers are more advantageous for us than numbers that have a record length less than or equal.

Find the maximum number of K, such that L <= B [K] <= R. Then we find the minimum number K, such that all bits of the number A [B [K]] except for len (X) the least significant bits are equal to the bits of the number A [B [K]] (len (X) is the length of the record of the number X). Then the answer to the request is

solve (K`, K, L, R, len (X), X).

All operations can be performed using various modifications of the segment tree.

Please bear with me, Pardon for delay, Thanks.


#6

Official contest statistics and interesting highlights by The Chef himself :stuck_out_tongue: :slight_smile: -

https://blog.codechef.com/2018/11/16/competition-recaps-in-case-you-missed-it-here’s-what-went-down-at-the-november-long-challenge-2018/

Credits - @teenage_witch :slight_smile:


#7

Let’s see who win the race. @admin or @taran_1407. Laddu or Editorials. xD


#8

No it will be unrated in this case.


#9

@lakh are you sure about this? have you ever done this?


#10

Its not rated for you, and your participation is also not considered.


#11

But it will be considered for plagiarism checks, and if caught, you will be penalized.


#12

Laddus are yet to be credited in my account for Oct18a. I was ranked 16 (in Indian Category). I mailed them but got no reply :frowning:
Anyone who got laddus ??


#13

@aryanc403, you may have to wait for around 1.5 months, I got my laddus (for some challenge), during the last days of next challenge…


#14

10 days is a lot of days I guess :stuck_out_tongue:


#15

Lol!!!


#16

Ab toh aadat ho gyi hai :stuck_out_tongue:


#17

See you on announcement page of 100th CookOff.


#18

Taran, afaik, has already written editorials. @admin is yet to review and move them :stuck_out_tongue: