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)
Reminder 1: Contest starts in 2 hours!
Is this round is similar to normal CC round? what can be the expected difficulty level?
It's rated for only Div.2. So it's Div 2 level.
+1
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.
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.
If $$$y > x$$$ and $$$y - x$$$ is divisible by $$$4$$$, answer is $$$3$$$.
oh, I am such a fool!
Thanks for the help
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.
How to solve KGCD properly? Testcases seems to be weak, as $$$O(N^2)$$$ with some random and magic passes.
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
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.
I had considered about duplicates, but did not think about the even-odd grouping, and maybe combining both these things does just work out.
I feel this could've been rated for div1 too. The quality of questions were really good.
When will the editorial be posted ?
All editorials have ben posted on Codechef Discuss. :)
Auto comment: topic has been updated by abhi2402 (previous revision, new revision, compare).
I was getting WA on 5th problem, but after the contest when i changed my if condition from
to
it worked. why?
For sure, you have overflow with (1ll<<i)
Oh, I checked your code and you have changed
to
First one is bad, because C++ will do == first and only then &.
Got it. Thanks alot!
Great set of problems.