Блог пользователя swapnilr

Автор swapnilr, 4 года назад, По-английски

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.

  • Проголосовать: нравится
  • +74
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    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.

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

»
4 года назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

I forgot the name of the round .

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

swapnilr Anything special for our college participants?

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Will there be a separate Ranklist for div1?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      DCOD2019 had separate ranklists. Why not this time?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

That where unexpected difficult problems.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

    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)

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

»
4 года назад, # |
Rev. 4   Проголосовать: нравится +6 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Will there be any editorial?

»
4 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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)

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        No.

      • »
        »
        »
        »
        4 года назад, # ^ |
        Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

        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.

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

1
2
5 10
  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

AC_CODE
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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 .

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 года назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится