### dalex's blog

By dalex, 8 months ago,

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.

• +130

 » 8 months ago, # |   0 I spent so much time on K and never realised you don't have to kill heroes in one go QAQIs the problem even solvable if that is required?
•  » » 8 months ago, # ^ |   +7 I remember long time ago we concluded that it isn't, but maybe it's because we are orange.
 » 8 months ago, # | ← Rev. 2 →   +8 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.
•  » » 8 months ago, # ^ |   0 :(Maybe you have a countertest? I'll add it.
•  » » » 8 months ago, # ^ |   +8 I don‘t — actually 100 was approximation for log improvements and random order for achieving log on average :)
 » 8 months ago, # |   0 By the way, could you share the grader for N?
•  » » 8 months ago, # ^ |   0 madskillzIt is hardcoded for this problem, including the top-right corner starting position.
•  » » » 8 months ago, # ^ |   +15 Thanks, I now got AC :) N#include using namespace std; using ll = long long; int main() { ios_base::sync_with_stdio(false); cin.tie(0); string str; cin >> str; cin >> str; // ....???. // ....??.? // ....?.?? // .....??? // ...Q.... // ..K..... // ........ // ........ string res = "c3c4 "; res += "c4c5 "; res += "c5c6 "; // ....???. // ....??.? // ..K.?.?? // .....??? // ...Q.... // ........ // ........ // ........ res += "d4e3 "; // ...?.??? // .....??? // ..K..??. // .....?.? // ........ // ....Q... // ........ // ........ res += "c6d6 "; // ..?..??? // .....??? // ...K.??. // .....?.? // ........ // ....Q... // ........ // ........ res += "e3e7 "; // .?....?? // ....Q... // ...K..?. // .....?.? // .....??. // ........ // ........ // ........ res += "d6c6 "; res += "c6b6 "; // .?....?? // ....Q... // .K....?. // .....?.? // .....??. // .....??? // .....??? // ........ res += "e7e8 "; // ....Q... // ......?? // .K...?.? // .....??. // .....??? // .....??? // .....??? // .....??? res += "b6c6 "; res += "c6d6 "; // ....Q... // ......?? // ...K.?.? // .....??. // .....??? // .....??? // .....??? // .....??? res += "e8e6 "; // .....?.? // ......?? // ...KQ... // ......?? // .....?.? // .....??. // .....??? // .....??? res += "d6e7 "; res += "d6d7 "; res += "d7e7 "; // .......? // ....K.?? // ....Q... // ......?? // .....?.? // .....??. // .....??? // .....??? res += "e7f7 "; res += "e7e8 "; res += "e8f7 "; // .......? // .....K.? // ....Q... // ......?? // .....?.? // .....??. // .....??? // .....??? res += "e6e8 "; // ....Q... // .....K.? // .......? // .....??? // .....??? // .....??? // .....??? // .....??? res += "f7g8 "; // Sidetrack: kill that position! res += "e8g8 "; res += "g8g6 "; // ....Q.K. // ........ // .....?.? // .....??. // .....??? // .....??? // .....??? // .....??? res += "g8g7 "; res += "g8h8 "; res += "h8g7 "; // ....Q... // ......K. // ........ // .....??. // .....??? // .....??? // .....??? // .....??? res += "e8e7 "; // ........ // ....Q.K. // ........ // .....?.? // .....??. // .....??? // .....??? // .....??? res += "g7g6 "; res += "g7h7 "; res += "h7g6 "; // ........ // ....Q... // ......K. // ........ // .....??. // .....??? // .....??? // .....??? res += "e7e6 "; // ........ // ........ // ....Q.K. // ........ // .....?.? // .....??. // .....??? // .....??? res += "g6g5 "; res += "g6h6 "; res += "h6g5 "; res += "e6e5 "; // ........ // ........ // ........ // ....Q.K. // ........ // .....?.? // .....??. // .....??? res += "g5g4 "; res += "g5h5 "; res += "h5g4 "; res += "e5e4 "; // ........ // ........ // ........ // ........ // ....Q.K. // ........ // .....?.? // .....??. res += "g4g3 "; res += "g4h4 "; res += "h4g3 "; // ........ // ........ // ........ // ........ // ....Q... // ......K. // ........ // .....??. res += "e4c2 "; // ........ // ........ // ........ // ........ // ........ // ......K. // ..Q..... // ....???? res += "g3f3 "; res += "c2e2 "; // ........ // ........ // ........ // ........ // ........ // .....K.. // ....Q... // ......?? res += "e2g2"; cout << res << '\n'; } 
 » 8 months ago, # |   +10 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.
•  » » 8 months ago, # ^ |   -10 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.
•  » » » 8 months ago, # ^ |   +30 Well, there was no way of requesting clarifications... ("Questions" tab is missing from this contest's Yandex interface.)
•  » » » » 8 months ago, # ^ |   0 I didn't know it's configured like this. Is it always the case on Opencups or was it a misconfiguration?
•  » » » » » 8 months ago, # ^ |   0 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?
 » 8 months ago, # |   0 What's the case 10 for F?
•  » » 8 months ago, # ^ | ← Rev. 3 →   0 try 4 0 6 2 8 6 14 10 12 
•  » » 8 months ago, # ^ |   0 Real test 105 0 4 2 10 6 12 8 18 14 16 
 » 8 months ago, # |   0 F. Thanks for the contest, I really enjoyed most of the problems! :)
 » 8 months ago, # |   0 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?
•  » » 8 months ago, # ^ | ← Rev. 2 →   +18 (btw, ld is long double in my code) Spoilerint n; ld a[LIM], b[LIM], c[LIM], d[LIM]; bool bsearch(ld mid){ ld num = 0, den = 0; forn(i,n){ if(mid * (c[i] - a[i]) > (d[i] - b[i])){ num += b[i]; den += a[i]; } else{ num += d[i]; den += c[i]; } } return (num/den >= mid); } int main(){ fastio; int tests = 1; //cin>>tests; while(tests--){ cin>>n; forn(i,n){ int ta,tb,tc,td; cin>>ta>>tb>>tc>>td; a[i] = ta; b[i] = tb; c[i] = tc; d[i] = td; } ld l = 0, r = 1e10; forn(i,200){ ld mid = (l+r)/2; if(bsearch(mid)) l = mid; else r = mid; } cout<
•  » » » 8 months ago, # ^ |   0 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!
 » 8 months ago, # |   0 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
•  » » 8 months ago, # ^ |   0 resolved :)
 » 7 months ago, # |   +8 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?
•  » » 7 months ago, # ^ |   +5
 » 3 months ago, # | ← Rev. 3 →   0 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?
 » 2 days ago, # | ← Rev. 2 →   0 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.