bully....maguire's blog

How to solve problem D in codeforces global round 6 (1266D)
By bully....maguire, history, 5 years ago, In English

https://codeforces.net/contest/1266/problem/D

Editorial of the problem does not explains how to implement the solution .It only tells what conditions will hold after every operation and at the end (when optimal answer has been reached).

I read few submissions and they used set to solve the problem , for example : https://codeforces.net/contest/1266/submission/67106641

I will be very thankful if someone helps me to understand the solution .

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

I used two pointers. They respectively point a positive number and a negative number.


	int p1 = 1, p2 = 1;
	while (true) {
		while (a[p1] <= 0) p1++;
		while (a[p2] >= 0) p2++;
		if ((p1 > n) && (p2 > n)) break;
		ll k = min(a[p1], -a[p2]);
		a[p1] -= k;
		a[p2] += k;
		ans.pb({p1, p2, k});
	}
→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    ohhh. can u explain why it works and how u guessed that EDIT: Lol, i skipped editorial, sry)

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Noticed that there is no need to minimize the number of non-zero debts, only the total debt. So, keeping the total debt, the implementation is not unique and all of them can transform to each other. The following implementations can be all legal for the same query :

      1 3 10
2 4 10

      1 4 10
2 3 10

      1 3 5
1 4 5
2 3 5
2 4 5

      So I just choose one of them.

      I'm not sure that I got your point, so feel free to ask more.

      → Reply