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

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

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
  • Проголосовать: не нравится

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

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

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

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

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

contest starts in ~ 30 mins

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

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

»
2 месяца назад, # |
  Проголосовать: нравится 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

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

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

    (Talking about B)

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

      i'm not understanding why it is correct

      • »
        »
        »
        »
        2 месяца назад, # ^ |
          Проголосовать: нравится 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

  • »
    »
    2 месяца назад, # ^ |
    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.

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

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

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

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

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

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

          • »
            »
            »
            »
            »
            »
            2 месяца назад, # ^ |
              Проголосовать: нравится 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.

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

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

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

The problems were nice

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

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