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

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

We invite you to participate in CodeChef’s Starters 91, this Wednesday, 24th May, rated till 6-stars Coders (ie. for users with rating < 2500).

Time: 8:00 PM — 10:00 PM IST

Note that the duration is 2 hours. Read about the recent CodeChef changes here.

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 for all users for 1 day as soon as the contest ends, after which they will be available only to Pro users.

Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.

Hope to see you participating. Good Luck!

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

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

Hoping this time, correct input test cases are there :)

All the best, everyone!

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

Note: Some problems have subtasks.

»
17 месяцев назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится
Personal Opinion
»
17 месяцев назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Why the answer for 2nd problem (Odd GCD Permutation) for n = 1 is No. Isn't it should be yes coz for odd indices, gcd is 1 and for even indices, it will be 0. Hence gcd for odd indices is greater than the even one. Then why no?

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

    Why is the gcd of empty array 0?
    Vacuous_truth
    Pick any positive integer (say g), for empty array (say A). this statement holds true -
    g divides all the elements present in A.

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

    Just now, I checked the announcement, they changed the constraints to N >= 2. I wasted too much time thinking about the edge case in it. It shouldn't be done ;/

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

In Limited Shopping, why is this submission fast enough?
I coded $$$O(n*n*k)$$$ brute force at the last minute to fetch 30 points and was surprised to see 100 points on it.

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

    I did O(n*k*k*k) to get 11 points but got 30 points.

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

    It seems like just low constant factor.

    I did a quick operation count, your code does about $$$6\cdot 10^8$$$ operations in the worst case, but they're all pretty simple ones so it happens to run fast.

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

Loved the question -XOR & sum

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

    How did you solve it?

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

      Start with the simple observation that $$$a + b = a \oplus b \iff a \& b = 0$$$, ie $$$a$$$ and $$$b$$$ share no 'on' bits.

      The observations from each subtask:

      Subtask 2
      Subtask 3

      Putting these together, we arrive at:

      The final solution

      Here's my AC submission. Sadly couldn't come up with this during contest :P