swapnilr's blog

By swapnilr, 6 weeks 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 smit_mandavia 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

»
6 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

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

»
6 weeks 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.

  • »
    »
    6 weeks 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.

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it -13 Vote: I do not like it

    6 star king is back take care all

»
6 weeks 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?

  • »
    »
    6 weeks 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.

  • »
    »
    6 weeks 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.

»
6 weeks ago, # |
  Vote: I like it -18 Vote: I do not like it

my favorite codechef

»
6 weeks ago, # |
  Vote: I like it +22 Vote: I do not like it

I forgot the name of the round .

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

swapnilr Anything special for our college participants?

»
5 weeks 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!

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Will there be a separate Ranklist for div1?

  • »
    »
    5 weeks 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).

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

      DCOD2019 had separate ranklists. Why not this time?

      • »
        »
        »
        »
        5 weeks 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.

»
5 weeks 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.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

expecting some graph theory problems....

»
5 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

That where unexpected difficult problems.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

  • »
    »
    5 weeks 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)

  • »
    »
    5 weeks 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.

»
5 weeks 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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Will there be any editorial?

»
5 weeks 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.

»
5 weeks 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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      5 weeks 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)

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        No.

      • »
        »
        »
        »
        5 weeks 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.

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

          [Update]

          I got the answer. please ignore it.

          [DELETED]
          • »
            »
            »
            »
            »
            »
            5 weeks 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.

»
5 weeks 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.

»
5 weeks 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
  • »
    »
    5 weeks 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.

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

i was doing the same in Beautoful Circles as mentioned in solutions outlines but i don't know what went wrong and i started thinking that this method is wrong............shit i would've tried ............so its ok......

overall contest was good problem A and B were amazing and rest is history...........

However why is difficulty not balanced as you can see problem C was way harder than problem B. there is a huge hike in difficluty after B.

»
5 weeks 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
»
5 weeks 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?

»
5 weeks 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 .

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It was my first short contest on codechef i did the same mistake i read minmax string problem for 20-25 min as it was on top when contest started i wasn't able to do it then i saw dashboard and i was like fu*k then i fastly solve problem to win and help hands which lead me under 70

»
5 weeks 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.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it