Epiphany 13.0
A: Gifts
Epiphany 13.0 A — Gifts
The minimum number of operations required to sort a list of $$$n$$$ gifts is $$$n−x$$$, where $$$x$$$ is the length of the longest sorted suffix.
Proof:
Let $$$k$$$ be the minimum number of steps required to sort the gifts. Observe that if $$$k$$$ steps are optimal, the first $$$k$$$ gifts must be moved, implying that the remaining $$$n-k$$$ gifts were already sorted in ascending order.
Consider the $$$n-k$$$ sorted gifts at the end. We can iteratively insert the unsorted gifts into this suffix to achieve complete sorting: Pick the first unsorted gift and place it in its correct position within the sorted suffix, maintaining the sorted order. Repeat this process for the remaining $$$k−1$$$ unsorted gifts. This takes $$$k$$$ operations.
#include<bits/stdc++.h>
#define forn(l,n,i) for(int i=l;i<n;i++)
#define ll long long int
using namespace std;
void solve(){
int n;
cin>>n;
vector<int> v(n);
forn(0,n,i) cin>>v[i];
int prev=v[n-1]+10;
for(int i=n-1;i>=0;i--){
if(v[i]>prev){
cout<<i+1;
return;
}
prev=v[i];
}
cout<<0;
}
int main(){
int t;
cin>>t;
while(t--){
solve();
cout<<"\n";
}
return 0;
}
B: Hulk Smash
Epiphany 13.0 B — Hulk Smash
Observations
- The number of zeroes in the fully reconstructed sequence directly corresponds to the number of transformations.
- Each non-zero value $$$x$$$ in the sequence suggests that the $$$x$$$ entries immediately preceding this must be $$$x−1,x−2,…,0$$$. Fill in any missing values $$$(-1)$$$ with these corresponding values. The problem statement ensures the consistency of provided sequences.
- After filling some $$$(-1)$$$ as described in observation $$$2$$$, some $$$(-1)$$$ entries might remain. These can be filled in two ways:
- Replace $$$(-1)$$$ with $$$0$$$, creating a potential transformation.
- Replace $$$(-1)$$$ with $$$a_{i-1}+1$$$, continuing a previous streak.
Previous observation implies that a range of zeroes can be achieved:
- Maximum Zeroes: Fill all remaining $$$(-1)$$$ with $$$0$$$.
- Minimum Zeroes: Fill all remaining $$$(-1)$$$ with preceding values, to continue streaks (as described above).
Let $$$minzero$$$ and $$$maxzero$$$ represent the minimum and maximum achievable zero counts. To answer a query $$$x$$$, check if $$$minzero ≤ x ≤ maxzero$$$.
If true, output $$$YES$$$, indicating a feasible sequence with $$$x$$$ transformations. strategy: let $$$k = x - minzero$$$ then for the first $$$k-1$$$ missing values which are remaining after applying observation $$$2$$$, fill them with $$$0$$$ and for the remaining continue the preceding streak, hence number of zeroes become $$$x$$$.
If false, output $$$NO$$$, indicating no such sequence exists.
#include<bits/stdc++.h>
#define forn(l,n,i) for(int i=l;i<n;i++)
#define ll long long int
using namespace std;
void solve(){
int n,q;
cin>>n>>q;
vector<int> v(n);
forn(0,n,i) cin>>v[i];
int prev=-1;
v[0]=0;
for(int i=n-1;i>0;i--){
if(v[i]==-1){
if(prev==-1) continue;
else {
v[i]=prev;
prev--;
}
}
else{
prev=v[i]-1;
}
}
int ans=0,extra=0;
forn(0,n,i){
if(v[i]==-1)extra++;
else if(v[i]==0) ans++;
}
int left=ans,right=ans+extra;
forn(0,q,i){
int x;
cin>>x;
if(x>=left && x<=right) cout<<"YES\n";
else cout<<"NO\n";
}
}
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);
int t;
cin>>t;
while(t--){
solve();
cout<<"\n";
}
return 0;
}
C: Fight Between Friends
Epiphany 13.0 C — Fight Between Friends
Sort both the arrays in increasing order of the strengths.
Consider the strengths of an individual from Alice's team denoted by $$$x$$$, and the strengths of all individuals from Bob's team denoted by $$$b_1, b_2, ..., b_m$$$. If $$$b_k \le x$$$ and $$$b_{k+1} \gt x$$$, then the points gained by a person from Alice's team with strength $$$x$$$ will be $$$k$$$ and can be determined using the lower_bound($$$x$$$) function on the array $$$b$$$ (representing the strengths of Bob's team).
T.C: O((N + M) * (logN + logM))
Epiphany 13.0 C — Fight Between Friends
Sort both the arrays in increasing order of the strengths.
By iterating through each person from Alice's team, one person compares their strength with individuals from Bob's team. If the first person ($$$i=0$$$) from Alice's team can beat $$$j$$$ people, then in the next iteration ($$$i=1$$$, representing the next person from Alice's team), it assures that this person will beat $$$j$$$ people. In addition to this, the process continues to identify other individuals whom the person in the current iteration ($$$i=1$$$) can defeat to the persons from Bob's team.
T.C: O(N * logN + M * logM)
// Yagnik Dhameliya
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
#define all(a) a.begin(), a.end()
void solve()
{
int n, m;
cin >> n >> m;
vector<int> a(n), b(m);
for(int i = 0; i < n; i++)
{
cin >> a[i];
}
for(int j = 0; j < m; j++)
{
cin >> b[j];
}
sort(all(a));
sort(all(b));
function<int(vector<int>, vector<int>)> run = [&](vector<int> a, vector<int> b)
{
int ans = 0;
for(int i = 0; i < a.size(); i++)
{
auto it = lower_bound(all(b), a[i]);
if(it != b.begin())
{
if(it == b.end() || *it >= a[i]) it--;
ans = (ans + (it - b.begin() + 1)) % mod;
}
}
return ans;
};
cout << run(a, b) << " " << run(b, a) << endl;
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t = 1;
while(t--)
{
solve();
}
return 0;
}
// Yagnik Dhameliya
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
#define all(a) a.begin(), a.end()
void solve()
{
int n, m;
cin >> n >> m;
vector<int> a(n), b(m);
for(int i = 0; i < n; i++)
{
cin >> a[i];
}
for(int j = 0; j < m; j++)
{
cin >> b[j];
}
sort(all(a));
sort(all(b));
function<int(vector<int>, vector<int>)> run = [&](vector<int> a, vector<int> b)
{
int ans = 0;
int i = 0, j = 0;
while(i < a.size())
{
while(j < b.size() && a[i] > b[j]) { j++; }
ans = (ans + j) % mod;
i++;
}
return ans;
};
cout << run(a, b) << " " << run(b, a) << endl;
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t = 1;
while(t--)
{
solve();
}
return 0;
}
D: SOS Signal
Epiphany 13.0 D — SOS Signal
The given problem can be stated as an equation to find solution for linear equation
This equation is called a Diophantine equation. Let equation (1) be satisfied for some x and y then the time when the signal can be successfully read can be given as
Result 1: A solution to linear Diophantine equation $$$mx+ny=r$$$ exists only if $$$gcd(m,n) ∣ r$$$. If solution exists, let's say $$$(x_\circ,y_\circ)$$$ then there are infinite solutions, generalizing
Result 2: Using the Euclid Algorithm, a solution to the following equation can be obtained.
Rewriting our original equation we have,
Let $$$g=gcd(c,d)$$$ then if $$$g∤k$$$ then solution doesn't exist and we can print $$$-1$$$ as output.
If $$$g∣k$$$, then we need to find the solution for the equation $$$(2)$$$, such that both $$$(x, y)$$$ are the smallest positive pair (for the first time the ship reads signal successfully).
Let's say $$$(x_0,y_0)$$$ are solutions for the equation $$$(c/g)x+(d/g)y=1$$$ which can be obtained using Euclid's algorithm.
This implies that $$$(x′,y′)=(x_0\cdot(k/g),−y_0\cdot(k/g))$$$ is a solution for the equation $$$cx−dy=k$$$
The general solution can then be given by
In order to find the smallest positive pair of $$$(x,y)$$$ from the above general terms, we compute two pairs $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$ where $$$x_1$$$ is the smallest positive integer $$$x$$$ obtained by equating the general term for $$$x$$$ to $$$0$$$ and $$$y_2$$$ is the smallest positive integer $$$y$$$ obtained by equating the general term of $$$y$$$ to $$$0$$$. We then pick the pair such that both $$$x,y \gt =0 $$$ and are the smallest.
#include<bits/stdc++.h>
#define forn(l,n,i) for(int i=l;i<n;i++)
#define ll long long int
using namespace std;
ll inf = 1e18;
vector<ll> extended_euclid(ll a,ll b){
ll x=1,y=0,x1=0,y1=1;
while(b){
ll temp=x,temp1=y;
x=x1;
y=y1;
x1 = temp - (a/b)*x1;
y1 = temp1 - (a/b)*y1;
a%=b;
swap(a,b);
}
vector<ll> res(2);
res[0]=x;
res[1]=y;
return res;
}
void solve(){
ll a,b,c,d;
cin>>a>>b>>c>>d;
// cx - dy = b+d - (c+a) ; x,y>=0
ll rhs = b+d -c -a;
ll g = __gcd(c,d);
if(rhs%g!=0){
cout<<-1;
return;
}
ll mult = rhs/g;
vector<ll> res = extended_euclid(c/g,d/g);
ll x=res[0]*mult;
ll y = res[1]*(-mult); // d<0
// gen sol = (x +- t*d/g, y +- t*c/g) => line with positive slope
ll ca = d/g;
ll da = c/g;
// making x>=0
ll x1 = ((x%ca) + ca)%ca;
ll y1 = (x1*c-rhs)/d;
// making y>=0
ll y2 = ((y%da) + da)%da;
ll x2 = (rhs + y2*d)/c;
ll time=inf;
if(x1>=0 && y1>=0)time=min(time,c*x1+c+a);
if(x2>=0 && y2>=0) time=min(time,c*x2+c+a);
cout<<time;
}
int main(){
int t;
cin>>t;
while(t--){
solve();
cout<<"\n";
}
return 0;
}
E1: New Year Games-1
There are many hints in problem statement.
Groups , Groups are merged
DSU ?
Try to use two different parent vectors in dsu one for path comparison and another for accessing the main parent.
Epiphany 13.0 E1 — New Year Games-1
We have to implement as given in the problem statement: first, for any two groups that face off, we update their win vector, and then we create the next group by merging both groups and updating their score and size from the last two groups.
Only n-1 games play at maximum because if both players are from the same group, then the game is abandoned. As for each time any two groups merge, and in starting, we have n groups, so a maximum of n-1 games are played; all others are abandoned.
par[next_ind] = next_ind;
par[a] = next_ind;
par[b] = next_ind;
// Update main parent pointers
par_main[next_ind] = next_ind;
par_main[a] = next_ind;
par_main[b] = next_ind;
// Update score and size information
score[next_ind] = score[a] + score[b];
size[next_ind] = size[a] + size[b];
// Update winner count based on average scores
if (score[a] / size[a] > score[b] / size[b]) win[a]++;
if (score[a] / size[a] < score[b] / size[b]) win[b]++;
// Move to the next index for the new set
next_ind++;
After playing all games we can find the total win of each person using the main parent vector in total O(n) time
As we are doing path compression using one vector so time complexity of DSU is nearly O(1).
TC = O(n+m)
// Rutvik Ranpariya
#include <bits/stdc++.h>
using namespace std;
int main() {
// Fast I/O optimization
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
cin >> n >> m;
// Data structures to manage disjoint sets
vector<int> score(2 * n + 10);
vector<int> size(2 * n + 10);
vector<int> par(2 * n + 10);
vector<int> par_main(2 * n + 10);
vector<int> win(2 * n + 10, 0);
int next_ind = n + 1;
// Input scores for each player
for (int i = 1; i <= n; i++) {
cin >> score[i];
size[i] = 1;
par[i] = i;
par_main[i] = i;
}
// Function to find the representative/base of a disjoint set
function<int(int)> base = [&](int val) {
if (par[val] == val) return val;
return par[val] = base(par[val]);
};
// Function to join two disjoint sets
function<void(int,int)> join = [&](int a, int b) {
a = base(a);
b = base(b);
if (a == b) return;
// Create a new set and update parent pointers
par[next_ind] = next_ind;
par[a] = next_ind;
par[b] = next_ind;
// Update main parent pointers
par_main[next_ind] = next_ind;
par_main[a] = next_ind;
par_main[b] = next_ind;
// Update score and size information
score[next_ind] = score[a] + score[b];
size[next_ind] = size[a] + size[b];
// Update winner count based on average scores
if (score[a] / size[a] > score[b] / size[b]) win[a]++;
if (score[a] / size[a] < score[b] / size[b]) win[b]++;
// Move to the next index for the new set
next_ind++;
};
// Process merge operations
int a, b;
while (m--) {
cin >> a >> b;
join(a, b);
}
// Propagate winner information to the main parent
for (int i = next_ind - 1; i; i--)
if (par_main[i] != i) win[i] += win[par_main[i]];
// Output the number of wins for each player
for (int i = 1; i <= n; i++) cout << win[i] << " ";
return 0;
}
Epiphany 13.0 E1 — New Year Games-1
Define Basic DSU Structure. In DSU keep arrays also for Score and Length which denotes the score and length of a group where $$$x$$$ is the main parent of the group (score[ $$$x$$$ ], length[ $$$x$$$ ]).
If people $$$x$$$ and $$$y$$$ are playing a game then find the probability of $$$x$$$ and $$$y$$$. Say, avg($$$x$$$) and avg($$$y$$$).
Things to do in DSU:
cnt[ $$$x$$$ ]: Stores the count of $$$winning$$$ of the node $$$x$$$.
Group: Say, Initially, $$$x$$$ & $$$y$$$ playing a game and say avg($$$x$$$) > avg($$$y$$$). So, we make an edge from $$$x$$$ -> $$$y$$$ by storing the id[ $$$x$$$ ] and incrementing cnt[ $$$x$$$ ] by $$$1$$$. (where $$$x$$$ = node which has a higher probability.)
id[ $$$x$$$ ]: id[ $$$x$$$ ] used to give the number to each child of $$$x$$$ according to their joining.
This means, If $$$y$$$ joins $$$x$$$ then id[ $$$x$$$ ] = 1, and the edge will be added like this => adj[ $$$x$$$ ].push_back({$$$y, id[x]$$$}) ~ adj[ $$$x$$$ ].push_back({$$$y, 1$$$})
after that, If $$$z$$$ joins $$$x$$$, then id[ $$$x$$$ ] = 2 and edge will be added like this => adj[ $$$x$$$ ].push_back({$$$z, id[x]$$$}) ~ adj[ $$$x$$$ ].push_back({$$$z, 2$$$})
In case, if avg($$$x$$$) = avg($$$y$$$) then do not increment id[ $$$x$$$ ] as we are not incrementing cnt[ $$$x$$$ ].
This id will be used to count the $$$winning$$$ of a $$$node$$$ after it joins the group(where $$$x$$$ = the main parent).
Say, after all the queries id[ $$$x$$$ ] = $$$5$$$, and when $$$z$$$ joined at that time id[ $$$x$$$ ] = $$$2$$$.
It means in total the group of $$$x$$$ wins $$$5$$$ times and ultimately $$$z$$$ wins $$$3$$$ times($$$5$$$ — $$$2$$$) after joining the group.
Things to do in DFS:
Going to every node starting with the nodes who have in-degree = $$$0$$$.
Now at every child of a node, in the child do this: cnt[ $$$child$$$ ] += cnt[ $$$node$$$ ] — $$$id$$$.
Because as explained above if $$$node$$$ has been won $$$5$$$ times and when $$$child$$$ joined at that time $$$id$$$ = $$$2$$$,
then this should be done: cnt[ $$$child$$$ ] += $$$3$$$ => ans[ $$$child$$$ ] += ($$$5$$$ — $$$2$$$) => cnt[ $$$child$$$ ] += (cnt[ $$$node$$$ ] — $$$id$$$).
// Yagnik Dhameliya
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
const int M = 1e9 + 7;
const int MX = 1e6 + 5;
vector<array<int, 2>> adj[MX];
vector<int> deg, cnt, id;
void init(int n)
{
deg.resize(n);
cnt.resize(n);
id.resize(n);
}
class DSU{
public:
vector<int> par, score, len;
int n;
DSU(int sz, vector<int> &s)
{
n = sz;
par.resize(n);
score.resize(n);
len.resize(n);
for(int i = 0; i < n; i++)
{
par[i] = i;
len[par[i]] = 1;
score[i] = s[i];
}
}
int find(int node)
{
if(node == par[node]) return node;
return par[node] = find(par[node]);
}
int avg(int u)
{
return floor(score[u] / len[u]);
}
bool merge(int u, int v)
{
u = find(u);
v = find(v);
if(u == v) return u;
if(avg(u) == avg(v))
{
adj[u].push_back({v, id[u]});
}
else
{
if(avg(u) < avg(v)) swap(u, v);
cnt[u]++;
adj[u].push_back({v, ++id[u]});
}
par[v] = u;
len[u] += len[v];
score[u] += score[v];
deg[v]++;
return u;
}
};
void solve()
{
int n, m;
cin >> n >> m;
vector<int> s(n);
for(int i = 0; i < n; i++)
{
cin >> s[i];
}
init(n);
DSU d(n, s);
for(int i = 1; i <= m; i++)
{
int x, y;
cin >> x >> y;
x--, y--;
d.merge(x, y);
}
vector<int> v;
for(int i = 0; i < n; i++)
{
if(!deg[i]) v.push_back(i);
}
function<void(int)> dfs = [&](int node)
{
for(auto [child, id] : adj[node])
{
cnt[child] += cnt[node] - id;
dfs(child);
}
};
for(auto it : v) dfs(it);
for(auto it : cnt) cout << it << " ";
cout << endl;
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t = 1;
// cin >> t;
while(t--)
{
solve();
}
return 0;
}
E2: New Year Games-2
Epiphany 13.0 E2 — New Year Games-2
There wasn't much difference in E1 and E2 in this problem we have to keep count of probability of win insert of win count.
// Calculating win probabilities and taking modulo
int p1 = (score[a] * mod_inverse(size[a], mod)) % mod;
int p2 = (score[b] * mod_inverse(size[b], mod)) % mod;
int inv = mod_inverse(p1 + p2, mod);
win_prob[a] = (p1 * inv) % mod;
win_prob[b] = (p2 * inv) % mod;
TC = O(n+m)
// Rutvik Ranpariya
// Including necessary header files
#include <bits/stdc++.h>
using namespace std;
// Defining macro for shorthand notation of long long
#define int long long
// Setting a global constant for modulo operation
int mod = 1e9 + 7;
// Function to calculate extended Euclidean GCD
int extended_euclidean_gcd(int a, int b, int *x, int *y) {
if (b == 0) {
*x = 1;
*y = 0;
return a;
}
int x1, y1;
int d = extended_euclidean_gcd(b, a % b, &x1, &y1);
*x = y1;
*y = x1 - y1 * (a / b);
return d;
}
// Function to calculate modular inverse using extended Euclidean algorithm
int mod_inverse(int a, int m) {
int x, y, d;
d = extended_euclidean_gcd(a, m, &x, &y);
if (d != 1)
return -1;
return (x % m + m) % m;
}
int32_t main() {
// Fast I/O optimization
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// Input variables for the number of players (n) and the number of pairwise connections (m)
int n, m;
cin >> n >> m;
// Arrays to store scores, sizes, and parent information for each player
vector<int> score(2 * n + 10);
vector<int> size(2 * n + 10);
vector<int> par(2 * n + 10);
vector<int> par_main(2 * n + 10);
vector<int> win_prob(2 * n + 10, 0);
vector<int> count_of_game(2 * n + 10, 0);
// Variable to keep track of the next available index for a new player
int next_ind = n + 1;
// Inputting initial scores and initializing player attributes
for (int i = 1; i <= n; i++) {
cin >> score[i];
size[i] = 1;
par[i] = i;
par_main[i] = i;
}
// Lambda function to find the base parent of a player
function<int(int)> base = [&](int val) {
if (par[val] == val)
return val;
return par[val] = base(par[val]);
};
// Lambda function to join two players and update the data structures
function<void(int, int)> join = [&](int a, int b) {
a = base(a);
b = base(b);
if (a == b)
return;
// Creating a new player and updating parent information
par[next_ind] = next_ind;
par_main[next_ind] = next_ind;
par[a] = next_ind;
par[b] = next_ind;
par_main[a] = next_ind;
par_main[b] = next_ind;
// Updating scores and sizes
score[next_ind] = score[a] + score[b];
size[next_ind] = size[a] + size[b];
// Taking modulo of the score to avoid overflow
score[next_ind] %= mod;
// Calculating win probabilities and taking modulo
int p1 = (score[a] * mod_inverse(size[a], mod)) % mod;
int p2 = (score[b] * mod_inverse(size[b], mod)) % mod;
int inv = mod_inverse(p1 + p2, mod);
win_prob[a] = (p1 * inv) % mod;
win_prob[b] = (p2 * inv) % mod;
// Incrementing the next available index
next_ind++;
};
// Inputting pairwise connections and joining players accordingly
int a, b;
while (m--) {
cin >> a >> b;
join(a, b);
}
// Array to store the final answer for each player
vector<int> ans(n + 1, -1);
// Loop to update win probabilities and count of games played for each player
for (int i = next_ind - 1; i; i--) {
if (par_main[i] != i) {
win_prob[i] += win_prob[par_main[i]];
count_of_game[i] += count_of_game[par_main[i]] + 1;
// Taking modulo of the win probability
win_prob[i] %= mod;
// Storing the final answer for each player if it is an original player (not created during merging)
if (i <= n)
ans[i] = (win_prob[i] * mod_inverse(count_of_game[i], mod)) % mod;
}
}
// Outputting the final answer for each original player
for (int i = 1; i <= n; i++)
cout << ans[i] << " ";
return 0;
}
Epiphany 13.0 E2 — New Year Games-2
Define Basic DSU Structure. In DSU keep arrays also for Score and Length which denotes the score and length of a group where $$$x$$$ is the main parent of the group (score[ $$$x$$$ ], length[ $$$x$$$ ]).
If people $$$x$$$ and $$$y$$$ are playing a game then find the probability of $$$x$$$ and $$$y$$$. Say, p($$$x$$$) and p($$$y$$$).
My meaning of the term $$$winning$$$ is: that node have a higher probability of winning.
My meaning of the term $$$losing$$$ is: that node have a lower probability of winning.
Things to do in DSU:
cnt[ $$$x$$$ ]: Stores the total number of games played by $$$x$$$.
Group: Say, Initially, $$$x$$$ & $$$y$$$ playing a game and say p($$$x$$$) > p($$$y$$$). So, we make an edge from $$$x$$$ -> $$$y$$$ by storing the id[ $$$x$$$ ] and incrementing cnt[ $$$x$$$ ] by $$$1$$$. (where $$$x$$$ = node which has a higher probability.)
ans[ $$$x$$$ ]: Stores the sum of the probabilities when the node $$$x$$$ was $$$winning$$$.
Similar concept as the $$$id$$$ that if in the group of $$$x$$$ if $$$y$$$ joins then we need to remove current ans[ $$$x$$$ ] from the final ans[ $$$x$$$ ] as only the sum of probability after joining of $$$y$$$ added to the ans [ $$$y$$$ ]. To do this we add current ans[ $$$x$$$ ] to the adjacency list when we make the edge and we do this after understanding the $$$id$$$.
val[ $$$x$$$ ]: Stores the sum of the probabilities when the node $$$x$$$ was $$$losing$$$.
The val[ $$$x$$$ ] should be directly added to all the children and grandchildren till the leaf node as if any node $ loses any time then that node never represents the group some other node will come into the picture. So, no need to store current value and stuff.
id[ $$$x$$$ ]: id[ $$$x$$$ ] used to give the number to each child of $$$x$$$ according to their joining.
This means, If $$$y$$$ joins $$$x$$$ then id[ $$$x$$$ ] = 1, and the edge will be added like this => adj[ $$$x$$$ ].push_back({$$$y, id[x], ans[x]$$$}) ~ adj[ $$$x$$$ ].push_back({$$$y, 1, ans[x]$$$})
after that, If $$$z$$$ joins $$$x$$$, then id[ $$$x$$$ ] = 2 and edge will be added like this => adj[ $$$x$$$ ].push_back({$$$z, id[x], ans[x]$$$}) ~ adj[ $$$x$$$ ].push_back({$$$z, 2, ans[x]$$$})
This id will be used to count the number of games played by a $$$node$$$ after it joins the group(where $$$x$$$ = the main parent).
Say, after all the queries id[ $$$x$$$ ] = $$$5$$$, and when $$$z$$$ joined at that time id[ $$$x$$$ ] = $$$2$$$.
It means in total the group of $$$x$$$ played $$$5$$$ games and ultimately $$$z$$$ played $$$4$$$ times($$$5$$$ — $$$2$$$) + $$$1$$$ after playing the match and joining the group.
Things to do in DFS:
Going to every node starting with the nodes who have in-degree = $$$0$$$.
Now at every child of a node, in the child do this: cnt[ $$$child$$$ ] += cnt[ $$$node$$$ ] — $$$id$$$ + $$$1$$$.
Because as explained above if $$$node$$$ has been won $$$5$$$ times and when $$$child$$$ joined at that time $$$id$$$ = $$$2$$$,
then this should be done: cnt[ $$$child$$$ ] += $$$3$$$ => cnt[ $$$child$$$ ] += ($$$5$$$ — $$$2$$$) => cnt[ $$$child$$$ ] += (cnt[ $$$node$$$ ] — $$$id$$$) + $$$1$$$.
Also,at every child of a node, in the child also do this: ans[ $$$child$$$ ] += ans[ $$$node$$$ ] — ans_till_child. (ans_till_child = Stored answer at the time of edge was created.)
Also, at every child of a node, in the child also do this: ans[ $$$child$$$ ] += val[ $$$child$$$ ]. (Adding the $$$losing$$$ probability.)
// Yagnik Dhameliya
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
const int M = 1e9 + 7;
int gcdExtended(int a, int b, int* x, int* y)
{
if (a == 0)
{
*x = 0, *y = 1;
return b;
}
int x1, y1;
int gcd = gcdExtended(b % a, a, &x1, &y1);
*x = y1 - (b / a) * x1;
*y = x1;
return gcd;
}
int inv(int a)
{
int x, y;
int g = gcdExtended(a, M, &x, &y);
return (x % M + M) % M;
}
const int MX = 1e6 + 5;
vector<array<int, 3>> adj[MX];
vector<int> deg, ans, val, id, cnt;
void init(int n)
{
deg.resize(n);
ans.resize(n);
val.resize(n);
id.resize(n);
cnt.resize(n);
}
void add_self(int &a, int b)
{
a += b;
if(a >= M) a -= M;
}
int add(int a, int b)
{
return (a + b) % M;
}
int sub(int a, int b)
{
return (a - b + M) % M;
}
int mul(int a, int b)
{
return (a * b) % M;
}
class DSU{
public:
vector<int> par, score, len;
int n;
DSU(int sz, vector<int> &s)
{
n = sz;
par.resize(n);
score.resize(n);
len.resize(n);
for(int i = 0; i < n; i++)
{
par[i] = i;
len[i] = 1;
score[i] = s[i];
}
}
int find(int node)
{
if(node == par[node]) return node;
return par[node] = find(par[node]);
}
int team_score(int u)
{
return mul(score[u], inv(len[u]));
}
int prob(int u, int v)
{
int s_u = team_score(u);
int s_v = team_score(v);
return mul(s_u, inv(add(s_u, s_v)));
}
bool merge(int u, int v)
{
u = find(u);
v = find(v);
if(u == v) return u;
int u_v = prob(u, v);
int v_u = prob(v, u);
if(u_v == v_u)
{
add_self(ans[u], u_v);
add_self(ans[v], u_v);
adj[u].push_back({v, ans[u], ++id[u]});
}
else
{
if(u_v < v_u) swap(u, v), swap(u_v, v_u);
add_self(ans[u], u_v);
add_self(val[v], v_u);
adj[u].push_back({v, ans[u], ++id[u]});
}
par[v] = u;
add_self(len[u], len[v]);
add_self(score[u], score[v]);
deg[v]++;
cnt[u]++;
return u;
}
};
void solve()
{
int n, m;
cin >> n >> m;
vector<int> s(n);
for(int i = 0; i < n; i++)
{
cin >> s[i];
}
init(n);
DSU d(n, s);
for(int i = 1; i <= m; i++)
{
int x, y;
cin >> x >> y;
x--, y--;
d.merge(x, y);
}
vector<int> v;
for(int i = 0; i < n; i++)
{
if(!deg[i]) v.push_back(i);
}
function<void(int)> dfs = [&](int node)
{
for(auto [child, ans_till_child, id] : adj[node])
{
add_self(ans[child], sub(ans[node], ans_till_child));
add_self(ans[child], val[child]);
add_self(cnt[child], sub(cnt[node], id) + 1);
dfs(child);
}
};
for(auto it : v) dfs(it);
for(int i = 0; i < n; i++)
{
if(!cnt[i]) cout << -1 << " ";
else cout << mul(ans[i], inv(cnt[i])) << " ";
}
cout << endl;
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t = 1;
// cin >> t;
while(t--)
{
solve();
}
return 0;
}
F: Money Distribution
Divide the given tree into components using Heavy-Light Decomposition
Apply lazy segment tree on each component or chain to store and get $$$(a, b)$$$ for the ranges.
Notice the condition $$$q*k \le 5\cdot10^7$$$.
For each node in the path from $$$u$$$ to $$$v$$$ run a query on the segment tree for each query of Type-2 for $$$logN$$$ time to get the value of $$$(a, b)$$$ of the range $$$[x, x]$$$ Where $$$x$$$ is the node in the path from $$$u$$$ to $$$v$$$. Now, the path from $$$u$$$ to $$$v$$$ takes time-$$$K$$$ and each node takes $$$logN$$$ for $$$Q$$$ times.
Epiphany 13.0 F — Money Distribution
Define the basic Heavy-Light Decomposition structure . Where each node will get Id's according to the heavy and light edges by doing a DFS traversal.
For Type-1 Query: If $$$u$$$ and $$$v$$$ are in the same chain then add the value pair $$$(a, b)$$$ to all the nodes in the chain of $$$u$$$ and $$$v$$$ using the lazy segment tree of that chain.
Otherwise, according to depth, choose a node from $$$u$$$ and $$$v$$$ such that the depth of the head of the node is higher and add the value pair $$$(a, b)$$$ to all the nodes of the chain in which the chosen node lies(using the lazy segment tree of that chain). Do this till both the nodes come to the same chain.
For Type-2 Query: If $$$u$$$ and $$$v$$$ are in the same chain then run a loop from Id[head[u]] to Id[u] (Assume that depth[head[u]] > depth[head[v]]) and run a query on the segment tree of that chain till the leaf node where the range is $$$[x, x]$$$ only. Where $$$x$$$ is the Id of the node in the path from $$$u$$$ to $$$v$$$.
Keep two answer variables initially initialized with $$$0$$$ and each will store the answer of either the left or the right side of the $$$LCA(u, v)$$$.
Now, take value pair $$$(a, b)$$$ from the segment tree node for the range $$$[x, x]$$$ and add $$$st[node].a * Id[x] + st[node].b$$$ to the appropriate answer variable the left or the right.
If $$$u$$$ and $$$v$$$ are not in the same chain then choose a node such that the head of the node has the higher depth and apply the above operation of query on the chain of the current node.
At last, return the $$$XOR$$$ of both the answer variables.
T.C: $$$O(Q * (K + logn) * logn)$$$
// Yagnik Dhameliya
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
#define all(a) a.begin(), a.end()
struct value{
int a, b;
};
class HLD{
public:
vector<int> head, heavy, depth, parent, id;
int id_num;
vector<value> st, lazy;
int n;
map<pair<int, int>, int> map_node;
vector<int> map_val;
HLD(int sz, vector<int> *adj)
{
n = sz;
head.resize(n + 1);
heavy.resize(n + 1, -1);
depth.resize(n + 1);
parent.resize(n + 1);
id.resize(n + 1);
map_val.resize(n);
id_num = 0;
dfs_sz(0, adj);
dfs_hld(0, 0, adj);
map_vals();
st.resize(4 * n);
lazy.resize(4 * n);
build(0, 0, n - 1);
}
value move(value x, value y)
{
return {x.a + y.a, x.b + y.b};
}
void build(int node, int start, int end)
{
if(start == end)
{
map_node[{start, end}] = node;
return;
}
int mid = (start + end) >> 1;
build(2 * node + 1, start, mid);
build(2 * node + 2, mid + 1, end);
}
void push(int x, int y, int node, int start, int end)
{
st[node].a += (end - start + 1) * x;
st[node].b += (end - start + 1) * y;
if(start != end)
{
lazy[2 * node + 1].a += x;
lazy[2 * node + 1].b += y;
lazy[2 * node + 2].a += x;
lazy[2 * node + 2].b += y;
}
lazy[node].a = lazy[node].b = 0;
}
void update(int node, int start, int end, int l, int r, value p)
{
if(lazy[node].a != 0 || lazy[node].b != 0)
{
push(lazy[node].a, lazy[node].b, node, start, end);
}
if(start > r || end < l) return;
if(l <= start && end <= r)
{
push(p.a, p.b, node, start, end);
return;
}
int mid = (start + end) >> 1;
update(2 * node + 1, start, mid, l, r, p);
update(2 * node + 2, mid + 1, end, l, r, p);
st[node] = move(st[2 * node + 1], st[2 * node + 2]);
}
value query(int node, int start, int end, int l, int r)
{
if(lazy[node].a != 0 || lazy[node].b != 0)
{
push(lazy[node].a, lazy[node].b, node, start, end);
}
if(start > r || end < l) return {};
if(start == end) return st[node];
int mid = (start + end) >> 1;
value left = query(2 * node + 1, start, mid, l, r);
value right = query(2 * node + 2, mid + 1, end, l, r);
return move(left, right);
}
int dfs_sz(int node, vector<int> *adj)
{
int sz = 1, mx = 0;
for(auto it : adj[node])
{
if(it == parent[node]) continue;
parent[it] = node, depth[it] = depth[node] + 1;
int child_sz = dfs_sz(it, adj);
sz += child_sz;
if(child_sz > mx)
{
mx = child_sz;
heavy[node] = it;
}
}
return sz;
}
void dfs_hld(int node, int top, vector<int> *adj)
{
head[node] = top;
id[node] = id_num++;
if(heavy[node] != -1) dfs_hld(heavy[node], top, adj);
for(auto it : adj[node])
{
if(it == parent[node] || it == heavy[node]) continue;
dfs_hld(it, it, adj);
}
}
void map_vals()
{
for(int i = 0; i < n; i++) map_val[id[i]] = i + 1;
}
void update_path(int u, int v, value p)
{
while(head[u] != head[v])
{
if(depth[head[u]] > depth[head[v]]) swap(u, v);
update(0, 0, n - 1, id[head[v]], id[v], p);
v = parent[head[v]];
}
if(depth[u] > depth[v]) swap(u, v);
update(0, 0, n - 1, id[u], id[v], p);
}
int query_path(int u, int v)
{
int ansv = 0, ansu = 0;
while(head[u] != head[v])
{
if(depth[head[u]] > depth[head[v]]) swap(u, v), swap(ansv, ansu);
int x = id[head[v]], y = id[v];
for(int i = x; i <= y; i++)
{
query(0, 0, n - 1, i, i);
int node = map_node[{i, i}];
int val = map_val[i];
ansv += st[node].a * val + st[node].b;
}
v = parent[head[v]];
}
if(depth[u] > depth[v]) swap(u, v), swap(ansv, ansu);
int x = id[u], y = id[v];
for(int i = x; i <= y; i++)
{
query(0, 0, n - 1, i, i);
int node = map_node[{i, i}];
int val = map_val[i];
ansv += st[node].a * val + st[node].b;
if(i == x) ansu += st[node].a * val + st[node].b;
}
return ansv ^ ansu;
}
};
void solve()
{
int n, q;
cin >> n >> q;
vector<int> adj[n];
for(int i = 1; i <= n - 1; i++)
{
int u, v;
cin >> u >> v;
u--, v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
HLD hld(n, adj);
while(q--)
{
int type;
cin >> type;
if(type == 1)
{
int u, v, a, b;
cin >> u >> v >> a >> b;
u--, v--;
hld.update_path(u, v, {a, b});
}
else
{
int u, v;
cin >> u >> v;
u--, v--;
cout << hld.query_path(u, v) << endl;
}
}
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t = 1;
while(t--)
{
solve();
}
return 0;
}
T.C: $$$O(Q * (K + logn) * logn)$$$
Idea: shiven
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
struct value{
int a, b;
};
struct node{
int val, sz, sum, a, b;
};
class HLD{
public:
vector<int> head, heavy, depth, parent, id, map_val;
vector<node> st;
int id_num;
int n;
HLD(int sz, vector<int> adj[])
{
n = sz;
head.resize(n + 1);
heavy.resize(n + 1, -1);
depth.resize(n + 1);
parent.resize(n + 1);
id.resize(n + 1);
map_val.resize(n + 1);
id_num = 0;
dfs_sz(0, adj);
dfs_hld(0, 0, adj);
map_vals();
st.resize(4 * n);
}
void print()
{
for(int i = 0; i < n; i++)
{
cout << i + 1 << " " << map_val[i] << endl; // id, node.
}
}
void map_vals()
{
for(int i = 0; i < n; i++) map_val[id[i]] = i + 1;
}
int dfs_sz(int node, vector<int> adj[])
{
int sz = 1, mx = 0;
for(auto it : adj[node])
{
if(it == parent[node]) continue;
parent[it] = node, depth[it] = depth[node] + 1;
int child_sz = dfs_sz(it, adj);
sz += child_sz;
if(child_sz > mx)
{
mx = child_sz;
heavy[node] = it;
}
}
return sz;
}
void dfs_hld(int node, int top, vector<int> adj[])
{
head[node] = top;
id[node] = id_num++;
if(heavy[node] != -1) dfs_hld(heavy[node], top, adj);
for(auto it : adj[node])
{
if(it == parent[node] || it == heavy[node]) continue;
dfs_hld(it, it, adj);
}
}
void push(int node)
{
st[2 * node + 1].a += st[node].a;
st[2 * node + 1].b += st[node].b;
st[2 * node + 1].val += st[node].a * st[2 * node + 1].sum + st[node].b * st[2 * node + 1].sz;
st[2 * node + 2].a += st[node].a;
st[2 * node + 2].b += st[node].b;
st[2 * node + 2].val += st[node].a * st[2 * node + 2].sum + st[node].b * st[2 * node + 2].sz;
st[node].a = st[node].b = 0;
}
void set(int node, int start, int end, int i, int val)
{
if(start > i || end < i) return;
if(start == end)
{
st[node].sum = val;
st[node].sz = 1;
return;
}
int mid = (start + end) >> 1;
if(st[node].a || st[node].b) push(node);
set(2 * node + 1, start, mid, i, val);
set(2 * node + 2, mid + 1, end, i, val);
st[node].sum = st[2 * node + 1].sum + st[2 * node + 2].sum;
st[node].sz = st[2 * node + 1].sz + st[2 * node + 2].sz;
st[node].val = st[2 * node + 1].val + st[2 * node + 2].val;
}
void update(int node, int start, int end, int l, int r, value p)
{
if(start > r || end < l) return;
if(l <= start && end <= r)
{
st[node].val += p.a * st[node].sum + p.b * st[node].sz;
st[node].a += p.a;
st[node].b += p.b;
return;
}
int mid = (start + end) >> 1;
if(st[node].a || st[node].b) push(node);
update(2 * node + 1, start, mid, l, r, p);
update(2 * node + 2, mid + 1, end, l, r, p);
st[node].val = st[2 * node + 1].val + st[2 * node + 2].val;
}
int query(int node, int start, int end, int l, int r)
{
if(start > r || end < l) return 0ll;
if(l <= start && end <= r) return st[node].val;
int mid = (start + end) >> 1;
if(st[node].a || st[node].b) push(node);
int left = query(2 * node + 1, start, mid, l, r);
int right = query(2 * node + 2, mid + 1, end, l, r);
return left + right;
}
void update_path(int u, int v, value p)
{
while(head[u] != head[v])
{
if(depth[head[u]] > depth[head[v]]) swap(u, v);
update(0, 0, n - 1, id[head[v]], id[v], p);
v = parent[head[v]];
}
if(depth[u] > depth[v]) swap(u, v);
update(0, 0, n - 1, id[u], id[v], p);
}
int query_path(int u, int v)
{
int ans = 0;
while(head[u] != head[v])
{
if(depth[head[u]] > depth[head[v]]) swap(u, v);
ans += query(0, 0, n - 1, id[head[v]], id[v]);
v = parent[head[v]];
}
if(depth[u] > depth[v]) swap(u, v);
return ans += query(0, 0, n - 1, id[u], id[v]);
}
};
class binlift{
public:
int n, l, timer;
vector<int> tin, tout;
vector<vector<int>> dp;
binlift(int sz, int root, vector<int> adj[])
{
n = sz;
l = ceil(log2(n));
timer = 0;
tin.resize(n + 1);
tout.resize(n + 1);
dp.resize(n + 1, vector<int> (l + 1));
dfs(root, root, adj);
}
void dfs(int node, int par, vector<int> adj[])
{
tin[node] = ++timer;
dp[node][0] = par;
for(int j = 1; j <= l; j++) dp[node][j] = dp[dp[node][j - 1]][j - 1];
for(auto it : adj[node])
{
if(it == par) continue;
dfs(it, node, adj);
}
tout[node] = ++timer;
}
bool is_ancestor(int u, int v)
{
return (tin[u] <= tin[v] && tout[u] >= tout[v]);
}
int lca(int u, int v)
{
if(is_ancestor(u, v)) return u;
if(is_ancestor(v, u)) return v;
for(int j = l; j >= 0; j--)
{
if(is_ancestor(dp[u][j], v)) continue;
u = dp[u][j];
}
return dp[u][0];
}
};
void solve()
{
int n, q;
cin >> n >> q;
vector<int> adj[n];
for(int i = 1; i <= n - 1; i++)
{
int u, v;
cin >> u >> v;
u--, v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
HLD hld(n, adj);
for(int i = 0; i < n; i++) hld.set(0, 0, n - 1, hld.id[i], i + 1);
binlift bin(n, 0, adj);
while(q--)
{
int type;
cin >> type;
if(type == 1)
{
int u, v, a, b;
cin >> u >> v >> a >> b;
u--, v--;
hld.update_path(u, v, {a, b});
}
else
{
int u, v;
cin >> u >> v;
u--, v--;
int lca = bin.lca(u, v);
int a = hld.query_path(u, lca);
int b = hld.query_path(v, lca);
cout << (a ^ b) << endl;
}
}
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t = 1;
// cin >> t;
while(t--)
{
solve();
}
return 0;
}
T.C: $$$O(Q * logn * logn)$$$
Thanks for the fast editorial!! Nice Contest although wated 6 submissions on C because of not taking fast i/o.
If you are using HLD in problem F then it is possible to solve it in $$$O(q \log^2n)$$$ time. Construct HLD and segtree on top of tree. For each node, a range query can be done with range addition on a segtree(store $$$ax + b$$$ for each node and apply range addition appropriately). Path queries can be answered by walking on the segtree. Complexity for both is $$$O(log^2n)$$$.
I was thinking the same but didn't get much clarity on whether this would work. If you have a solution then you can share that. It will be useful for others to understand the approach.
Consider a segtree with following operations —
1) Range add $$$(a,b)$$$
2) Find range sum of $$$ax + b$$$
Once you make this segtree just apply it on the tree. HLD will have additional $$$\log n$$$ factor making each operation $$$\log^2 n$$$. A nice implementation of HLD is here — https://mirror.codeforces.com/blog/entry/81317
Alternatively you can flatten the tree and create fenwick trees of size $$$2*n$$$ to store sum of $$$a$$$ and $$$b$$$ from root to current node. Each query of type 1 can be broken into queries of $$$(a,b)$$$ from root to node and $$$(-a,-b)$$$ from root to LCA. For query of type 2, just iterate over all nodes from node to LCA. Value of current node is $$$sum_a(Enter[node],Exit[node]) \cdot x + sum_b(Enter[node],Exit[node])$$$. Unlike last method, this needs sum of path sums over all queries to be small.
Nicely explained. But in this approach also the query of type 2 running for all the nodes from node to LCA so that K factor will be still present here.
Yeah the alternative method will walk one by one. But if you build a HLD then you can break any path on the tree into $$$O(\log n)$$$ heavy chains and $$$O(\log n)$$$ light edges.
Okay, so we will add (a, b) in segtree with seg[node].sum and seg[node].size and for each a and b it can be done in O(logn). Is this the way you are talking about? I'll try it.
i solved e1 and e2 using small to large merging But I will look for dsu also
in problem d, i find (x,y) in d but dont know how it works if just making x>=0 or y>=0 gives us optimal answer
Any proof Yagnik_Dhameliya shadow9236
Tintin will keep sending signal on time = a+c,a+2c, a+3c, ... a+c*x and the ship will read for the position signal on time=b+d,b+2*d,b+3*d,... ,b+yd. So keeping the smallest positive x,y>=1 satisfying cx+a=dy+b will give us the smallest time.
i was thinking like, is it always exist that at least one of the pair in which both are positive?
i was thinking like one is incrementaed by a fac and other is decremented by a factor Is it possible to have some answer in other pairs also?
Yes you are correct, for equation ax + by = c we have the general equation x=x∘ ± t⋅(n/gcd(m,n))and y=y∘ ∓ t⋅(m/gcd(m,n)),t∈Z where when one increases then the other decreases. But for problem D equation is cx — dy = k, in this case general solution is
x=x∘ ± t⋅(n/gcd(m,n))and
y=y∘ ± t⋅(m/gcd(m,n)),t∈Z
so both x and y increases or both decreases, so we can guarantee there will be a pair with both of them positive.
Ohh got it Thanks
Alternate solution for D,
WLOG, assume that $$$a+c \lt b+d$$$. First ship will send signals at every time t for which $$$t$$$ mod $$$c$$$ $$$\equiv$$$ $$$a$$$ mod $$$c$$$ and $$$t \geq a + c$$$. Therefore we need to find smallest $$$x \geq 0$$$ for which $$$(b + d + d \cdot x)$$$ mod $$$c \equiv a$$$ mod $$$c$$$. Let $$$y = gcd(c, d)$$$. $$$d \cdot x$$$ mod $$$c \equiv (a-b-d)$$$ mod $$$c$$$
Therefore, possible values for $$$x$$$ exist only if $$$y | (a-b-d)$$$ mod $$$c$$$, and can be found by,
$$$(d/y) \cdot x$$$ mod $$$(c / y) \equiv ((a-b-d) / y)$$$ mod $$$(c / y)$$$
Since, $$$(d/y)$$$ and $$$(c/y)$$$ are coprime, we can find $$$(d/y)^{-1} mod (c/y)$$$ using Euclidean theorem or Euler's theorem (will need to use Pollard Rho to use that). Then, their signals will occur simultaneously for all values of x for which $$$x$$$ mod $$$(c / y) \equiv ((a-b-d) / y) \cdot ((d/y)^{-1} mod (c/y)) $$$ mod $$$(c / y)$$$
so the answer would be $$$b + d + d*x$$$
Great approach thanks for sharing