Single Round Match 757

Do you start to announce writers before the round?

The link doesn't work for me. The correct link is misof.

Error log:

TypeError: Cannot read property 'handle' of null
    at p (chunk-1556278029512.js:1)
    at $o (main-1556278029512.js:100)
    at wa (main-1556278029512.js:100)
    at ji (main-1556278029512.js:100)
    at Vi (main-1556278029512.js:100)
    at Cs (main-1556278029512.js:100)
    at Ts (main-1556278029512.js:100)
    at ys (main-1556278029512.js:100)
    at Ji (main-1556278029512.js:100)
    at Object.enqueueSetState (main-1556278029512.js:100)
...

Why is it high though? There are only 6.6k reachable states with the current constraints, so even if we multiply it by 2^9 it'll be still not that large.

There are various factors that make problems "harder" (i.e., make success rates lower): requires hard-to-notice idea, requires the knowledge of a bit advanced algorithm, requires lengthy implementation, the sample intentionally excludes corner cases, the TL is tight, etc.

I understand that misof is trying to make problems easier. My impression is that this is done by lowering the level of ideas. However there are other ways to make problems easier even if we require the same level of ideas. Making problems harder by tight TL feels like a "waste" of success rates.

For example, I think the easies of both SRM 757 and 756 are very nice. They definitely require observation for me, and probably for other reds too. I think they are enjoyable for reds too and can be good candidates of easy Mediums.

I misread the problem as if the players can set at most one pile on fire, and kept wondering why the hell piles of size n-1 win the game.

There is an observation that the number of states where the second player wins is just 156. Therefore, if your solution is not fast enough, you can notice this observation and precalculate answers locally.

You can use a max heap to always choose the most unfavorable color -- the ones who need more of their kind to be whole (F).

Here is the code:

	int fewestSocks(int C, int F, vector <int> s) {
		
		int n = s.size();
		
		priority_queue<pair<int, int> > max_heap;
		
		for(int i = 0; i < n; i++) {
		
			max_heap.push(make_pair( F, s[i])); // (requirement, available) 			
		}
		
		int ans = 0;
		
		while((C > 0) && !max_heap.empty()) {
		
			pair<int, int> t = max_heap.top(); 
			
			ans++;
			
			max_heap.pop();
			
			t.second --; // inventory down by one
			t.first --; //  so requirement is also down by one
			
			if (t.first == 0) { C--; t.first = F; }
			
			if (t.second != 0) max_heap.push(t);
			
		}
			
		if(C > 0) return -1;
		return ans;

	}

Sorry for the delay, the editorial got lost on its way to you. Here's the draft (and please mention me by name to send me a notification if there is a similar issue in the future).

Editorial