Codeforces Aim Tech Round 3 Editorial

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

Tutorial is loading...

Code

int main() {
  int n, b, d;
  std::cin >> n >> b >> d;

  int current_size = 0;
  int result = 0;
  int x;
  for (; n > 0; --n) {
    std::cin >> x;
    if (x > b) {
      continue;
    }
    current_size += x;
    if (current_size > d) {
      ++result;
      current_size = 0;
    }
  }

  std::cout << result << "\n";
  return 0;
}

Tutorial is loading...

Code

const int MAXN = 100000;

int x[MAXN];

int main() {
  int n, A;
  scanf("%d %d", &n, &A);
  if (n == 1) {
    printf("0\n");
    return 0;
  }
  for (int i = 0; i < n; i++) {
    scanf("%d", &x[i]);
  }
  int first_max = -2e6;
  int second_max = -2e6;
  int first_min = 2e6;
  int second_min = 2e6;

  for (int i = 0; i < n; i++) {
    if (x[i] > second_max) {
      second_max = x[i];
      if (second_max > first_max) {
        swap(second_max, first_max);
      }
    }
    if (x[i] < second_min) {
      second_min = x[i];
      if (second_min < first_min) {
        swap(second_min, first_min);
      }
    }
  }
  printf("%d\n", min(first_max - second_min + min(abs(A - first_max), abs(A - second_min)),
                     second_max - first_min + min(abs(A - second_max), abs(A - first_min))));

  return 0;
}

Tutorial is loading...

Code

void solve() {
  string s;
  cin >> s;
  for (int i = 0; i < s.length(); ++i) {
    if (s[i] == 'a') {
      continue;
    }
    int j = i + 1;
    while (j < s.length() && s[j] != 'a') {
      ++j;
    }
    for (int r = i; r < j; ++r) {
      --s[r];
    }
    cout << s << "\n";
    return;
  }

  s.back() = 'z';
  cout << s << "\n";

}

Tutorial is loading...

Code

void imp() {
  cout << "Impossible\n";
  exit(0);
}

ll invtriange(ll x) {
  ll l = 1, r = 1000000;
  while (r - l > 1) {
    ll m = (l + r) / 2;
    if (m * (m - 1) / 2 > x) r = m;
    else l = m;
  }
  if (l * (l - 1) / 2 != x) {
    imp();
  }
  return l;
}

int main() {
  vvl a(2, vl(2));
  for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) {
    cin >> a[i][j];
  }
  if (a[0][0] + a[0][1] + a[1][0] + a[1][1] == 0) {
    cout << "0\n";
    return 0;
  }
  ll c0 = invtriange(a[0][0]);
  ll c1 = invtriange(a[1][1]);
  if (a[0][0] == 0 || a[1][1] == 0) {
    if (a[0][1] + a[1][0] == 0) {
      if (c0 == 1) c0 = 0;
      if (c1 == 1) c1 = 0;
      cout << string(c0, '0') << string(c1, '1');
      return 0;
    }
  }
  if (c0 * c1 != a[0][1] + a[1][0]) {
    imp();
  }
  string s(c0 + c1, '0');
  for (int i = 0; i < s.size(); ++i) {
    if (c0 == 0 || a[0][1] < c1) {
      s[i] = '1';
      a[1][0] -= c0;
      --c1;
    } else {
      a[0][1] -= c1;
      --c0;
    }
  }
  cout << s << endl;
  return 0;
}

Tutorial is loading...

Code

int n;
vector<vector<int>> g;
vector<int> cnt;

int min_mx = 1e9;
int center = -1;

void dfs(int v, int p) {
	cnt[v] = 1;
	int mx = 0;
	for (int to : g[v]) {
		if (to == p) {
			continue;
		}
		dfs(to, v);
		cnt[v] += cnt[to];
		mx = max(mx, cnt[to]);
	}
	mx = max(mx, n - cnt[v]);
	if (mx < min_mx) {
		min_mx = mx;
		center = v;
	}
}

vector<pair<int, int>> subtrees;
vector<int> ans;

void dfs1(int v, int p, int sum_other, int prev) {
	if (sum_other <= n / 2) {
		ans[v] = 1;
	}
	for (int i = 0; i < 2 && i < subtrees.size(); ++i) {
		if (subtrees[i].second == prev) {
			continue;
		}
		if (n - cnt[v] - subtrees[i].first <= n / 2) {
			ans[v] = 1;
		}
	}
	for (int to : g[v]) {
		if (to == p) {
			continue;
		}
		dfs1(to, v, sum_other, prev);
	}
}

void solve() {
	cin >> n;
	g.resize(n);
	cnt.assign(n, 0);
	for (int i = 1; i < n; ++i) {
		int a, b;
		cin >> a >> b;
		--a; --b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	dfs(0, 0);

	assert(center != -1);
	ans.assign(n, 0);
	ans[center] = 1;
	dfs(center, center);
	int sum_all = 0;
	for (int to : g[center]) {
		subtrees.emplace_back(cnt[to], to);
		sum_all += cnt[to];
	}
	sort(all(subtrees));
	reverse(all(subtrees));

	for (int to : g[center]) {
		dfs1(to, center, n - cnt[to], to);
	}

	for (int i = 0; i < n; ++i) {
		cout << ans[i] << ' ';
	}
	cout << "\n";

}

Tutorial is loading...

Code

class FixFlow {
public:
	void solve(std::istream& in, std::ostream& out) {
		int n, m;
		in >> n >> m;
		int s = n;
		int t = n + 1;
		MinCostFlow<int, int> flow(n + 2);
		vector<int> balance(n);
		int INF = 1000000000;
		flow.addEdge((size_t) (n - 1), 0, INF, 0);


		int defaultAnswer = 0;
		for (int i: range(m)) {
			int a, b, c, f;
			in >> a >> b >> c >> f;
			--a, --b;
			balance[a] += f;
			balance[b] -= f;
			if (f <= c) {
				flow.addEdge(a, b, c - f, 1);
				flow.addEdge(a, b, INF, 2);
				flow.addEdge(b, a, f, 1);
			} else {
				// f > c
				defaultAnswer += f - c;
				flow.addEdge(a, b, INF, 2);
				flow.addEdge(b, a, f - c, 0);
				flow.addEdge(b, a, c, 1);
			}
		}

		int sumB = 0;
		for (int i: range(n)) {
			if (balance[i] > 0) {
				flow.addEdge(i, t, balance[i], 0);
				sumB += balance[i];
			} else {
				flow.addEdge(s, i, -balance[i], 0);
			}
		}

		auto res = flow.findFlow(s, t, MinCostMaxFlowStrategy());
		assert(res.flow == sumB);
		out << res.cost + defaultAnswer << "\n";
	}
};

Tutorial is loading...

Code

class MAI {
public:
	void solve(std::istream& in, std::ostream& out) {
		int N, m;
		int a, b;
		int k;
		in >> N >> m >> a >> b >> k;
		using Z = ZnConst<1000000007>;
		Z p = Z::valueOf(a) / b;
		Z q = 1 - p;

		// dp[r'] = sum l < r <= r' d[l][r]
		vector<Z> dp(m + 1, Z());
		dp[m] = 1;

		vector<Z> powersP(k + 1), powersQ(k + 1);
		powersP[0] = powersQ[0] = 1;
		for (int i: range(k)) {
			powersP[i + 1] = powersP[i] * p;
			powersQ[i + 1] = powersQ[i] * q;
		}

		vector<Z> fact = factorials<Z>(k + 1);
		vector<Z> invfact = fact;
		for (auto& x: invfact) {
			x = 1 / x;
		}

		auto get_p_one_side = [&](int l) {
			if (l > k) {
				return Z();
			}
			return powersP[l] * powersQ[k - l] * fact[k] * invfact[l] * invfact[k - l];
		};

		for (int iter: range(N)) {
			vector<Z> dp_one(m + 1, Z());
			Z sumPl, sumPlDpl;

			for (int r: inclusiveRange(m)) {
				//new_d[l][r] = p[l] * p[n - r] * (have_something - dp[l] - dp[n - r])
				Z have_something = dp.back();
				dp_one[r] = get_p_one_side(m - r) * (
						have_something * sumPl - sumPlDpl - sumPl * dp[m - r]
				);
				sumPl += get_p_one_side(r);
				sumPlDpl += get_p_one_side(r) * dp[r];
			}

			for (int i: range(m)) {
				dp_one[i + 1] += dp_one[i];
			}

			dp = move(dp_one);
		}

		out << dp.back();
	}
};

Comments (57)

Show archived | Write comment?

sherlo_code

8 years ago, # |

Hi, I am not able to understand the string generation part of Recover string problem div2 D. Please explain the intution and other insight for the problem.

Thanks All

→ Reply

zeliboba

8 years ago, # ^ |

I rewrote editorial, please check.

haleyk100198

Mine solution is a bit different from the bubble sorting which the editorial provided, but I hope this helps.

Consider that for each '1's in the string generated, the amount of sub-sequences of "10" that contains this '1' equals to the amount of '0' after it. By this fact, we can build a greedy solution and determine if '1' or '0' should be put on position i.

Case 1: There are more unused '0's than "10" that are yet to be built -> put '0' here since '1' will not fulfill the situation.

Case 2: The counterpart of case 1 -> put '1' here and it won't violate the situation.

This works because we have checked that cnt(1) * cnt(0) = cnt(01) + cnt(10), and this greedy solution can always get a result string of exactly c sub-sequences of "10".

The time complexity is O(n).

The same idea is described in the end of editorial for this problem

dsharma080

← Rev. 2 →

For the linear time solution approach try considering the following example:

Suppose given input of : 1 4 2 3

Then number of 0's=2

And number of 1's=3

Clearly there will be a solution ( (4+2)==2*3 )

Then we are moving from the string of 00111 to the desired string as follows (in braces follows the aii's):

00111 {1,6,0,3}

Shift one zero to end

01110 {1,3,3,3}

Now shifting the other zero will not lead to ans as a01 which is 3 now will only decrease.

Then move the 0 just moved to the left by the amount needed to equate it to the a01 given in the input ( 4-3=1)

Moving that 0 left gives the desired ans

01101 {1,4,2,3}

egor.okhterov

← Rev. 3 →

There is also online algorithm.

Suppose, we know the string should have n zeros and m ones. It means the total length should be n + m.

We will create our string one character at a time from left to right. At each position we have a choice — either we put 0 or we put 1. Let's start from the first position.

If we place 0 as the first character, we will have m pairs of the type 01 (because we will have to put m ones after the current zero in the future). If we place 1 as the first character, we will have n pairs of the type 10.

At i'th position we know that we should have a01 and a10 pairs of appropriate type. Placing 0 at current position inevitably leads to generating some amount of pairs of type 01. If this amount is greater than a01, it means that we cannot place 0 in the current position.

This logic leads to the following code.

while (n + m)
{
    if (a01 >= m)
    {
        cout << 0;
        a01 -= m;
        n--;
    }
    else
    {
        cout << 1;
        a10 -= n;
        m--;
    }
}

I am lost in the prove of Div1C... Could someone explain the prove a bit less formal?

zscoder

+31

Here's a simpler explanation for Div.1 C :

Fix the centroid as the root of the tree (can be found in O(n)). Now, for a given vertex x, we need to see if it can be a centroid by replacing an edge. Let the root be r and the subtrees be S₁, S₂, ..., S_k. The key is to note that if we remove x, the components in the subtree of x is definitely small (i.e. at most $\text{[math]}$ ), since r is the centroid. Also, the link from it to its parent is removed. Also, an edge replacement will clearly remove an edge from the remaining tree (the tree obtained after removing x's subtree) and replace it with an edge connecting to x (otherwise it doesn't change anything). Thus, when x is removed, the newly placed edge is removed as well. This means that we only need to find the edge to remove in the remaining tree to minimize the maximum size of the two resulting components. Also, this can be thought as taking a subtree out of the remaining tree. Since the subtree size is at most $\text{[math]}$ (r is the centroid), we need to maximize the size of the subtree we take, which does not contain r. Now, it is clear that we'll remove one of S₁, S₂, ..., S_k and we can easily calculate the answer by storing the two maximum subtree sizes among these subtrees.

Code : 20156041

CMaster

Great solution!

Nams

Your solution definitely seems to be easier to understand then the one given in editorial. But still I am unable to understand the crux of it. I get the solution till the part where you have removed x from the tree and link of par[x] and x is removed. After that I don't get the idea where you have placed the new edge. Can you please help me out here?

After you remove the link between par[x] and x, the graph effectively split into few trees, those that are "below" x and the big tree that contains the original root. The trees "below" x are small, since the root is the centroid. So, we need to only change the size of the big tree. Thus, it only makes sense to remove an edge from the big tree. Where do we add the extra edge? We just add it such that one of its endpoints is x, so when x is removed this edge disappears as well. Now, we are only left with the problem in determining which edge from the big tree to remove, which is simple.

Thanks for the help, now I get how it works. =)

kronos96

Regarding Div.1 C, I have 1 query. Why is it that only one of the subtrees of the original centroid(root) will be disconnected ? why cannot centroid be included in the removed portion ? I cant seem to prove this fact on my own. Pls help!

sanket407

can u explain case when bestidx == -2 comes into play in your solution ? ie when sub[i] == best !

plz find bug in my code :: !! http://codeforces.net/contest/709/submission/20545506

MedoN11

Even though I kept getting WA on case n = 1, there's "a don't think" way of solving Problem B using DP.

Run DP from left, and from right. Choose a point you start at,and depending on your direction keep multiplying the transitions by 2. Once you choose your point, don't, and just go forward/backward normally.

You should also take care of that you skip at most one item using a flag.

Not the best solution, but an easy way to solve it.

TaoSama

+25

can someone please explain how to solve div 1 D ? or is there a general method to solve this kind of flows ?

Nezzar

Consider the case where c_i = ∞ and there are no edges directed from or to the source and the sink. Let in_i and out_i be the total amount of input flow (flows towards vertex) and output flow (flows from vertex) of vertex i respectively. Let d_i be out_i - in_i, then we want to make d_i = 0 for all i.

Build a costed flow graph with n + 2 vertex including a new source and sink, and the n representative of the vertices in the original graph. For every i, if d_i > 0, then construct an edge from source to i with cost 0 and flow d_i. Otherwise, construct an edge from i to sink with cost 0 and flow - d_i.

Consider every edge in the original graph from u to v with flow f, Build an edge from u to v with cost 1 and flow ∞ in the costed flow graph. Build an edge from v to u with cost 1 and flow f in the costed flow graph. Compute the min-cost-max-flow of the costed flow graph, and the minimum cost is the cost required to fix the flow.

Reasoning is not hard after the graph is built, but as my explanation skill is horrible I tend to skip this part. After you see the reasoning, the handling of c_i and source and sink should be trivial. (Though I overcomplicated a lot of things and got WA... TAT)

cool, I've already found the tut in icpc-camp blog, great thanks all the same. wow, classical flow problem, feasible flow, and based on it, this problem will be solved.

arasmus

7 years ago, # ^ |

can u plz mention the link of the tutorial

← Rev. 4 →

sorry for replying late.

there is only a tutorial in Chinese.

original

[mine](http://taosama.com/2016/08/26/AIM%20Tech%20Round%203%20(Div.%201)%20D.%20Incorrect%20Flow%EF%BC%88%E6%9C%89%E6%BA%90%E6%B1%87%E5%8F%AF%E8%A1%8C%E8%B4%B9%E7%94%A8%E6%B5%81%EF%BC%89)

(I don't know why I can't post the link in the right way

cool

IuriG

In 709B, shouldn't we also pay attention for when we don't have to return to the point at the other side? For example, when the entry is: 2 5 2 8 We should only go to the leftmost checkpoint, but we shouldn't return to the rightmost checkpoint in order to pass through the right checkpoints because the only point that is to the right is the one we chose not to visit.

riadwaw

If you are not going to go to 8, then 2 is both leftmost and rightmost, and you need to go to it, and then to it again, but the second one cost you nothing

Bad example, sorry. What about 3 5 3 4 10 4 is the rightmost (ignoring 10, obviously), but there's no need to go to it since I've already passed through it

Then you go to the right first and to the left then

I see, thanks.

hellman_

Div1C:

(assume its root is w), remove an edge uw between its subtree and the remaining tree, and add an edge between x and u

I guess we need to add edge between x and w (since subtree is rooted at w and is detached).

Kostroma

Thank you, it will be fixed as long as codeforces manage to take the new version of editorial from polygon.

marvelousmangos

In the main post you mentioned cheaters. What exactly happened?

agul

+12

It happens from time to time, some guys send equal solutions for the problems and after the contest they are banned.

chezbgone

I think that the problem with problem A is that people did not realize that the "waste" is actually the juice and not the oranges you throw out. That is why I couldn't understand it at first.

PiyushArora01

Can anyone see this code for the strings question and tell me what's wrong with it? http://ideone.com/sFgcXB

PedroBortolli

When the string only has a's you are not doing anything, when you should. The problem says that we must find one non-empty substring and make the changes asked. So when you have "aaaa" for example, you must shift the last letter. In this case the output would be "aaaz".

I did that and now its giving TLE on test 27. Could you tell me what modification needs to be done?

A greedy algorithm works in this problem, so you can simply iterate through the letters, making the changes, until you find an "a". When you find it, break.

Now if you've made changes, print the string. If you haven't, shift the last letter. You don't really have to do all these ifs

Death_Scythe

It is because of the repeated string comparisons. The idea is very easy to implement, it shouldn't take that many lines of code.

http://codeforces.net/contest/709/submission/20125058

Swistakk

+15

That may be a very stupid challenge, but it is also possible to solve Div1E for constraints like m ≤ 10, n ≤ 10⁹ :P

Yeah, we also thought about it =)

ffao

In the last paragraph for Div1E, it seems you dropped the t - 1 index from sum_dp_r[t - 1][n]. It might be a bit obvious, but it confused me the first time I read it.

Thank you, it is fixed now.

bartek19121995

Hi. What is cnt array in Div1C (Centroids)? I have never heard this shortcut.

shdut

For div1 E,what's the a/b-the probability mean? Isn't it the probability that each block not been destroyed?

mnaeraxr

Where is the editorial for problem D?

RazvanD

-8

At the top of the editorial it says:

Here is the part of the editorial, other problems will come a bit later

It is already here btw

Are you telling me that if I code exactly what you said in editorial for problem D it will get AC? OK I will believe you.

I_love_Captain_America

ignore

MarioYC

In the editorial for C shouldn't the -1 in the inequality be +1?

AMR-KELEG

For problem Div2 D (Div1 B):

"If a01 + a10 ≠ c0·c1, then answer is impossible."

How do you get this formula? What does it really mean?

Thanks

brighterstill

You have c0 zeroes and c1 1's. number of ways of choosing one 0 and one 1 are (c0 choose 1)*(c1 choose 1) which is c0*c1. Now all such pairs will either be contributing to a01(if the zero you chose came before the one you chose) or a10(if the one you chose came before the zero you chose) . There is no other possibility. Hence a01 + a10 = c0.c1.

Diplomate

I can't get the point of problem C. When we remove the point which we want to turn into a centroid, do the incident edges get removed too?

k790alex

Yes. This splits you tree in several connected components.

0736TuT

Hi, I always get TLE on test 21... I passed the test point which n = 400000 but I can't pass the 399999 one lol

Is it random? I use bfs instead to avoid stackoverflow.

shahidul_brur

Why this tutorial is not attached as the contest materials in the contest page?

I've tried my best, but cf server didn't let me do this.

Oh! Probably MikeMirzayanov can do something..

Kostroma's blog