Hi Codeforces,
We at IIIT-Delhi would like to invite you to ProCon 2016, the annual programming contest conducted as a part of our technical festival. We will have 6-7 problems of varying difficulty over 2.5-3 hours with ACM style scoring. Also, there are prizes worth 20k INR for top Indian students.
Contest starts August 6, 2016, 21:00 IST
Check in your timezone here
Register at: http://esya.iiitd.edu.in/events/procon/register(for prizes)
Link to contest: https://www.codechef.com/PROC2016
RSVP: Facebook event
EDIT: contest starts in less than 24 hours.
EDIT: contest starts in 3 hours. We have 6 problems, and 2.5 hours for you to solve them. Good luck!
EDIT: contest ends in 1 hour, 2 problems remain unsolved.
EDIT: Winners will be listed here after a plag check, and contacted by email for prizes. There will be a replay on the next Saturday(August 13) in the CF Gym. An editorial will be published after the replay.
EDIT: Problems were set by the following.
rjalfa0 -> A
slender_hangman -> B, F
polingy -> C, D
lifecodemohit -> E
The problems were tested by the above, and AmbarPal and kzanmos.
UPDATE: Winners
1. rajat1603
2. sidhant
Winners will be contacted by email regarding prizes.
Auto comment: topic has been updated by polingy (previous revision, new revision, compare).
What is the expected cutoff for Procon Junior? I got 500 :)
Please follow the Procon Junior page here
Auto comment: topic has been updated by polingy (previous revision, new revision, compare).
Auto comment: topic has been updated by polingy (previous revision, new revision, compare).
Auto comment: topic has been updated by polingy (previous revision, new revision, compare).
Auto comment: topic has been updated by polingy (previous revision, new revision, compare).
Seems like the problem statement for Gangsters' wasn't clear. You are not required to pay for node t, but paying at s is mandatory. Interestingly, I had asked about this in the comments, and I was told that paying at both is mandatory, which is not the case. I guess the statement wasn't clear among the panel as well xD
I didn't assumed anything as such to not pay at t. But it passed.
How to solve it ?Using bitmask,right?
Yes. Precompute nodes within distance k and set their mask to have bit i on. Try all masks of people to pay. Choose the one with minimum cost that allows you to reach t from s. Prune this a little bit to fit under TL.
Can you share your code?
Expected answer for this was 0 instead of 100.
Are you sure? Mine prints 100 but gets AC
Idk. Mine prints 0. I added an if statement to ignore the cost of the end vertex and my code became TLE from WA. Then I changed dfs to bfs and it passed..
Changed DFS to BFS
What did you use DFS for in the 1st place? -_-
I forgot that I needed your permission to use depth first search. Apologies.
Apology accepted.
you are NibNalin?
Considering fake accounts are not allowed on CF.
Will this account get banned if I provide proof that it is by NibNalin
My other account was banned without any warning. throwaway_123
For each mask he would have used dfs to check if it is possible to reach from s to t with that..
rajat1603 Ofcourse it is NibNalin -_-
Hi, the panel was quite clear on the statement. If s or t are in a gangster's territory, you have to pay them.
How to solve this : https://www.codechef.com/PROC2016/problems/PRCS16B
Fix the number x that A will take. Then make an array C -> C[i] = 1 for all positions i such that B[i] = x, else C[i] = 0. Number of cyclic shifts required is now the maximum distance between two adjacent 1s in the circular array C. Add N to the final answer to account for the assignment costs. Note that if C has just one 1 then number of shifts needed is N - 1.
Isn't the number x that B will take is The number occurring maximum number of times in Array A
Are they going to publish proper editorial or something like that ????
Solutions aren't visible. Please share approaches for E.
The time limit was huuuuge that points almost towards a bruteforce (12 secs), however it didn't passed.
We will publish editorials after a replay. A brute force solution will not pass ^.^
Minimize Tree :-
Let (x, y) be the edge we are removing. The added edge (u, v) will have u in the subtree of y and v outside the subtree of y. I think that v should be the node with the least depth outside the subtree of y and u should be the centroid of the subtree rooted at y. This would be O(n). Was this the expected solution?
Interesting, we implemented v the same way you talk, but for u, our algorithm was substantially different. What you are saying is probably correct though, we can discuss in more detail after the replay. EDIT: can you test your idea on the second sample, I think it doesn't work there
Cool, Thanks!
Auto comment: topic has been updated by polingy (previous revision, new revision, compare).