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

Автор yash_daga, история, 9 дней назад, По-английски

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!

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

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

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

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

    Thanks for pointing out, both are correct now :)

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

    Is this the end for programmers?

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

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

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

contest starts in ~ 30 mins

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

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

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

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

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

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

    (Talking about B)

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

      i'm not understanding why it is correct

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

        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

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

    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.

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

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

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

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

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

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

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

            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.

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

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

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

The problems were nice

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

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