Hello CodeForces Community!
We are back with another set of brain racking problems this August Lunchtime 2018, a three-hour test to knack your coding abilities. There are more reasons to be delighted as ShareChat has opened some exciting job opportunities for professionals across the globe! More details can be found on the August Lunchtime contest page.
This time on the problem setting panel are:
- Problem Setter: kingofnumbers (Hasan Jaddouh), allllekssssa (Aleksa Plavsic)
- Problem Tester and Editorialist: Pepe.Chess (Hussain Kara Fallah)
- Statement Verifier: Xellos (Jakub Safin)
- Russian Translator: Mediocrity (Fedor Korobeinikov)
- Mandarin Translator: huzecong (Hu Zecong)
- Hindi Translator: Srijan Dubey
- Vietnamese Translator: VNOI Team
Contest Details:
Time: 25th August 2018 (1930 hrs — 2230 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.
Contest link: https://www.codechef.com/LTIME63
Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.
Prizes: Top 10 performers in Global and Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here: https://discuss.codechef.com/questions/51999/how-do-i-win-a-codechef-goodie. (For those who have not yet received their previous winning, please send an email to winners@codechef.com)
Good Luck!
Hope to see you at the contest!
UPD He did it again! uwi solved everything in last minutes and got the first place! Congratulations!
TOP 5:
Mrip
Big congratulation to winner of div 2 round receed.
Thanks for participation!
UPD: One hour before contest !
nice problem c but b was a bit bad,implementation-_-. nice problemset.
Thanks, but you have one more hour for solving!
yet another greedy casework problem >_<
I absolutely hated that problem. I've been getting WA for the past 1 hour, and can't even pass the 1st two sub tasks -_-
The two groups problem was nice though.
what is full solution for that,i only got 50 for X and two groups
I'm not very good at explaining, but I'll try.
First, try to visualise if there was a single array and you wanted to minimise (max-min). Bring all elements of the array in range [0,x-1] by taking modulo x, and count the number of operations done so far, let it be op1. (this count will be needed in full solution). Now, you have O(n) candidates for solution. sort the array after taking modulo, and you can see that either the answer is (arr[n]-arr[1]) or the answer will be (arr[i-1]-(arr[i]-x)) if we do one more operation, do this in decreasing order of i.
After doing this for both arrays, we have 2 new arrays a[n] and b[m]. a[i] represents (max-min) after doing op1+i operations, and b[] is the same for the other array. Now take another observation, if I do -x on both arrays on every element my answer doesn't change, they're basically dummy operations. Now let's say you want a[i] + b[j] to be your final answer, that means you have done (op1+i) operations on 1st array and (op2+j) operations on 2nd array. Now you want to make them the same count, by doing the dummy operations. By bezout identity, you can see that it can be done if (op1+i)%gcd(m,n) == (op2+j)%gcd(m,n). then a[i]+b[j] can be one answer. Now simply divide both array elements into modulo classes of gcd(m,n), take minimum for each class, and update final answer.
You can look at my code if you're having trouble understanding this.
https://www.codechef.com/viewsolution/19864707
got it
can you explain why do we need to bring all elements of array in range [0,x-1]?
For a single array, let's write arr[i] = a*x+b.
If max(a)-min(a) > 1, we can always improve our answer.
We brought all elements in [0,x-1] for ONE possible candidate answer, the most trivial one.
After that we do -x on the maximum value, take the difference again, do -x on new maximum, take the difference again, and so on. After n such operations, we'll get our original reduced array back, with all elements now having -x done. So, our answer has to be amongst the previous O(n) candidates
The task was much harder than I expected! I solved it and wrote correct code in 20 minutes, so I didn't see so many tricky cases, I had three "tricky" ifs (and case like x<n is obvious).
At beginning, I planned to give next version:
For each index i, we must have at least two indices j and l on distance not bigger than D.
And then I realized 14 different cases and change it in this easier task(and much nicer than that version :P).
How to solve the last 3 problems?
how to solve problem JAGAM
The game either lasts 2 turns or ends in a tie.
1) If the first player can win in 1 move, print 1.
2) If every possible move for the first player results in a state where the second player can win in 1 move, print 2.
3) Otherwise, every player can do the opposite of his opponent's move, and the game ends in a tie
lokpati see this...exactly this solution struck to me the moment I read the question.
How to solve "GukiZ Has More Candies " ?
How to solve X and two groups?
I was using priority queue, in each turn reducing the maximum to less than second maximum by subtracting a factor of x from both top element. My idea was that in less than or equal to 2*(n + m) iterations we will obtain the optimum value, because after that the relative order will repeat.
But I was constantly getting WA on last subtask. Any reason why?
That statement, unfortunately, isn't correct :(
Can you disprove it or give a counter example.
I actually proved it but don't know if I missed something
Imagine that you have all the numbers belonging in the interval [0, x - 1] Let's sort both arrays, and make two new arrays, sdif and tdif , where sdifi = si + 1 - si (going circular), and same thing goes for the other array, Now, every move you make is a circular rotation of both arrays, and the current answer you're getting is 2 * x - sdifo - tdifo. For example, if gcd(n, m) = 1, we could have every possible combination of elements as first elements of the arrays (n * m combinations overall). I think this is a good counterexample and a good hint to the actual solution.
Nice. Nice proof indeed.
Wow very very interesting. Good job VladaMG98! Could you maybe give us a backstory on that name?
Thank you VladaMG98, very cool!
You did.
Take the set 1 1000000000 and x=1. It's clear that you need to make 10^9-1 moves, but you just make 2.
When the editorials will be out?
UPD: Still waiting for editorials :(