 # STICNOT - Sticky Notes Solution Code Explanation

Continuing the discussion from STICNOT - Sticky notes solution?:

Problem Clarification

Given values of N vertex and N-1 edges. You can perform 3 operations.

1. Swap vertex value
2. Swap edges value
3. Change vertex value - cost 1 coin per action.

You need to make all adjacent vertex values greater than or equal to the edge value i.e. av \ge be
Find out the minimum number of coins you need to satisfy the required condition.

Solution Explanation

Every edge value need two greater or equal vertex value.
To check it, we can use `priority_queue`.

• Take input and store edge and vertex value in a priority_queue, say `priority_queue<int> a, b;` [a for vertex value, b for edge value].
Code example:
``````  int n;
cin >> n;
priority_queue<int> a, b;
for (int i = 1, x, y, d; i < n; i++) {
cin >> x >> y >> d;
b.push(d);
}
for (int i = 0, d; i < n; i++) {
cin >> d;
a.push(d);
}
``````
• Count how many coins you need to achieve this, say `cnt = 0`
Priority_queue keep the maximum value at the top position in c++ (java keep the minimum value at the top position).

• Now checkout the maximum value of edge, if it is greater then the vertex value, then we need 2 coins to get maximum value. i, e, `cnt += 2` otherwise pop out the maximum vertex value. Now every edge need one maximum or equal vertex value to satisfy the condition.
Code Example:

``````  int cnt = 0;
if (b.top() > a.top()) {
cnt += 2;
b.pop();
} else {
a.pop();
}
``````
• Now loop throw all edges and check out the condition: av \ge be if condition is false, need one coin to fix it. We always use coin to change minimum vertex value, that’s why we don’t pop out vertex value. Pop out vertex value from a if the condition is true. Here is the code example:
``````  while (!b.empty()) {
if (b.top() > a.top())
cnt++;
else
a.pop();
b.pop();
}
``````
• Now print out the minimum coins (cnt) you need to satisfy the required condition.
``````   cout << cnt << "\n";
``````

That’s all Solution Code
``````#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define sz(a) a.size()
#define all(a) a.begin(), a.end()
#define w(a) std::cerr << #a << " : " << (a) << "\n";

void solve() {
int n;
cin >> n;
priority_queue<int> a, b;
for (register int i = 1, x, y, d; i < n; i++) {
cin >> x >> y >> d;
b.push(d);
}
for (register int i = 0, d; i < n; i++) {
cin >> d;
a.push(d);
}
int cnt = 0;
if (b.top() > a.top()) {
cnt += 2;
b.pop();
} else {
a.pop();
}

while (!b.empty()) {
if (b.top() > a.top())
cnt++;
else
a.pop();
b.pop();
}
cout << cnt << "\n";
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif

register int tc;
cin >> tc;
while (tc--) solve();
return 0;
}
``````

Happy Coding 4 Likes

A nice editorial !!!

1 Like

@naveen19991124 Thanks There is one small little bug with your solution. What if there is exactly one vertex value greater than the max edge value, then you’ll need 1 coin to make the min vertex value >= the max edge value!
@smile_forever

@sahil0907 Nope bro It’s also included in this code, When there is only one vertex value is greater than edge value, then we need another maximum value to satisfy the required condition.

If only one vertex value is greater then edge value, then we pop out the maximum vertex value at first using if->else condition (else condition executed). then we check out the 2nd next vertex value with edge value, if 2nd maximum value is less than edge value, then cnt++…
Please check out the code for clarification:

``````  if (b.top() > a.top()) {
cnt += 2;
b.pop();
} else {
a.pop();
}

while (!b.empty()) {
if (b.top() > a.top())
cnt++;
else
a.pop();
b.pop();
``````

Oh thanks, got it!
Could you help me with my TLE?
My Submission

@sahil0907 Your code should be time optimized. Just follow few steps to optimize it. There is too many input, therefor you should use `ios_base::sync_with_stdio(false); cin.tie(0);` OR `scanf, printf`. Avoid `endl` to print new line, Just use `"\n"` instead `endl`. Only few optimization make your code faster, and now it takes only 0.40 sec Here is you AC Code.
Happy coding 2 Likes