swapnilr's blog

Invitation to Dementia 2020 (Rated for Div. 2) on CodeChef
By swapnilr, 4 years ago, In English

Hi all!

Programming Club, IIT Mandi and ACM Student Chapter, IIT Mandi are organizing Dementia 2020, our annual programming contest on 13th August, 8:30 pm — 11 pm IST.

The contest features 5 problems of varying difficulty and contest duration is 2 hours and 30 minutes. The contest is rated for Division 2 on CodeChef (<1800 rating). However, Division 1 can participate out of competition (4* and 5* users especially, should find some problems interesting).

The problem setters for the contest are lane, dhr_1, rtanmay, _-Noob-_ and swapnilr.

We would like to thank jtnydv25 for being the round coordinator on behalf of CodeChef and suggesting a major improvement to one of the problems and l_returns for testing the problems and catching issues that slipped our internal testing, taran_1407 for an initial review of the problem ideas, as well as the rest of the CodeChef team for managing other logistics of the contest.

Good luck and have fun!

UPD: The author's solution for HELPHAND was pointed out to be incorrect and since this affects a lot of users, the contest will be unrated. We hope you find the other problems good for learning purposes. We apologize for the mistake. Editorials are being added on CodeChef Discuss.

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

Comments Comments (44)
| Write comment?
»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Correction- In Codechef Contest page, its written "Rated for all". Link

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

If 4-stars will find the problemset interesting then why not make it rated for them. Like codeforces has div 2/educational rounds rated upto 2100 even though people above 1900 are officially in div 1.

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

    CodeChef and Codeforces both do not support custom rating bounds (for good reasons). Codeforces just places Candidate Masters in both divisions — but you are not given a choice there either, you can't set a Div 2 only round where only upto Experts are rated.

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

What if someone gets to division 1 after giving your round. Will he be continuing giving long in division 2?

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

    Yes, the person would belong in division 1 from next challenges.

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

    For the current Long he will keep continuing participating in DIV2 all rating updates will be simultaneous as LONG Ends as per the rules and policies of Codechef.

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

I forgot the name of the round .

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

swapnilr Anything special for our college participants?

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

Reminder: contest starts in 5 hours. Hope to see you in the standings!

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

Will there be a separate Ranklist for div1?

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

    Unfortunately, during the contest, only Div. 2 contestants will be visible in the standings. However, once the contest is over, the combined Div1+2 ranklist will definitely be provided (this is managed by CodeChef, and I think we would need to wait for MOSS to be applied before releasing the ranklist).

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

      DCOD2019 had separate ranklists. Why not this time?

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

        That was a separate contest for each division, like how Cook-Offs, Lunchtimes, Long challenges are organized. Think of this one more like a Div2 only round like the ones on Codeforces, but it's hosted on CodeChef, so there is no "show unofficial" option to view yourself in the ranklist.

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

There should be some more contests in CodeChef that should be rated for all.

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

That where unexpected difficult problems.

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

Pretty tough contest....can someone explain the solution of "Helping Hands" problem

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

    Every prime counts as 2, every other number as 1.

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

    Precalculate the number of distinct primes till a number for each number from 1 to 1e6. This can be done by applying sieve and doing prefix sum.

    For a number n let this number be p, then to create the final lcm for 1 to n we will require p-1 moves where we take the highest power of each prime at each step at the end we will have 2 numbers(the numbers involved in the last operation) which will attain the required value. For the remaining n-2 numbers we can take their lcm with any of the above 2 numbers therefore we will only need 1 move for each of the remaining n-2 numbers.

    Final formula: p-1+n-2 (for n>2)

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

      I missed the cases with n=2 and n=1, now I feel so stupid...

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

    First, you need to get a pair of numbers equal to LCM(1,2,...,n) then it will take 1 operation for each of the n-2 remaining numbers. To do this, we will perform the operation on biggest powers of primes <= n. There is one such power for each prime, so we can count this using sieve. Ok, now say there x such powers. Answer = solve(x) + n-2, treat very small cases separately because they are weird. You can compute solve(x) with DP. Base cases are solve(0)=solve(1)=0 and the recurrence is solve(x) = solve((x+1)/2) + solve(x/2) + 1 we split set of powers in half and use 1 extra operation to combine them at the end.

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

We hope you found at least some of the problems interesting.

Problem authors-

MINMXSTR — swapnilr (with suggestion by Jatin Yadav (contest coordinator from CodeChef) to increase constraints and make the problem interesting instead of O(N*Q))

TOWIN — rtanmay

SPPSTR — lane

BEACIRC — _-Noob-_

HELPHAND — dhr_1

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

Will there be any editorial?

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

I don't know why I was getting WA in beautiful circles.I did the same thing as in editorial. Can anyone help me in it.Here is the link of the solution https://www.codechef.com/viewsolution/36691768

UPD:Got the mistake.

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

Great contest! What is the expected time complexity for the question of intersecting circles My n^2*log(n) solution is getting TLE! Can anyone point out as to why that is happening? Link to my submission- https://www.codechef.com/viewsolution/36692585

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

    I think in worst case your program will reach O(n^3).

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

      Yes, but in the worst case, wouldn't the answer be n(n-1)(n-2)/6? So, you would have to iterate over all possible triplets..? (Haven't seen the tutorial)

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

        No.

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

        We don't have to iterate all the triplets. Here is my approach. Iterate over all pairs of circles. Circle passing through intersection of C1 and C2 will have equation C1+kC2=0.Also there is one more condition,the circle passes through the centres of C1 and C2.So when you put the points in the above equation and do some maths and then compare the k values obtained you will get dist(c1,c2)=r1^2 + r2^2 where c1,c2 are centre coordinates. So the problem reduces to finding all pairs of circles satisfying the above condition. Now you can find the centre of circle as (c1+c2)/2 and radius as dist(c1,c2)/2.So you just have to find how many such circles are there which can be done using map.

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

          [Update]

          I got the answer. please ignore it.

          [DELETED]
          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Looks like your issue was the increasing size of map and that was leading to TLE.

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

Thank you for the contest, problems are nice and I think MINMXSTR is very interesting.

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

Are tests weak for A ? Like this solution will fail at this case :

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

    Your general idea for n!=2 is correct — if it was incorrect, you wouldn't have got AC.

    Apart from obvious n=1 and n=10^4, we can't make testcases for arbitrary n. I wouldn't call the testcases weak, especially on a cakewalk problem.

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

My solution to beautiful circles, its quite need and easy to understand just in case somebody needs a reference

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

Hi. My ratings on codechef have not been updated,is it because it was my first codechef contest?

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

This was a disaster for me , i read that string problem which was solved by only four (thought it was easy) . And thought i can do it. But after wasting more than half time ,i got tle. Solved the easiest in last half hour .

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

Is the contest still rated? As Helping Hand problem had a wrong test case.

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

    No, it's unrated, read the update in this announcement.

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

Problem editorials have been uploaded. Here are the links-

https://discuss.codechef.com/t/towin-editorial-dementia/74776
https://discuss.codechef.com/t/minmxstr-editorial/74612/
https://discuss.codechef.com/t/beacirc-dementia/74610
https://discuss.codechef.com/t/sppstr-editorial/74638

Problem HELPHAND was found to be incorrect, so no editorial for that.

→ Reply