### dalex's blog

By dalex, 3 years 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

 » 3 years 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?
•  » » 3 years ago, # ^ |   +7 I remember long time ago we concluded that it isn't, but maybe it's because we are orange.
 » 3 years 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.
•  » » 3 years ago, # ^ |   0 :(Maybe you have a countertest? I'll add it.
•  » » » 3 years ago, # ^ |   +8 I don‘t — actually 100 was approximation for log improvements and random order for achieving log on average :)
 » 3 years ago, # |   0 By the way, could you share the grader for N?
•  » » 3 years ago, # ^ |   0 madskillzIt is hardcoded for this problem, including the top-right corner starting position.
•  » » » 3 years 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'; } 
 » 3 years 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.
•  » » 3 years 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.
•  » » » 3 years ago, # ^ |   +30 Well, there was no way of requesting clarifications... ("Questions" tab is missing from this contest's Yandex interface.)
•  » » » » 3 years ago, # ^ |   0 I didn't know it's configured like this. Is it always the case on Opencups or was it a misconfiguration?
•  » » » » » 3 years 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?
 » 3 years ago, # |   0 What's the case 10 for F?
•  » » 3 years ago, # ^ | ← Rev. 3 →   0 try 4 0 6 2 8 6 14 10 12 
•  » » 3 years ago, # ^ |   0 Real test 105 0 4 2 10 6 12 8 18 14 16 
 » 3 years ago, # |   0 F. Thanks for the contest, I really enjoyed most of the problems! :)
 » 3 years 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?
•  » » 3 years 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<
•  » » » 3 years 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!
 » 3 years 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
•  » » 3 years ago, # ^ |   0 resolved :)
 » 3 years 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?
•  » » 3 years ago, # ^ |   +5
 » 3 years 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?
 » 3 years 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.