We invite you to participate in CodeChef’s Starters 151, this Wednesday, 11th September, rated upto 5 stars (i.e. for users with rating < 2200)
Time: 8:00 PM — 10:00 PM IST
Joining us on the problem setting panel are:
Setters: Kanhaiya notsoloud1 Mohan, Harsh harsh__h, Ashish Kryptonix Gangwar, Bernard BERNARD Ibrahimcha, Krrish Krrishchanchal Chanchal
Tester: Manan mexomerf Grover
Contest Admin: Yash yash_daga Daga
Statement Verifier: Kanhaiya notsoloud1 Mohan
Text Editorialists: Nishank IceKnight1093 Suresh.
Note: Some problems have subtasks
Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest. The video editorials of the problems will be available only to Pro users.
Also, if you have some original and engaging problem ideas and are interested in them being used in CodeChef's contests, you can share them here. Hope to see you participating.
Good Luck!
The heading reads "rated upto 6 stars" but the body reads "rated upto 5 stars", which one is correct?
Thanks for pointing out, both are correct now :)
Is this the end for programmers?
if a problem is 2000 in codechef how much is it rated in codeforces?
1200-1500
contest starts in ~ 30 mins
honestly i feel like codechef is bluffing with its problems, sometime you think you solution would pass but somehow it doesn't
can someone give hint for d2 C? also I have no flippin' clue on how my B got AC. I had some the intuition of using sets and binary search but initial code was buggy. changed normal division to
static_cast<long double>
and it passed the samples so I just submitted. can someone help me in proving it?link
The complexity will go to $$$ O(2 \cdot n) $$$ at max i guess because there can be $$$ n $$$ erases from multisets at worst
Your code is correct I am not able to understand where are you facing problem?
(Talking about B)
i'm not understanding why it is correct
First of all double failed due to precision errors (floating variables are not very precise long double will also fail for higher numbers)
Read the official editorial see my code you will understand from there.
link
I can't prove it but for C, the sequence will go like this. $$$[0, a, b, a+b, 2b, a+2b, 3b, a+3b, \dots]$$$. My approach was to ignore all the multiples of $$$b$$$ that are less than $$$a$$$. Then, when we reach some $$$x$$$ such that $$$bx>=a$$$ simply the answer of the $$$ith$$$ smallest element will alternate here between $$$a+ib$$$ and $$$ib$$$ and you can calculate this greedily. Here is my Solution to make it clearer and sorry if my explanation sucks.
You can use binary search on answer...for problem C
Yes I know, but my answer is in O(1) which is better so I explained it.
can you please explain more, btw great, didn't thought that it's possible in o(1)
Sure, According to the sequence, we notice that an element is represented as $$$xb$$$ or $$$a+xb$$$ where $$$x$$$ is any positive integer. noticing that, let $$$m =\lfloor\frac{a}{b}\rfloor$$$, there are $$$m$$$ multiples of $$$b$$$ before $$$a$$$ which surely means that the first $$$m$$$ numbers in the sequence are these multiples because an element can be represented as $$$xb$$$. We now reach a state where every two elements in the sequence become $$$a(m+x)$$$ and $$$a+xb$$$. you will choose which one is the $$$Kth$$$ element depending on the parity of the remaining steps. Replace this $$$x$$$ by the remaining steps divided by two to obtain the answer. Well, to explain more I'll just explain an example. $$$A = 6, B = 2, K = 7$$$. here there a $$$3$$$ multiples of $$$2$$$, $$$[2,4,6]$$$ and with the $$$0$$$ as $$$F_0$$$, the sequence is now $$$[0,2,4,6]$$$, subtract our steps by $$$4$$$, $$$K = K - 4 = 3$$$, now every two elements will be $$$6+2x$$$ and $$$2(3+x)$$$. The sequence will be $$$[0, 2, 4, 6, 6, 8, 8, 10, 10,\dots]$$$. The $$$Kth$$$ element is $$$2(3+\lfloor\frac{3}{2}\rfloor) = 8$$$. The implementation will vary but the idea is the same, if anything is not clear please ask because I don't explain my solutions that much so it might not be clear.
let c=a/b sequence would be 0,b,2b...cb...a,(c+1)*b,a+b,(c+2)*b,a+2b....
The problems were nice
How to solve Shooting(Hard Version)? Any similar problem on CF/Atcoder?
I solved it using Manhattan trick Submission. Similar problem on AtCoder Problem