Hello CodeForces Community!

Congratulations to all those who have cleared the SnackDown 2016 Qualifiers. We hope you are prepared for the Pre-Elimination Rounds. There will be two pre-elimination rounds and 1000+ teams ( *to be precise, the top 1000 teams and teams with number of problems solved equal to 1000th team* ) will be selected from each of the 2 rounds, Pre-Elimination Round A and Pre-Elimination Round B, who will further advance to the SnackDown 2016 Elimination.

The CodeChef SnackDown 2016 Pre-Elimination Round A begins tomorrow, at 9 PM IST, 4th June.

The problems have been set and tested by Cherrytree (Sergey Kulik), Antoniuk (Vasya Antoniuk), and me (kevinsogo, Kevin Charles Atienza). The translations are written by huzecong (Hu Zecong), Antoniuk (Vasya Antoniuk), VNOI Team, Cherrytree (Sergey Kulik), with PraveenDhinwa (Praveen Dhinwa) as contest admin. I hope you will enjoy solving the problems. Please feel free to give your feedback about the problems in comments below.

- Furthermore, this year,
**CodeChef will be inviting 52 teams (top 25 global + top 25 Indian + all Girl team + Indian school team) for the onsite finals**. Of these 52 teams, 32 teams (top 15 each Global & Indian + Girl + Indian school team) will get an all-expense-paid trip to India, while the remaining 20 teams will be provided with accommodation and local travel in India. However, if any of these 20 teams win the competition, their travel fare will be reimbursed as well. It’s a win-win situation.

Along with the cash prizes for Global Winners, there are special prizes for Best School Team, Best Girls team and Best Indian Team (the total cash prizes are worth $22,500).

- The winning team shall win a whopping cash prize of $10,000.
- Also, taking into consideration the previous discussions regarding the timing of online elimination round of the contest, the organizers have decided to reschedule the round.

**The new timings for the SnackDown 2016 Elimination Round are:**

In order to accommodate the new timings, they have also rescheduled the June Cook-Off 2016. And the new timings for the June Cook-Off are:

Date & Time: 26th June 2016, 21:30 Hrs IST to 00:00 Hrs IST

I hope you like the new timings and that will enjoy the contest till the very end. That will be all from my side for now. See you all at the contest.

Regards,

Kevin

It's nice to see more team competitions with onsites (especially w/o weird restrictions like VKCup; though there is one weird restriction here, about organizations)! I'm looking forward to participating in this, thanks for organizing.

However, there are a couple of concerns:

Elimination round is only a couple of weeks before the onsite; is it possible for 25 global teams to get Indian visas in such a short about of time? (I have no experience with Indian visas, just asking; typically it is difficult on such a short notice)

2000 teams in elimination round is a lot; are you sure Codechef is going to handle that many teams well? During the first hours of qualification round, it was essentially unusable.

@ilyakor we have done a bit of research about the Indian visa process before coming up with the dates and we are hopeful that we can get the visa within the time frame. Also, we will be communicating with all the global participants (who will be advancing to elimination round) regarding the documentation, this helps us to quickly proceed with the visa process just after the elimination.

Coming to the platform: we have fixed all the issues and looking forward to deliver a great contest.

Unfortunately, platform is not fixed for me. I can't even load problem statements now.

Check for errors in your console. I guess ur browser is old.

Any chance it will work soon? It doesn't work for half an hour already.

UPD. I don't know why, but it doesn't work in Safari, and works in Chrome.

hey, it is working fine, we have seen over 3000 submissions so far and no complaints. Could you please share a screenshot? Sometimes it happens due to some plugin which is installed in your browser.

Update: This can be due to the old version of your browser.

I don't think it's related to browser version, because it was working fine before, and even during the first 5 minutes of the contest (I was able to submit one problem in Safari).

hey, If you are still facing an issue in Safari. Could you please send us a screenshot with console open to snackdown@codechef.com?

Hi ilyakor,

Regarding your point of allowing team formation only from same organization, we will take a review over it after the end of this Snackdown, and will decide whether it requires changes.

Primarily, our reason for allowing team formations from same organistion is historic in the sense that we started Snackdown with keeping in mind ACM ICPC preparations for Indian teams. But, now as we invite participants from all over the world and also from various channels, like high school students, university students (both eligible/ineligible for ICPC) and past university students, we are open to changes in this.

We will also have a public opinion regarding whether we should make a fixed/predecided distribution of high school students, university and non-university students in the onsite participation or not.

Thanks a lot for your feedback, ilyakor!!

How many computers per team could we use during Elimination Round?

@zeliboba there is no restriction as such for all the online rounds. For ex: If you and your partner are at two different places during the contest, you can login with your individual accounts and submit on behalf of your team. Coming to the final onsite round each team will be given a single computer to compete.

Reviving this old thread: "Coming to the final onsite round each team will be given a single computer to compete" — does this mean each team needs to bring their laptop, or are the computers provided by the organizers? In the latter case, a couple of very interesting questions arise:

(also, is all of this specified somewhere in the rules? I searched but failed to find anything...)

Thanks in advance for your reply! (and thank for organizing this competition)

I am not sure of this year's snackdown but last year we were allowed to carry prewritten code which we had to mail codechef before the contest. And you can find last year's contest environment here , but this year we didn't recieve any mail regarding contest environment and stuff yet so i am not sure.

Thanks for answering! <= 20MB of files + no Idea = no Java :( I hope this year environment limitations will be less strict.

We will be supporting Eclipse and IntelliJ Idea for Java. We will notify about the exact versions of these programs in a mail or a notifications to be sent in some time.

Gentle Reminder !! Contests starts in few hours. !!

90 is quite a lot for few :P

Oh, sorry. It should be few hours.

How to solve sharing candies ? All I could think of was that the minimum difference was zero and maximum difference was

abs(b-a), and to check for the least value which had natural number solution forx,ywithin that rangeUnable to parse markup [type=CF_TEX]

CF Tex is broken: Answer = min(abs(a-b) mod {gcd(c, d)}, gcd(c, d) -abs(a-b) mod {gcd(c, d)}

How to solve Chef and his study plans? Will there be editorials?

Let

next[i] denote the least value of right endpoint among all segments starting at some index ≥i. So for each query , you can find the answer using this array by doingL,R=input() , and thenL=next[L] + 1 whileL≤Rand increment answer in each iteration . But this isO(N) . To make this faster , use binary jumping .next[i][j] = the index we will be after jumping 2^{i}times. With this you can simulate this inO(log(n)) time withO(NlogN) precomputation . CodeNice code!

I guess the complexity for this is

O((M+Q) *logN)I handled the queries offline by sorting the starting points in reverse order with persistant segment trees.For current st,en if en < all en's visited till now ,root[st]=root[en+1] ,otherwise root[i]=root[i+1] where in segment tree I have frequency of all end points. code

Just in case you have missed, the editorials are available at: https://discuss.codechef.com/tags/snckpa16,editorial/

Your's question i.e. Chef and his study plans can be found out at https://discuss.codechef.com/questions/81931/subseg2-editorial

Can anyone explain the solution of Longest Increasing Subsequences .

My solution: let's implement just two operations: * 2 and + 1. Here they are:

permutation}(M+ 2)(M+ 1), whereM=max({permutation})M+ 1)...(M+LEN){permutation}, whereLENis the length of LIS of {permutation}(take a pen and try out some examples here, understanding how and why these operations work is significant)

So we can for any given N we can generate the sequence with N LISes with this recursive function:

But it is not enaugh because the length of the result sequence will be more than 100 in some cases. So let's generalize the operations:

Kinstead of * 2K- 1) instead of + 1You can do it on your own and check yourself here (sorry for white text, but spoilers don't work with markup):

*

K<=> {permutation}(M+K)...(M+ 1)+

Z<=> (M+Z)...(M+ 1) (M+Z+ 1)...(M+Z+LEN- 1){permutation}Now when, for example,

K= 7 all result sequences forn= [1, 100000] will fit in 100 numbers.Time complexity is

O(T*log^{2}(N))Isn't it log^2 n per test?

Sure, thx!

Could you explain your solution for number 11111 in base 7(it's less than 7^5 which is less than 1e5). As far as I understand it will go like 10-11-110-111-1110-1111-11110-11111 and it'll have length of 7-14-21-42-49-98-105-210 respectively

For 11111

_{7}= 2801_{10}n will really go like 1-10-11-110-111-1110-1111-11110-11111, but length will go like 1-8-10-17-20-27-31-38-43.Here's step-by-step explanation:

Sorry for hardcoded width but otherwise it looks ugly18 7 6 5 4 3 29 101 8 7 6 5 4 3 217 16 15 14 13 12 1118 19 209 10 1 8 7 6 5 4 3 2 17 16 15 14 13 12 1127 26 25 24 23 22 2128 29 30 3118 19 20 9 10 1 8 7 6 5 4 3 2 17 16 15 14 13 12 11 27 26 25 24 23 22 2138 37 36 35 34 33 3239 40 41 42 4328 29 30 31 18 19 20 9 10 1 8 7 6 5 4 3 2 17 16 15 14 13 12 11 27 26 25 24 23 22 21 38 37 36 35 34 33 32Thanks, I see where my calculation went wrong

short problem analysis for all the SNCKPA16 problems: https://aleigorithms.wordpress.com/2016/06/05/snackdown-online-pre-elimination-round-a/

How did you came up with the equations in the last problem ?

ok I got it and I will analyze it for anyone who didn't find it yet.

First of all take as example the list [1, 2]. After 1 sec it will be [1, 3, 2] etc.. If you keep the sums you will notice that at first it is (a+b) (logic)! After that it is (a+b)*2, after (a+b)*5, so I am going to iterate the numbers that we multiply the started sum. [1, 2, 5, 14, 41, ....] Now you can notice that to reach to ith number we need to add ith-1 + 3^m 1 + 1 = 2, 2 + 3 = 5, 5 + 9 = 14, 14 + 27 = 41 .... so we take the recursive relation an = an-1 + 3^(n-2). To solve that we break it in an = an-1 and F(n) = 3^(n-2) To solve that we use the "recursive linear homogeneous" theorem and we are done with that equation: an = 1/2 + (3/2) * 3^(n-2) You can check it that it is correct. Lets say we want a2, then a2 = 1/2 + (3/2) * 3^0 = 1/2 + 3/2 = 2 a3 = 1/2 + (3/2) * 3 = 1/2 + 9/2 = 5 ... So we found the equation !!! That equation is the same the guy use above in his editorial, I checked it. With a little difference, he uses indexed=0 for m, but my equation use indexed=1

What does 1000+ teams(to be precise, the top 1000 teams and teams with number of problems solved equal to 1000th team ) mean ?

Many teams have solved problems equal to the 1000th team.

Do all of them qualify?