yash_daga's blog

By yash_daga, history, 2 months ago, In English

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:

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!

  • Vote: I like it
  • +33
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The heading reads "rated upto 6 stars" but the body reads "rated upto 5 stars", which one is correct?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

if a problem is 2000 in codechef how much is it rated in codeforces?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

contest starts in ~ 30 mins

»
2 months ago, # |
  Vote: I like it +4 Vote: I do not like it

honestly i feel like codechef is bluffing with its problems, sometime you think you solution would pass but somehow it doesn't

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Your code is correct I am not able to understand where are you facing problem?

    (Talking about B)

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i'm not understanding why it is correct

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You can use binary search on answer...for problem C

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

        Yes I know, but my answer is in O(1) which is better so I explained it.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          can you please explain more, btw great, didn't thought that it's possible in o(1)

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      let c=a/b sequence would be 0,b,2b...cb...a,(c+1)*b,a+b,(c+2)*b,a+2b....

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The problems were nice

»
2 months ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve Shooting(Hard Version)? Any similar problem on CF/Atcoder?