Hello everyone,
As you may know, ICPC movement has officially died in my university. It was a streak of 14 NEERCs in a row, with 3 WFs, but now it's over and it doesn't seem to recover in near future. Let's celebrate this event with Samara Farewell Contest, and don't forget to press F!
It is a collection of not-so-easy (still easy for nutellas) problems authored by dalex and craus throughout our ICPC career and then problemsetting career. Find the enter links on Opencup site on Sunday, January 3, 2021, 11:00 MSK.
We can discuss the problems here after the contest ends. I will also upload it to Codeforces Gyms, but a bit later.
Links:
I spent so much time on K and never realised you don't have to kill heroes in one go QAQ
Is the problem even solvable if that is required?
I remember long time ago we concluded that it isn't, but maybe it's because we are orange.
I have solved B with some art of annealing: randomly choose one quest from each pair and perform 100 iterations by trying to flip quests while traversing in random order.
:(
Maybe you have a countertest? I'll add it.
I don‘t — actually 100 was approximation for log improvements and random order for achieving log on average :)
By the way, could you share the grader for N?
madskillz
It is hardcoded for this problem, including the top-right corner starting position.
Thanks, I now got AC :)
K's statement was quite confusing for me. I understood "Note that if Bloodseeker had 1 hit-point before he last-hits the i-th enemy, he doesn't die." as "in each second, first he hits an enemy and then he takes damage", but apparently that was supposed to mean that first he takes damage, then he hits an enemy, then the 0 hp condition is checked.
Sorry for that. I didn't expect this statement to be understood this way. In the game losing HP is a continuous process, and regeneration is instant. I will rewrite this part before uploading to CF Gyms.
You could ask a clarification request. I was ready to answer but there were no clars.
Well, there was no way of requesting clarifications... ("Questions" tab is missing from this contest's Yandex interface.)
I didn't know it's configured like this. Is it always the case on Opencups or was it a misconfiguration?
Hmm, I just checked it and it seems that GP of Siberia was the last contest in this season which was configured to let us ask questions. snarknews, do you want to look into this?
What's the case 10 for F?
try
F. Thanks for the contest, I really enjoyed most of the problems! :)
I am curious about how others implement problem B.
For me I used binary search and got in trouble with the precision. I finally passed by recalulating the answer using the input data but rather not using the direct answer from the binary search.
Is there anyone willing to share the implementation?
(btw, ld is long double in my code)
Thank you for your code! I just found that I have set wrong lowerbound for the binary search. (I set it 1 instead of 0.) The interesting thing is that my code, which was accepted, is actually wrong (the precision is actually enough) and I don't know why it passed all the tests, lol.
Thank you again!
Can anyone help me with promlem M?
I'm constantly having ML 21. I have only 3 arrays of int 0.5M each, and 1 array of bool with 0.5M elements. I do not have recursion :(
I can't understand from were I'm getting this ML :(
https://ideone.com/0veMsS
resolved :)
Can someone help me with the problem L? I can't understand how to construct the answer thorugh the parents. Can someone share the solution code or explain this to me?
L, authors' solution
I stucked at understanding problem B: If the NPC was chosen randomly, how come can we deterministically know the speed of earning gold? Is it that we need to find something like expected value?
To be more specific, there are infinitely possibility of infinite sequence of chosen npcs, but we need to calculate a single value out of all of that. Each possibility might have different speed. How do we make all that into a single value?
About Problem N:
First, this problem requires some chess knowledges, and I felt that this is not trivial. In particular, avoiding stalemates was harsh, and without chess basics I wouldn't be able to handle those situations. Just an opinion, but I think this problem is not appropriate for competitive programming contest...
If you decided to include this problem in a contest anyways(yeah, it's just an Open Cup!), you had to make your statements clear so that all required information about chess is provided in statement. There was no information about "stalemate" and "move that would place your own king in check is an invalid move" in the statement.
Chess from SEERC 2013 would be a good reference. This ICPC regional problem provides all (required) information about Chess rules, including basic rules, possible moves for each pieces, invalid move, and stalemate.