Блог пользователя bully....maguire

How to solve problem D in codeforces global round 6 (1266D)
Автор bully....maguire, история, 5 лет назад, По-английски

https://mirror.codeforces.com/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://mirror.codeforces.com/contest/1266/submission/67106641

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

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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});
	}
→ Ответить
  • »
    »
    5 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить