Samara Farewell Contest 2020 (XXI Open Cup, Stage 8, GP of Samara)

→ Обратите внимание

До соревнования
Codeforces Round 986 (Div. 2)
08:18:47
Зарегистрироваться »

*есть доп. регистрация

→ Трансляции

Codeforces Round 986 (Div 2) - Solution Discussion

Shayan

До начала 10:23:47

Всё →

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3821
3	Benq	3736
4	Radewoosh	3631
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3388
10	gamegame	3386

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	161
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя dalex

Samara Farewell Contest 2020 (XXI Open Cup, Stage 8, GP of Samara)

Автор dalex, 4 года назад, По-английски

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:

Обсуждение Samara Farewell Contest 2020 (XXI Open Cup, Grand Prix of Samara)

opencup, samara, farewell

+130

dalex
4 года назад
26

Комментарии (26)

Написать комментарий?

mango_lassi

4 года назад, # |

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?

→ Ответить

dalex

4 года назад, # ^ |

I remember long time ago we concluded that it isn't, but maybe it's because we are orange.

→ Ответить

helThazar

4 года назад, # |

← Rev. 2 →

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.

→ Ответить

dalex

4 года назад, # ^ |

Maybe you have a countertest? I'll add it.

→ Ответить

helThazar

4 года назад, # ^ |

I don‘t — actually 100 was approximation for log improvements and random order for achieving log on average :)

→ Ответить

mango_lassi

4 года назад, # |

By the way, could you share the grader for N?

→ Ответить

dalex

4 года назад, # ^ |

madskillz

It is hardcoded for this problem, including the top-right corner starting position.

→ Ответить

mango_lassi

4 года назад, # ^ |

+15

Thanks, I now got AC :)

#include <bits/stdc++.h>
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';
}

→ Ответить

dorijanlendvaj

4 года назад, # |

+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.

→ Ответить

dalex

4 года назад, # ^ |

-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.

→ Ответить

mnbvmar

4 года назад, # ^ |

+30

Well, there was no way of requesting clarifications... ("Questions" tab is missing from this contest's Yandex interface.)

→ Ответить

dalex

4 года назад, # ^ |

I didn't know it's configured like this. Is it always the case on Opencups or was it a misconfiguration?

→ Ответить

mnbvmar

4 года назад, # ^ |

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?

→ Ответить

dragoon

4 года назад, # |

What's the case 10 for F?

→ Ответить

ssor96

4 года назад, # ^ |

← Rev. 3 →

try

→ Ответить

dalex

4 года назад, # ^ |

Real test 10

→ Ответить

TheOneYouWant

4 года назад, # |

F. Thanks for the contest, I really enjoyed most of the problems! :)

→ Ответить

YaoBIG

4 года назад, # |

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?

→ Ответить

TheOneYouWant

4 года назад, # ^ |

← Rev. 2 →

+18

(btw, ld is long double in my code)

Spoiler


int 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<<setprecision(35)<<fixed;

		cout<<l<<ln;
	}

	

	return 0;
}

→ Ответить

YaoBIG

4 года назад, # ^ |

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!

→ Ответить

stostap

4 года назад, # |

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

→ Ответить

stostap

4 года назад, # ^ |

resolved :)

→ Ответить

LipArcanjo

4 года назад, # |

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?

→ Ответить

dalex

4 года назад, # ^ |

L, authors' solution

→ Ответить

AquaBlaze

3 года назад, # |

← Rev. 3 →

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?

→ Ответить

16silver

3 года назад, # |

← Rev. 2 →

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.

→ Ответить

Соревнования по программированию 2.0

Время на сервере: 10.11.2024 10:16:13 (j3).

Десктопная версия, переключиться на мобильную.

При поддержке