kevinsogo's blog

By kevinsogo, history, 8 years ago, In English

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

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

| Write comment?
»
8 years ago, # |
  Vote: I like it +81 Vote: I do not like it

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.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    @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.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

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

    • »
      »
      »
      8 years ago, # ^ |
      Rev. 2   Vote: I like it +5 Vote: I do not like it

      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.

      • »
        »
        »
        »
        8 years ago, # ^ |
        Rev. 2   Vote: I like it +5 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          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).

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    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!!

»
8 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

  • »
    »
    8 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    @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.

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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:

      • What IDE's are going to be installed? E.g. for Java programmers IntelliJ Idea is crucial, writing Java in Vim would be quite suboptimal;
      • Is prewritten code allowed? If problems will be in the same spirit as on elimination round (i.e. requiring non-trivial data structures like persistent segment tree), this point is quite important.

      (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)

      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

»
8 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

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

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 for x, y within that range

  • »
    »
    8 years ago, # ^ |
    Rev. 8   Vote: I like it -10 Vote: I do not like it

    Unable 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)}

»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

  • »
    »
    8 years ago, # ^ |
    Rev. 2   Vote: I like it +20 Vote: I do not like it

    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 doing L, R = input() , and then L = next[L] + 1 while L ≤ R and increment answer in each iteration . But this is O(N) . To make this faster , use binary jumping . next[i][j] = the index we will be after jumping 2i times. With this you can simulate this in O(log(n)) time with O(NlogN) precomputation . Code

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Nice code!
      I guess the complexity for this is O((M + Q) * logN)

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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

»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can anyone explain the solution of Longest Increasing Subsequences .

  • »
    »
    8 years ago, # ^ |
    Rev. 5   Vote: I like it +15 Vote: I do not like it

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

    •  * 2 <=> {permutation}(M + 2)(M + 1), where M = max({permutation})
    •  + 1 <=> (M + 1)...(M + LEN){permutation}, where LEN is 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:

    list<int> gen(int n) {
      if (n == 1) {
        return { 1 };
      }
      list<int> res = gen(n / 2);
      mulTwo(res); // * 2
      if (n % 2 != 0) {
         addOne(res); // + 1
      }
      return res;
    }
    

    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:

    •  * K instead of  * 2
    •  + 1,  + 2, ...,  + (K - 1) instead of  + 1

    You 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 for n = [1, 100000] will fit in 100 numbers.

    Time complexity is O(T * log2(N))

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Isn't it log^2 n per test?

    • »
      »
      »
      8 years ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        8 years ago, # ^ |
        Rev. 2   Vote: I like it +15 Vote: I do not like it

        For 111117 = 280110 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 ugly
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

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

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?