how come your name is mango lassi?

ratist :D

So the guy likes Petr's daughter :p

wake up now..its about time

It's not you who got a better rank than tourist, why R U so excited?

E1 was bitmask dp with complexity $$$O(3^n*m)$$$, I tried to improve it to $$$O(2^n*m+3^n*n)$$$ by only considering top 12 results for every bitmask, but somehow got TLE.

First realize you'll need at most N columns (with the N largest elements), then do a DP on all columns:

f(x,mask) = max sum you can do for rows in mask (it is a bitmask), starting from column X

I think I solved it in $$$O(2^n n^3)$$$, by taking only the $$$n$$$ columns with largest maximum, and during a bitmask dynamic programming, transferring grid by grid.

Same as E1, just notice that you only need to sort columns by their maxima and take the top min(N, M) (if the sorted order isn't unique, just pick one). Proof: let's assume $$$M > N$$$, assign a column to each row maximum in the final solution and look at the smallest of these columns (in the picked order) that's not among the top $$$N$$$. If there's just one row maximum in this column, you can replace it by a column from the top $$$N$$$, suitably shifted. If there's more than one, you've chosen less than $$$N$$$ columns, so you can just add a column from the top $$$N$$$ and move one row maximum to it. Both cases result in one more of the top $$$N$$$ columns being chosen, so if you repeat this as long as possible, you'll either end up with the top $$$N$$$ columns all containing row maxima or no other columns containing row maxima. However, the former also implies there are no other columns containing row maxima, since there are just $$$N$$$ of them.

While Errichto didn't answer you, try watching his video of preration of problem H.

https://www.youtube.com/watch?v=IaViSV0YBog

My solution involves division only at the beginning and at the end, the rest is obviously numerically stable:

private double solveOne(List<TaskH.Segment> segments) {
            int n = segments.size();
            for (int i = 0; i < n; ++i) {
                TaskH.Segment s = segments.get(i);
                s.ptr = i;
                s.curEnergy = 0.0;
                s.maxEnergy = (s.right - s.left) / s.s;
                s.minEnergy = -(s.right - s.left) / (s.s + 2);
            }
            List<TaskH.Segment> segmentsByS = new ArrayList<>(segments);
            Collections.sort(segmentsByS, new Comparator<TaskH.Segment>() {
 
                public int compare(TaskH.Segment o1, TaskH.Segment o2) {
                    int z = Double.compare(o2.s, o1.s);
                    if (z == 0) {
                        z = Integer.compare(o2.left, o1.left);
                    }
                    return z;
                }
            });
            TreeSet<TaskH.Segment> available = new TreeSet<>(new Comparator<TaskH.Segment>() {
 
                public int compare(TaskH.Segment o1, TaskH.Segment o2) {
                    return o1.ptr - o2.ptr;
                }
            });
            available.addAll(segments);
            for (TaskH.Segment s : segmentsByS) {
                if (s.s == 0.0) break;
                s.alive = false;
                available.remove(s);
                NavigableSet<TaskH.Segment> after = available.tailSet(s, false);
                double capacity = s.maxEnergy - s.curEnergy;
                double spent = 0.0;
                while (!after.isEmpty()) {
                    TaskH.Segment t = after.first();
                    if (t.alive) {
                        double t1 = t.curEnergy - t.minEnergy;
                        double t2 = capacity - spent;
                        double transfer = Math.min(t1, t2);
                        spent += transfer;
                        t.curEnergy -= transfer;
                        if (t1 <= t2) {
                            available.remove(t);
                        } else {
                            break;
                        }
                    }
                }
                s.curEnergy += spent;
            }
            double res = 0.0;
            for (TaskH.Segment s : segments) {
                double v = (s.right - s.left - s.curEnergy * s.s) / (s.right - s.left + s.curEnergy);
                res += (s.right - s.left) / (s.s + v);
            }
            return res;
        }

In short, there is no issue with catastrophic cancellation because incorrectly computing some sum as $$$S + e$$$ instead of $$$S$$$ gives us a new value $$$V - e$$$ instead of $$$V$$$ and the errors cancel out. And the formal proof of the whole thing should use absolute errors only but that's fine because we never get huge numbers.

Could E1 have been solved entirely with implementation, or did it require dp?

Yes, exactly.

I used DSU to solve D.

Create graph, for each connected component with x vertices you can satisfy x-1 guests.

D is just M — (sum of sizes of connected component — number of connected components)... so yes, if you count any graph traversal to be greedy

Did you sort the DAG adjacency lists by the lexicographical order of numbers or by value? The latter is wrong.

I thought about fast Dijkstra with smth like trie and overloading comparator in set using this trie and binary jumps on it (LCA). But don't have enough time to finish idea and implement

Store numbers in trie lca can be used to compare them.

If one simply 1) compute minimum number of digits for reaching each node using Dijkstra; and 2) sort adjacency lists by lexicographical order; and 3) perform a greedy DFS on the resulting graph, making sure that the number of digits used is always equal to the minimum, one will get WA on test 47. (https://codeforces.com/contest/1209/submission/60551210)

For example, if there existed an edge between node 1 and 2 with number 1, between 2 and 3 with number 2, and between 1 and 3 with number 11, this algorithm will choose 1->2->3, not 1->3.

First, let's add some fake nodes on every edge separating number written on it by its digits. For example for the edge AB with 123 on it you create two more nodes and connect them like A-1-F1-2-F2-3-B.

After that you can assume that you need to find the shortest path by the number of edges in this graph for each initial vertex, and choose the lexicographically smallest one among all paths with the smallest length, because numbers with bigger length in digits are like bigger). To do so you can run some sort of bfs.

Suppose that you want to maintain all classes of equal by value paths with length x. To add one more edge, you iterate over all nodes in current level of bfs and add an ordered pair of (current class of node, digit on edge to the node in the next level) to current possibilities of going further. After that you need to select the smallest pair lexicographically for each node in the next level and update your classes just like in a suffix array building in O(n log n).

UB.

You should test it in custom invocation tab.

Agreed, my code for E2 took like an 30-40 minutes of coding+debugging, while I needed <10mins to read, code & submit G1. And I didn't even read G1 until quite late, because I expected it to be more like G-level problem

E1 is fine because I can optimize its code for E2. G1 however should not exist.

I believe subtasks are good at differentiating people who 1) cannot solve neither E1 nor E2, 2) those who can solve only E1, 3) those who solve E1 and after an hour come up with a solution for E2, and 4) good programmers who solve E2 in the first place.

G1 took me longer to figure out than E1+E2. I looked at E2, "hmm if $$$N=M$$$ then just subset DP in $$$O(4^N)$$$ and seems like I can sort the columns and take top $$$M$$$", then I checked if the second observation holds, wrote a solution, submitted, done. F killed me, I barely submitted and I'm really not sure if it's going to pass systests.

Very true, I don't see any point in these subtasks except for wasting participant's time on solving some partial cases of the problem. Yet for some reason they become more and more popular on codeforces. This has to stop.

"Additionally, since it was so much easier than F, the optimal strategy would have been to solve it before writing F." — and what is wrong with that? Recommended strategy is solve problems in increasing number of points so of course you should try reading and solving G1 before F.

And G1 makes it kind of 'unworth' solving G2, as it's much more difficult than F and deserves more points. QwQ

By the way, it leads to a result that solving H offers 4000 points while solving G only results in 2250. Just look at the scoreboard: ABCDEFG1H always ahead of ABCDEFG.

UPD: The problems themselves are quite awesome, though. Just hope a better score distribution.

I'm not sure but maybe finding the longest non-decreasing subsequence and marking all elements in it as 1 and if the rest of the elements aren't in sorted order there's no solution otherwise mark others as 2.

Create a sequence X with zeros. For every set of positions of the same value, for the segment between first and last occurrence add +1 in X. Then, we're looking for minima in X and between every two consecutive minima: a number that occurs most times. If for first occurrence of a value you store the number of occurrences of this value then the whole thing can be done with a segment tree.

Marcin_smu did it easier, without any interval operations. I don't know how though.

#include <bits/stdc++.h>
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

struct Node {
	int small, lazy;
	int max_pref, between, max_suf, any_max;
	void merge(Node& L, Node& R) {
		assert(lazy == 0);
		any_max = max(L.any_max, R.any_max);
		if(L.small == R.small) {
			max_pref = L.max_pref;
			between = L.between + max(L.max_suf, R.max_pref) + R.between;
			max_suf = R.max_suf;
		}
		else if(L.small < R.small) {
			max_pref = L.max_pref;
			between = L.between;
			max_suf = max(L.max_suf, R.any_max);
		}
		else { // L.small > R.small
			max_suf = R.max_suf;
			between = R.between;
			max_pref = max(L.any_max, R.max_pref);
		}
		small = min(L.small, R.small);
	}
	void increase(int by) {
		small += by;
		lazy += by;
	}
	void set(int x) {
		// I am leaf
		max_pref = 0;
		between = 0;
		max_suf = x;
		any_max = x;
	}
};
vector<Node> tree;
int BASE;
const int SET = -1, ADD = -2;
void rec(int id, int low, int high, int q_low, int q_high, int type, int x) {
	if(high < q_low || q_high < low) {
		return;
	}
	if(q_low <= low && high <= q_high) {
		if(type == SET) {
			debug() << "set" imie(id) imie(x);
			assert(low == high); // leaf
			tree[id].set(x);
		}
		else if(type == ADD) {
			tree[id].increase(x);
			debug() << "increase" imie(id) imie(x);
		}
		else {
			assert(false); // unknown type
		}
		return;
	}
	for(int c : {2 * id, 2 * id + 1}) {
		tree[c].increase(tree[id].lazy);
	}
	tree[id].lazy = 0;
	int last_left = (low + high) / 2;
	rec(2 * id, low, last_left, q_low, q_high, type, x);
	rec(2 * id + 1, last_left + 1, high, q_low, q_high, type, x);
	tree[id].merge(tree[2*id], tree[2*id+1]);
}

const int nax = 2e5 + 5;
set<int> pos[nax]; // positinos with this value

void turn_off(int value) {
	if(!pos[value].empty()) {
		int L = *pos[value].begin();
		int R = *pos[value].rbegin();
		if(L < R) {
			debug() << "-1 " imie(L + 1) imie(R);
			rec(1, 0, BASE - 1, L + 1, R, ADD, -1);
		}
		debug() << "SET" imie(L) imie(0);
		rec(1, 0, BASE - 1, L, L, SET, 0);
	}
}
void turn_on(int value) {
	if(!pos[value].empty()) {
		int L = *pos[value].begin();
		int R = *pos[value].rbegin();
		if(L < R) {
			debug() << "+1 " imie(L + 1) imie(R);
			rec(1, 0, BASE - 1, L + 1, R, ADD, +1);
		}
		debug() << "SET" imie(L) << pos[value].size();
		rec(1, 0, BASE - 1, L, L, SET, pos[value].size());
	}
}
	
void add(int i, int value) {
	debug();
	debug() << "add" imie(i) imie(value);
	turn_off(value);
	pos[value].insert(i);
	turn_on(value);
}
void rem(int i, int value) {
	turn_off(value);
	pos[value].erase(i);
	turn_on(value);
}


int main() {
	int n, q;
	scanf("%d%d", &n, &q);
	BASE = 1;
	while(BASE < n) {
		BASE *= 2;
	}
	tree.resize(2 * BASE);
	for(int i = 0; i < 2 * BASE; ++i) {
		tree[i].small = 4 * n;
	}
	vector<int> a(n);
	for(int i = 0; i < n; ++i) {
		scanf("%d", &a[i]);
		add(i, a[i]);
	}
	for(int tt = 0; tt <= q; ++tt) {
		if(tt != 0) {
			int i, x;
			scanf("%d%d", &i, &x);
			--i;
			rem(i, a[i]);
			a[i] = x;
			add(i, a[i]);
			
		}
		debug() << imie(tree[1].max_pref) imie(tree[1].between) imie(tree[1].max_suf) imie(tree[1].any_max);
		printf("%d\n", n - (tree[1].max_pref + tree[1].between + tree[1].max_suf));
	}
	debug() << imie(a);
}

A DSU based implementation of G1,
https://codeforces.com/blog/entry/69791?#comment-542689

This meme suggests that it was good to have subtasks in E and G. Was that intended? ;p (I messed up)

The goal of subtasks for E and G was to make the qualification (for the event) nice and without difficulty gaps. I agree that G1 should be lower-scored or non-existing, sorry about that. I don't think there was any tester that solved all problems to find the difficulty gap between F and G. I asked some of my friends to test G or H, and other testers mainly solved easier problems. There just aren't usually strong people that have enough time to test everything :( and this contest was kind of rushed so we didn't have time for an editorial, sorry for that too.

I was one of people that agreed for that subtask and explained a reason above. Indeed, the scoring was bad though.

can't see video.

Yay, now I can watch you fail F!

#

What a beautiful time complexity XD

NO!! become purple first

Check out this explanation using DSU, https://codeforces.com/blog/entry/69791?#comment-542689

I'm not aware of any and I didn't think about it. The only thing I did there was to write some randomized approach to break tests.

It is out now! Hope you enjoyed the contest!

Editorial

There's no DSU in the optimal solution.

Try this 4 2

1 1

10 10

10 1

1 10

There is no way to get 40, in fact the answer is 31. Your approach works only with N<=3.