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:
- Setters: Nishank IceKnight1093 Suresh, Suchit Atlas, Aditya Aditya_Mittal_31 Mittal, Andrei Sho Alexandru, Mihir BladeRunner Kaskhedikar, Dhanraj coderdhanraj Chaurasia, Mostafa Beevo Alaa, Nicholas __jk__
- Tester: Takuki tabr Kurokawa
- Statement Verifier: Nishank IceKnight1093 Suresh
- Video Editorialists: Sundar K Letscode_sundar, Madhav jhamadhav Jha, Jwala jwalapc , Adhish ak2006 Kancharla
- Text Editorialist: Nishank IceKnight1093 Suresh
- Contest Admin: Nishank IceKnight1093 Suresh
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!
Reminder: Contest starts in 2 hours!
Restarting codechef after a long time.
Passed div2 d at the last minute, hooray!
can u explain your idea plz
my sol is exactly the same as the tutorial's(and a little overcomplicated TaT), so I recommend u read the tutorial instead:)
CodeChef,启动！
Okay I am going to be the first to say:
ABSOLUTEDIFF: 1842D - Tenzing and His Animal Friends
What, how!?
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.
I feel the model approach is different. Can you please elaborate yours?
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]$$$.
Where is wrong ? can u give me a test.
n=3,k=12
what will interactor choose first?
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
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.
oh sorry i mis-understood on the last time.. can u explain your solution plz :|
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.
The testcases of Remove Stones are really weak. Simply breaking the loop after a certain time passes all the testcases.
How to Solve Problem Swap the numbers My Logic was to use Priority Queue but not able to get Correct Answer
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.
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
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
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.
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?
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.
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.
Auto comment: topic has been updated by IceKnight1093 (previous revision, new revision, compare).