kostya_by's blog

September Mega Cook-Off 2015 on CodeChef
By kostya_by, history, 9 years ago, In English

Hi everybody!

I invite you to participate in the CodeChef September Mega Cook-Off at https://www.codechef.com/COOK62. The problemset of the contest is prepared by me.

I hope you will like the problems: some of them require outstanding algorithmic thinking, some of them require brilliant coding skills — anyway, I'm pretty sure, that no one will get bored during the contest. ;)

Time: 20th September 2015 (21:30 hrs) to 21st September 2015 (00:00 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

Details: https://www.codechef.com/COOK62

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.

The contest was prepared not only by me, but also by these amazing guys:

Prizes:

  • Top 10 performers in Global and Indian category will win a cool CodeChef T-shirt. (For those who have not yet got their previous winning, please send an email to [email protected])

  • Top 75 Indian performers will be provided with a reimbursement (for travel and registration) of upto INR 1500 for ACM ICPC 2015 regionals.

Good luck! See you on Sunday!

Note from contest admin:

Before we invite you to take part in this Cook-Off, let us take this opportunity on behalf of the engineering team at CodeChef, for the terrible experience that you had to go through at the last Cook-Off, which got unrated. And while we do this, we are completely aware of the fact that we have been making too many mistakes when it comes to Cook-Off and our apologies have also been on the rise. However, we have fixed a few things between then and now. And we are very hopeful that the same experience will not be repeated. Among many things that we have fixed, one major change will be the contest environment. We will be launching a much lighter version of the contest environment tonight. We hope you get a much better experience from now on. However, if there are any issues that you face in this environment, we request you to report them to us and we will fix them all.

UPD:

The contest starts in 30 minutes!

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

Comments Comments (28)
| Write comment?
»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

It was a really disappointing experience in the last round. I also don't think most people will participate as your time almost clashes with the next codeforces round which is 30mins after the start of the codechef round.

I don't know for others but it's definitely going to be a codeforces round for me come sunday

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

I think Indian college students will participate in codechef. Hope they don't get messed up this time!!

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

    Yeah just read that it's an ACM-related cook off. So i guess it would help with those preparing for the upcoming regionals.

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

I think it clashes with the next codeforces round.Isn't it possible to change the schedule?

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

I still don't get it, why TOP 75 INDIAN PERFORMERS will be provided with a reimbursement for ACM ICPC 2015. ICPC is a contest for college students only(as the name suggests), so they should give the reimbursement to TOP 75 COLLEGE STUDENTS(Indians obviously) not indian performers.

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

    Thats true. The reimbursement will be to top 75 Indian students who will reach the onsite regionals.

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

First weekend contest in nearly a month, and it gets moved back. Aw man..

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

Auto comment: topic has been updated by kostya_by (previous revision, new revision, compare).

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

Gentle reminder !! Contest starts under 5 minutes.

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

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

Could somebody give me an idea of how to approach "Super Numbers"?

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

    φ(p1e1... pkek) = p1e1 - 1(p1 - 1)... pkek - 1(pk - 1).

    Since we want phi divide n, we can cross out all piei - 1. That is, prime powers do not matter. So we need numbers n = p1e1... pkek such that (p1 - 1)... (pk - 1)|p1... pk.

    First note that n should be even (except n = 1), since φ(n) is even for n > 2. Then (p1 - 1)... (pk - 1)|2p1... pk, since (2-1) does not bother us in the left side. This is only possible if some (pi - 1) = 2, that is pi = 3 and no other primes are present.

    So we simply need to count numbers of the form 2e23e3, e2 ≥ 1, e3 ≥ 0. (count number 1 as special case). We can count by iterating over all e2 ≤ 59 and e3 ≤ 37.

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

    Write a bruteforce for finding such numbers. Look at the first few. Do you see a pattern? :D

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

Something strange with penalty times in ranklist: if you add them, the result you get is less than total time shown by (16 minutes) times (number of wrong attempts). And one of Fdg's times is 02:47:54, so penalty time for each problem already counts wrong attempts; anyway, it doesn't add up.

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

Very good contest... I had big problems with fourth task, but I managed to solve it 3 minutes before end of contest.

About tasks, personally I don't like the first task ( he is simply implementation), other tasks was very interesting for me.

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

    I didn't like third task,I didn't manage to solve it and from what somebody told me,is just observation...Every super number is made just out of prime factors 2 and 3.

    Fourth task was nice and the first two implementation.

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

      Also I like the fourth task at most. Very nice, easy idea with DP, but I had to spend a lot of time to solve it :)

      The second and third task wasn't something spectacular, but they were new for me.

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

Thanks for the nice contest! I expected the problems to be a bit tougher and a simple DP solution for the fourth problem (Reigns2) was a little surprise for me.

PS: didn't have enough time to look at Counting Subgraphs, seems it was a hard one.

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

    Thanks for your solution for the third problem :) I understood it very clearly.

    Also it seems to me that last year mega cook-offs were more interesting,like september 2014. But maybe the next cook-off will be better.

    I'm glad that the site works smoothly, I can put my whole attention on problems from now on.

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

    Do you have a proof why DP gives desired answer? I fail To prove that dp is what we need.

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

      Firsly I looked how to minimize the cost for k chosen cities.Of course,you sort them in decreasing order by B[i](cuz a[i] surely will be added and it doesn't matter).

      So if you choose k cities randomly and this is the best answer for a fixed k, you'd better sort firstly the whole array decreasingly by b[i],because surely you will choose the same configuration and it's easier to calculate the cost.

      Also for adding city i as j-th city(now being the last of them),the cost is fixed a[i]+(j-1)*b[i], so you want to minimize the cost of choosing j-1 cities from i-1 positions. This gives us the clue that we should maintain a min DP.

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

What is the intended complexity for SUBGRAPH? My solution is O(N * K2 * L) and it barely passes the TL.

→ Reply