abhi2402's blog

Invitation to InfInITy 2k20 [Rated for Div. 2 on CodeChef]
By abhi2402, history, 4 years ago, In English

Hello Codeforces !!

I, on behalf of  the InfInITy Team, would like to invite you to take part in InfInITy 2k20, the first ever rated contest hosted by CodeChef IIITP Chapter , which will take place on Wednesday, November 4, 2020 at 21:00 ISTUTC+5.5. It is a 2.5 hr long contest.

The contest is Rated for Div. 2 on Codechef, but Div. 1 coders are encouraged to participate unofficially as there are prizes for top participants in combined(Div. 1 + Div. 2) ranklist. We'd be offering you 6 problems with varying difficulties.

PRIZES  : Top 3 performers  (Div1 + Div 2 combined)  will be awarded cash prize of INR 5000, 3000 & 2000 respectively.

Contest Link : www.codechef.com/INFY20
Contest Timing : 21:00 to 23:30 IST
Registration For Prizes : Infinity Website

I would really like to thank:

  • darshancool25 for Managing the contest , testing as well as proofreading and making suggestions for the problems.
  • silentone, nishit.sharma, ay21, prerit2001 for setting & testing the problems with me.
  • Codechef for their invaluable help and great platform.
  • BiT Legion for making this contest possible.

For any queries contact : bitlegion@iiitp.ac.in
Editorials for all the questions will be posted shortly after the contest ends! .

I hope you will enjoy solving the problems. Please give your feedback on the problem set in the comments below, after the contest.

UPD 1: All the editorials have been published on CodeChef discuss.

UPD 2: Congratulations to the winners! (Div 1 + Div 2)

  1. Geothermal
  2. nishant403
  3. EnEm
  • Vote: I like it
  • +63
  • Vote: I do not like it

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

Reminder 1: Contest starts in 2 hours!

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

    Is this round is similar to normal CC round? what can be the expected difficulty level?

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

    Reminder 2: Contest starts in 15 minutes. Good luck!

    Note: There are now separate contest pages for Div-1 and Div-2. It is rated for Div-2 and unrated for Div-1.

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

For Div1-A, what is wrong with this approach?

if x == y ans = 0;

if y>x and the difference is odd, we can do in one step by choosing a = y-x, so ans = 1;

if y>x and the difference is even, we can do in two steps by choosing a = (y-x)/2, so ans = 2;

if x>y and the difference is even, we can do in one step by choosing b = x-y, so ans = 1;

if x>y and the difference is odd, we can do in two steps by choosing a = 1 and b = x+1-y; so ans = 2;

UPD: Found the mistake a = (y-x)/2 might be even.

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

I'm feeling so stupid after seeing the solutions to SOLDVAL, I used sparse table with linear build time XD .

Partly because I didn't notice all problems were same in both divisions. I subconciously thought that Div1 2nd problem was Div2 4th problem difficulty level.

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

How to solve KGCD properly? Testcases seems to be weak, as $$$O(N^2)$$$ with some random and magic passes.

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

    Once you get the kth gcd, say g, you can create a new array containing only numbers which are divisible by g, divide them by g, and now the problem becomes to find out a pair of co-prime numbers. Then, for each number x in the array, find if there is any number which is not divisible by any prime factors of x (you can use inclusion-exclusion for that). Once you get the first number, just iterate back and find the second one.

    As for the test cases, i did try to make several test cases to make such random solutions fail, many did, but yours passed. There were many test cases having exactly 1 pair having the resultant gcd, and distributed at various indices in the different test cases, but guess i needed more of those. Can you explain your magic brute force XD

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

      Yes, your solution is clear now. Thanks!

      Well mine has two optimization. At the very beginning, as in your solution, we consider numbers only divisible by $$$g$$$, but make them unique (need to consider case with $$$a[i] = g$$$ carefully). After that, divide these numbers by two groups — odd and even. And then (until we succeed) we will try to pick in random either two odd numbers, or odd and even numbers, if their $$$gcd > 1$$$, terminate.

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

        I had considered about duplicates, but did not think about the even-odd grouping, and maybe combining both these things does just work out.

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

I feel this could've been rated for div1 too. The quality of questions were really good.

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

When will the editorial be posted ?

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

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

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

I was getting WA on 5th problem, but after the contest when i changed my if condition from

if(k&(1ll<<i)) { }

to

if((k&(1ll<<i))) { }

it worked. why?

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

    For sure, you have overflow with (1ll<<i)

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

    Oh, I checked your code and you have changed 

    if(k&(1ll<<i) == 0)

    to

    if((k&(1ll<<i)) == 0) {

    First one is bad, because C++ will do == first and only then &.

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

Great set of problems.

→ Reply