mgch's blog

Invitation to CodeChef March Lunchtime 2018!
By mgch, history, 7 years ago, In English

Hello CodeForces Community! Chef's next contest is just around the corner and I'd like to invite you for the same, the March Lunchtime 2018. Have a helping of Chef's challenges and solve all 6 contest problems to top the charts!

I hope you will join your fellow programmers and enjoy the contest problems. Joining me on the problem setting panel are:

  • Problem Setter:mgch (Misha Chorniy)
  • Problem Tester: Lewin (Lewin Gan)
  • Problem Editorialist: adkroxx (Adarsh kumar)
  • Problem Admin: kingofnumbers (Hasan Jaddouh)
  • Statement Verifier:Xellos (Jakub Safin)
  • Russian Translator: CherryTree (Sergey Kulik)
  • Mandarin Translator: huzecong (Hu Zecong)
  • Vietnamese Translator: VNOI Team

I hope you will have a great time solving them. Your feedback on the problem set is most welcome in the comments below after the contest.

Contest Details:

Time: 31st March 2018 (1930 hrs — 2230 hrs). (Indian Standard Time — +5:30 GMT) — Check your [timezone]https://www.timeanddate.com/worldclock/fixedtime.html?msg=March+Lunchtime+2018&iso=20180331T1930&p1=44&ah=3.

Contest link: https://www.codechef.com/LTIME58

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. Know more here: https://www.codechef.com/laddu.

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

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

I think this is the first time when there will be 6 problems in LunchTime.

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

Codechef site down??

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

    Works fine for me, but I can't see any problems.

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

      Same here. Sometimes 500 internal server error. Sometimes it loads but there is no problems that can be viewed.

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

Is it just me or nobody is able to see the problems ?

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

can't access problems , server down :(

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

Servers down.

What a classic codechef mess-up.

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it -16 Vote: I do not like it

I think we all should stop reloading the page to reduce load from their servers.

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

Atleast change the contest time by half hour so that problems don't appear suddenly.

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

15 minutes have passed no responses from them :(

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

    They replied: "We are facing some issues with our servers and hence the problems are not visible on the contest page and practice section right now. Please bear with us."

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

Seems like April has arrived a day early this year xD

→ Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it -25 Vote: I do not like it

BeautyofCodechef

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

Is div2 having the same problem?

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

It's UP

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

Seriously, after 40 minutes they just put it up without warning. That's ridiculous. Should've just turned it off and postponed with an hour. Was everyone expected to eagerly refresh for 40 minutes straight?

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

    yaa

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

    Yes, I would do the same if I only knew how the contest begins. Sorry for that. I really have no idea what's going on :(

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

    It was considered, but somehow they already got 4-5 submissions for easier problems before the bug was completely fixed. That way, damage was done- it couldnt be kept rated. The best that could be done was to hold an unrated round later.

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

Contest page is not showing correct number of accepted submissions(for div 1)!

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

Is it showing for anyone??

"You will have to login to check the contents on March Lunchtime 2018 Division 1 contest page.

Note: This is a restricted contest. It will only be accessible to users who are provided the permission. In case of any queries, please get in touch with the contest organizer."

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

Massive error in judgement there :(

Should have postponed it for an hour or so. First they display the problems all of a sudden without fixing the full issue. And now it seems the contest is "restricted". At least I am not able to see the contest page anymore.

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

I solved 3 problems and they made the contest restricted. It would have been a good one for me. :(

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

Wow! Final Exam tomorrow and ruined almost one and a half hour for nothing! -_-

Untitled

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

Site offline now I guess.

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

mgch: questions are still accessible on direct link of the questions, please disable it.

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

The submit button for 1st problem ZOZ is not visible on problem page, Is anyone also facing same issue.

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

In partitions problem can we solve it using randomisation. ? is there any other simpler solution for it?

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

    I think it focuses on the fact that there are only O(n1 / 3) divisors of a number!

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

      Nope,my idea is to iterate over all k and check if all multiples of total/k till kth multiple are present among prefix sums or not.this will take O(NlogNlogN) with naive implementation but there can some optimisations done.Though I had not submitted ,this seems good to pass because in practice it should run much faster(Yeah I am sorry.May be to analyse any better may be your fact is required).

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

        Yeah right! My one TLE's one case and yours passes in 0.2 second!

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

          So you coded seive way and submitted?

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

            In both solutions I am checking for k iff its a multiple of sum. So, complexity should be O(n1 / 3) * (Accumulated work for divisors)

            First solution: Its O(n) implying O(n4 / 3)

            Second solution: Uses prefix sums implying better than first xD

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

              why the complexity of Accumulated work for divisors is O(n^1/3)? i think it should be like O(sum^1/3).

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

                Yeah right! Though its not the accumulated work for divisors. Total complexity should be sum1 / 3 * (Accumulated work).

                Infact in the first term sum1 / 3 gives upper bound on all the divisors of sum but we are only considering those ones which are less than n.

                UPD: Author has explained it better about bounds on this below!

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

I was wondering if anybody was able to solve the last question of Div 1 — Queries on Tree on their own. The editorial cited a research paper. So, I'm guessing it was not a very well known algorithm. Was anybody able to solve the problem on their own in a different way ?

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

    where are the links for the editorials, they are not in the usual place .

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

      Here is it: https://discuss.codechef.com/tags/ltime58/

      Few words about ARRP:

      I can bound teja349's solution as O(N sqrt(N) * checking) using fact about Euler's function. But it's really hard to create test against it. If it's even possible.

      My solution: O(N log N + N log A)

      Let's create partial sums for every prefix, i.e. S[i] = A[1] + ... + A[i]

      Now, when partition for K is possible?

      If exists S[n] * 1 / K, S[n] * 2 / K, .. S[n] * K / K in the set of partial sums.

      What does that mean for S[n] * i / K(i = 1..K) ? It's equivalent S[n] * i / K = S[j] (for some j=1..N) <-> i / K = S[j] / S[n]. A[i] >= 1, hence all the values of S[i] / S[n] are distinct.

      Let's use reverse thinking, if we know the value of X / Y(irreducible fraction) = S[i] / S[n], how to find all values of K where it will be counted? Obviously, it will be counted for values Y, 2*Y, ..., [N/Y]*Y.

      So, now we have the problem with denominators of irreducible fractions. And it sounds like the next one: we have the numbers Y1, ..., YN. We need to find for every K for how many Yi(K % Yi == 0), denote it as cnt[K]. It can be done with some application of Sieve of Eratosphenes. And a partition for K is possible iff cnt[K] == K.

      The complexity is N log A(finding gcd for making the fractions S[i]/S[n] irreducible) and N log N(N + N / 2 + .. + N / N) for Sieve of Eratosphenes.

      Below is my code for ARRP(it's absolutely clear): https://pastebin.com/SUHJvQUt

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

        Thank you for the link and your explanation. I'll look at it.

        This was my favourite LunchTime contest so far. I really liked that there are more problems now that it's unrated.

        What is your opinion about the last problem of Div 1 ? Was it an impossible problem or is it possible for people who did not read that research paper to solve it ?

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
          ← Rev. 4   Vote: I like it 0 Vote: I do not like it

          Glad to hear it!!

          I guess you're asking about another approach. I'm not sure in this approach, probably you can solve it with sqrt-decomposition by queries and for every sqrt(Q) queries compress the tree in O(sqrt(Q)) (nodes+LCA of them)(nodes which will be used in the next O(sqrt(Q)) queries), then you can solve it in O((Q + N) * sqrt(Q) * log(N)) but with huge constant.

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

            Can you tell me how to solve the question Queries on Trees, for arrays ? I don't know how to solve that simpler question.

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

            I don't know if this is the right place but can you answer this question of mine regarding the problem GQR : Link

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

        I liked how you transformed it to a question of counting irreducible denominators.

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

        Heyy,Thanks

        Actually I dont know what I was thinking while analysing complexity.I just thought that checking was similar to sieve and thought nlogn and(logn) for checking. But after your comment I realise my analysis was wrong.But anyways it seems breaking that solution is not possible.

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

          There is no problem :)

          Tester thought that this approach has complexity O(N log N). Even me at the very beginning. It's quite confusing. The most crucial optimization is check if SUM % i == 0.

          → Reply