IceKnight1093's blog

Invitation to CodeChef Starters 96 (Rated till 5 Stars ) — 28th June
By IceKnight1093, 11 months ago, In English

We invite you to participate in CodeChef’s Starters 96, this Wednesday, 28th June, rated till 5-stars Coders (ie. for users with rating < 2200).

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:

Written editorials will be available for all on CodeChef Discuss. 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!

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

»
11 months ago, # |
  Vote: I like it +19 Vote: I do not like it

Reminder: Contest starts in 2 hours!

→ Reply
»
11 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Restarting codechef after a long time.

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

    Passed div2 d at the last minute, hooray!

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

      can u explain your idea plz

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

        my sol is exactly the same as the tutorial's(and a little overcomplicated TaT), so I recommend u read the tutorial instead:)

        → Reply
»
11 months ago, # |
  Vote: I like it +10 Vote: I do not like it

CodeChef,启动！

→ Reply
»
11 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Okay I am going to be the first to say:

ABSOLUTEDIFF: 1842D - Tenzing and His Animal Friends

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

    What, how!?

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

      It's the same idea of putting a constraint $$$(u,v,w)$$$ there are some changes in the problem but the key idea which is the shortest path is the same.

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

        I feel the model approach is different. Can you please elaborate yours?

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

          The solution in CF one is to get the shortest distance between $$$1$$$ and all other nodes and sort them in that order.

          The solution in CC one is to get the shortest distance between all pairs and check for given input that $$$|a_u-a_v| \leq dist[u][v]$$$ as you can see the core of the solution is to solve the system of constraints you can just get the shortest path and this means that $$$|a_u-a_v| \leq dist[u][v]$$$.

          → Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Where is wrong ? can u give me a test.

Remove Stones
→ Reply
  • »
    »
    11 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    n=3,k=12

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

      what will interactor choose first?

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

        Alice will choose 1. Then n=2 and Bob can only choose 1. Then n=1 and Alice chose 1 and n=0. So Alice wins

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

    I played you program with my program. It was fun. Your testcase is (n,k) = (5,10). You pick Bob and I take away 1 stone making n == 4. You cannot pick all 4 now.

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

      oh sorry i mis-understood on the last time.. can u explain your solution plz :|

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

        If k == 1 then you pick Alice and win in first turn.

        If the smallest factor of k(say p) divides n then you should pick Bob. Otherwise Alice. You can see that you can always take n down to the largest multiple of p < n.

        → Reply
»
11 months ago, # |
  Vote: I like it +17 Vote: I do not like it

The testcases of Remove Stones are really weak. Simply breaking the loop after a certain time passes all the testcases.

Code
→ Reply
»
11 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

How to Solve Problem Swap the numbers My Logic was to use Priority Queue but not able to get Correct Answer

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

    Since you can swap ai and aj if |i-j| >= k, that means you can swap a[0] with a[k], a[k+1], ..., a[n-1], a[1] with a[k+1], a[k+2], ..., a[n-1]. Which means all indices i < n-k can be swapped with all indices j >= k. Now there are three cases. First case : If n-k >= k i.e k <= n/2 then all numbers can be swapped around which means just sort the array and return it. Second case : If k > n then no number can be swapped, so just return the original array. Third case : Put the first n-k numbers and n-1-k+1 numbers in another array, sort them. Print the first n-k numbers then print the numbers from the original array from n-k+1 to k-1 and then print the remaining arrays from the new sorted array.

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

    I used a multiset ,so I think my approach was similar to yours and I got AC. My approach--> The indexes where swap operation will NOT be allowed will follow the following condition-> (abs(i-0) <k && abs(i-(n-1) ) <k).

    I stored all these indices in a set ns (non swappable indexes) and I stored rest of the indices in another set s (swappable indexes) and their respective values in a multiset and I again traversed theses swappable indices from left to right and filled the values of the multiset on these indices in an ascending order.

    Values at non-swappable indexes will remain the same as they were in the initial array. Finally I printed the answer array. This is my submission

    → Reply
»
11 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

i wrote a multibfs code for ABSOLUTEDIFF which runs in O(n + m + k). I believe the idea is very stupid but it surprisingly passes. Can anyone find a counter-test or explain why it works?

code

UPD — I think the tests were weak, I found a counter-test

test
→ Reply
  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think the tests are weak too, I literally just simulated the $$$k$$$ constraints $$$2 \cdot n$$$ times and checked if the upper bound at least the lower bound, and it passes all test cases. If this is actually correct, I don't have a proof for this, it's just random intuition lmao. Otherwise, the tests are just bad.

    → Reply
»
11 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone help with ZERO ARRAY please. I read the editorial but I don't understand why it suppose to consider N is even/odd. Aren't these two cases the same for a cyclic array?

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

    No they are different. Consider the linear system:

    $$$b_0 + b_{n-1} = a_0$$$.

    $$$b_0 + b_1 = a_1$$$.

    $$$b_1 + b_2 = a_2$$$.

    ...

    $$$b_{n-2} + b_{n-1} = a_{n-1}$$$.

    Intuitively, $$$b_1 = a_1 - b_0$$$, $$$b_2 = a_2 - a_1 + b_0$$$, $$$b_3 = a_3 - a_2 + a_1 - b_0$$$, therefore the parity of $$$n$$$ matters, because it decides the sign of $$$b_0$$$ in the expression.

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

      Yes. I took some time as well to figure out the difference between odd and even cases, as the previous replies says the sign of elements in the expression of $$$b_{n - 1}$$$ change even though the equation $$$b_{n - 1}$$$ = $$$a_{0}$$$ $$$ - $$$ $$$b_{0}$$$ remains the same.

      → Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by IceKnight1093 (previous revision, new revision, compare).

→ Reply