EDIT: sorry for the mistake.. I am extremely sorry. I am changing it...Those who actually saw the message I apologize.

It is impossible for me to check every timezone and then get a lower bound of time upon crossing which this list is will be true for everyone. This solely serves the purpose of a reminder and also a blog for discussion of the competition problems as the editorial is published quite late over there. As far as I know the time is shown correctly. What else do you guys want?

Yeah it is a day later. See here. Click on 'Click here to see when coding begins in other time zones.'

People are too lazy. Looks like one of the lowest participation recently :(

Use breadth first search and bit mask.
Use a map to index each undecided edge to a number from 0 to k - 1.
Consider all possible subsets of nodes [pow(2, 20) of them] and see if each of them forms a clique taking into consideration both the decided and undecided edges.
If a certain subset does indeed form a clique push it into a vector of pairs, the pair being the size of the clique and an integer whose ith bit is set to 1 if the ith index corresponds to an undecided edge found in the clique.
Sort this vector and then iterate through it from biggest to smallest clique size.
Run bfs on each secondary value — the one that contains information about what the undecided edges needed to form it are, if it has not been visited.
For each clique you know that forming it could also include other undecided edges unrelated to it. So iterate through i from 0 to k and OR the current integer with (1 << i). Therefore insert these values into the bfs queue if they haven't been visited by a larger clique size previously.
Every time you visit a value in the current BFS you would add the size of the current clique to the total.
Each subset of undecided edges gets visited once, so time complexity is pow(2, k) * k.

1 is the right answer. What happens is 3 is stickied on A[0] i.e on 3. So only 2 causes a conflict . Hence ans = 1 conflict

For all tasks samples are designed to show the input/output format, and be a quick sanity check on the understanding of problem.

For some tasks, they are just not designed for checking correctness (for example, case analysis tasks).

Unlike pretest in codeforces, you could see what's in the examples. So in this task we are telling you "please check correctness by yourself." clearly.

Sometimes adding a seemingly strong test may cause experienced contestant to fail, for example: sadly tourist failed Medium in TCO15 semifinal while there is a very strong example.

"and should generally catch mistakes like this." : from my experience, there is always a way to fail even there are few strong examples. Bugs are very random so it is hard to predict what it could be before we see it. So please read your program again and make some testcases by yourself if you want to avoid bugs (If you watch Petr's video you could find he always do it, sometimes after submission).

Btw, if I were the writer I would like to include large random testcases in this particular task, but it is also acceptable for me to leave it weak if the writer wants. In Div1-Easy I suggested to add a strong example because there are lots of wrong algorithms.

Пусть A — множество вершин графа такое, что степень любой вершины в A равна 1, и при этом для любого ребра (v, w) либо , либо .

Рассмотрим оптимальный порядок покраски вершин.

Возьмём вершину и единственное инцидентное ей ребро (v, w). Если в рассматриваемом порядке v идёт перед w, ничего делать не будем, иначе поменяем их местами. Утверждается, что ответ от этого не увеличится. Действительно, перед новой позицией v множество покрашенных рёбер не изменится, между v и w — не увеличится, поскольку вершина v влияет только на одно ребро, которое в обоих порядках пока ещё не покрашено, после w — снова не изменится.

Теперь переставим v в начало. Опять же, v влияет только на одно ребро, которое становится покрашенным только после w. Значит, штраф для всех вершин, которые стояли перед v, не увеличится, а штраф за саму вершину v даже обнулится.

Так как после этих действий ответ не увеличился, а исходный порядок был оптимальным, то мы получили новый оптимальный порядок, в котором v стоит в начале. Применив все предыдущие операции ко всем вершинам множества A, получаем, что существует оптимальный порядок, начинающийся со всех вершин множества A (идущих в любом порядке, так как штраф за них и так нулевой).

I completely don't understand the difficulty of this task. It looks like "Hey, bruteforce 2^10 assignments of '?' to '0'/'1' and find maximal clique in graph with 38 vertices as you want". Even if we forget that most difficult part of this problem (finding clique) can be copypasted from... anywhere, coding from scratch clique finding doesn't worth 550 pts.

I get AC with simple bruteforce: let's find anticlique. Take vertice with maximal degree, and take it to anticlique (and not take all it's neighbours), or don't take it to anticlique. If there are only vertices with degree <= 2, it is set of paths and cycles and we can calculate answer in linear time. Complexity -- T(n) <= T(n-1) + T(n-4) <= 1.38ⁿ (multiplied by 2¹⁰), which passes easily. Also, there are very weak tests, I had to resubmit because I find stupid bug, but even my first bugged solution get AC.

You can do it in O(2^n / 2n) using meet-in-the-middle.
- Split vertices in two equal (almost equal) parts in such way that all ?-edges goes in the first part.
- For each subset of the second part find largest clique, contained in this subset. This can be done in O(2^ss), where s is the size of the part. Probably even O(2^ss²) would pass.
- For each subset of the first part that contains only ?-edges and 1-edges, we can find largest clique in the second part connected to this.
- So, we will have bunch of implications of the form "if subset S of ?-edges is taken, largest clique is at least x"
- Using this, we can find in O(2^ss) (or O(3^s)) for each subset of ?-edges size of larges clique.
- Sum up this.

#include <bits/stdc++.h>

using namespace std;

const int M = 21;

vector<string> g;
int n;
int da[1 << M], db[1 << M];
int cont[1 << M];
int sub[1 << M];

int in(int mask, int k) {
	return (mask >> k) & 1;
}

void calc(vector<int> a, int *d) {
	int m = a.size();
	
	auto conn = [&](int x, int y) -> bool {
		return g[a[x]][a[y]] != '0';
	};
	
	vector<int> f(m);
	for (int i = 0; i < m; ++i)
		for (int j = 0; j < m; ++j)
			if (conn(i, j))
				f[i] |= 1 << j;
	
	d[0] = 1;
	for (int mask = 0; mask < (1 << m); ++mask) {
		int pos = (1 << m) - 1;
		for (int k = 0; k < m; ++k)
			if (in(mask, k))
				pos &= f[k];
		
		for (int to = 0; to < m; ++to)
			if (in(pos, to)) {
				int nxt = mask | (1 << to);
				d[nxt] |= d[mask];
			}
	}
} 

void conv(int n, int *d) {
	for (int i = 0; i < n; ++i)
		for (int mask = 0; mask < (1 << n); ++mask)
			if (in(mask, i))
				d[mask] = max(d[mask], d[mask ^ (1 << i)]);
}
			
	
class Clicounting {
public:
	
	int count(vector<string> G) {
		g = G;
		n = g.size();
		
		set<int> A, B;
		for (int i = 0; i < n; ++i)
			B.insert(i);
		
		auto move = [&](int x) -> void {
			A.insert(x);
			B.erase(x);
		};
			
		for (int i = 0; i < n; ++i)
			for (int j = 0; j < n; ++j)
				if (g[i][j] == '?') {
					move(i);
					move(j);
				}
		
		for (int i = 0; i < n; ++i)
			if (A.size() < n / 2)
				move(i);
		
		vector<int> a(A.begin(), A.end()), b(B.begin(), B.end());
		int as = a.size();
		int bs = b.size();
		
		calc(a, da);
		calc(b, db);
		
		for (int mask = 0; mask < (1 << bs); ++mask)
			if (db[mask])
				db[mask] = __builtin_popcount(mask);
		conv(bs, db);
		
		int q = 0;
		for (int i = 0; i < as; ++i)
			for (int j = i + 1; j < as; ++j)
				if (g[a[i]][a[j]] == '?') {
					cont[(1 << i) | (1 << j)] |= 1 << q;
					++q;
				}
		
		for (int i = 0; i < as; ++i)
			for (int mask = 0; mask < (1 << as); ++mask)
				if (in(mask, i))
					cont[mask] |= cont[mask ^ (1 << i)];
		
		vector<int> f(as);
		for (int i = 0; i < as; ++i)
			for (int j = 0; j < bs; ++j)
				if (g[a[i]][b[j]] == '1')
					f[i] |= 1 << j;
		
		for (int mask = 0; mask < (1 << as); ++mask) 
			if (da[mask]) {
				int to = (1 << bs) - 1;
				for (int k = 0; k < as; ++k)
					if (in(mask, k))
						to &= f[k];
				
				int cur = cont[mask];
				int sz = __builtin_popcount(mask) + db[to];
				sub[cur] = max(sub[cur], sz);
			}
		
		conv(q, sub);
		
		int ans = 0;
		for (int mask = 0; mask < (1 << q); ++mask)
			ans += sub[mask];
		
		return ans;
	}
};

P.S. I think it is a nice task. Sad that brute-force solution passed. Probably author didn't want to cause TL problems for intended solutions.

Simulate the process backwards

int countfee(vector <int> x, vector <int> y) {
  int m = SZ(x);
  vector<int> dp(1 << m, 1e9);
  VI masks(50);
  REP (i, m) {
    masks[x[i]] |= (1 << i);
    masks[y[i]] |= (1 << i);
  }
  dp.back() = 0;
  FORD (mask, (1 << m) - 1, 1) {
    REP (v, 50) {
      mini(dp[mask & (~masks[v])], dp[mask] + __builtin_popcount(mask));
    }
  }
  return dp[0];
}

Here is another simple solution (by the writer subscriber):

import java.util.Arrays;

public class Gperm {
	public int countfee(int[] x, int[] y) {
		int result = Integer.MAX_VALUE;
		int n = x.length;
		int v = 50;
		
		for (int m = 0; m < (1 << n); ++m) {
			int[] deg = new int[v];
			for (int i = 0; i < n; ++i) if ((m & (1 << i)) > 0)
				deg[x[i]]++; else deg[y[i]]++;
			Arrays.sort(deg);
			int cur = 0;
			for (int i = 0; i < v; ++i) cur += (v - i) * deg[i];
			result = Math.min(result, cur);
		}
		
		return result;
	}
}

Yes, we rejudged all solution to Div1-Hard and you passed system test. Congratulation! Somehow the reference output was wrong (it was generated by an old solution).

Btw, how to solve hard?