CodeGuerra Tutorial

Revision en22, by agrim07, 2023-12-22 20:26:20

A — PAS C3

Idea: agrim07

Hint

Tutorial

$$$\displaystyle\frac{{c_1 + c_2 + c_3}}{h} \times 10 \leq 4$$$

which can be re-written as

$$$c_3 \geq \displaystyle\frac{2h}{5} - c_1 - c_2 $$$

The above inequality can be modified to the following form to remove fractional values:

$$$c_3 \geq \displaystyle\left\lceil\frac{2h}{5}\right\rceil - c_1 - c_2$$$

We will use the following property to avoid dealing with float values as they are prone to precision errors:

$$$\displaystyle\lceil \frac{a}{b} \rceil = \lfloor \frac{a + b - 1}{b} \rfloor$$$

So the final answer should be

$$$ \displaystyle\max\{12, \lfloor \frac{2h + 4}{5} \rfloor - c_1 - c_2\} $$$

Alternatively, we can iterate from 12 to 40 while checking if the current value satisfies the passing criteria.

Code

include<bits/stdc++.h>

using namespace std;

define int long long

void solve() { int a, b, c; cin >> a >> b >> c; cout << max(12LL, (2 * c + 4) / 5 — a — b) << endl; }

signed main() {

int tt = 1;
// cin >> tt;
while(tt--) {
    solve();       
}
return 0;

}

</spoiler>

### B &mdash; Yet Another Merchandise Distribution

Idea: [user:pvtr,2023-12-22]

<spoiler summary="Hint">
Think of three case when last letter of given string is S , M and L
</spoiler>

<spoiler summary="Tutorial">
To solve this problem we will take three cases when input string last character is S Then we need to output in descending order. And if it is M then it should be placed after all small sized merch. And if it is L then need to simply arrange in ascending and output. 
For Implementation of this, in solution we used a comparator function in which we assigned a value to each string, k-XS represent (-k), M represents 0 and k-XL represents +k so simply we can sort in ascending order of assigned value which will give us required array.

</spoiler>


<spoiler summary="Code">

include <bits/stdc++.h>

using namespace std;

int get(string &a) { int A = 0; if(a.size() == 1) A = 0; else { if(a.back() == 'S') A -= (a[0] — '0'); else A += (a[0] — '0'); } return A; }

bool cmp(string &a, string &b) { if(get(a) < get(b)) return true; return false; }

void solve(){ int n; cin >> n; vector s(n); for(auto &x: s) cin >> x; sort(s.begin(), s.end(), cmp); for(auto &x: s) cout << x << " "; cout << "\n"; }

int main() { int t; cin >> t; while(t--) solve(); } ```

C — Fibonacci Parity

Idea: Fremder

Hint

Tutorial

Upon observation, it's evident that the function $$$f(s)$$$ generates the Fibonacci sequence starting from $$$f(s_2)$$$ . Given the established fact that every third Fibonacci number is even, we can conclude that $$$f(s)$$$ is even for $$$s$$$ = $$$s_{2+3i}$$$ and odd otherwise .

Now we got parity for nth element of both $$$s$$$ and $$$f(s)$$$ , compare parity of both and answer .

Code

include<bits/stdc++.h>

using namespace std;

define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

define int long long

define pb push_back

define ppb pop_back

define MOD 1000000007;

const int N=1e5;

void solve(){ int n; cin >> n; bool s = ((n%2)==0); bool fs = ((n%3)==2);

if(s == fs){
   cout << "YES";
}else cout << "NO";

cout << endl;

}

signed main() { fastio();

int t = 1;
cin >> t;
while(t--){
    solve();       
   }
return 0;

} ```

D — Subsequence Query

Idea: Fremder

Hint

Tutorial

During each query, the code efficiently checks if the suffix point occurs before the prefix point in the precomputed arrays , this determines if $$$str$$$ is subsequence of remaining string or not

Code

include<bits/stdc++.h>

using namespace std;

define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

define int long long

define pb push_back

define ppb pop_back

define MOD 1000000007;

const int N=1e5;

void solve(){ int m, n; cin >> n >> m; string s, t; cin >> s >> t; int index = 0; s.insert(0, "0"); t.insert(0, "0"); vector pre(n + 1), suff(n + 2); for(int i = 1; i <= n; i++) { if(s[i] == t[index + 1] and index<m) index++; pre[i] = index; } suff.back() = index = t.size(); for(int i = n; i > 0; i--) { if(s[i] == t[index — 1] and index>1) index--; suff[i] = index; } int q; cin >> q; while(q--) { int l, r; cin >> l >> r; if(suff[r + 1] — pre[l — 1] < 2) cout << "YES\n"; else cout << "NO\n"; } }

signed main() { fastio();

int t = 1;
while(t--){
    solve();       
   }
return 0;

} ```

E — Destroy them All

Idea: NirbhayPaliwal

Hint 1

Hint 2

Tutorial

Now Let's take this whole problem as $$$n$$$ sub-problem where answer to $$$ith$$$ problem is number humans to be deployed on $$$ith$$$ spot.

Now if we are able to destroy all spots by deploying $$$k$$$ number of humans then we will surely be able to do it by deploying $$$k+1$$$ people. Hence to solve this sub problem we will apply binary search on number of humans to be deployed, And to check for any value we will maintain one variable $$$buff$$$ denoting number of humans which can move to either of sites, use two pointers one pointing at left side of destroyed site and other at right side And if it is possible to destroy any site by placing $$$buff$$$ on it simply destroy it and in this way if we can destroy them all then $$$k$$$ value returns true and if both both sites i.e. left and right cannot be destroyed then function returns false.

Code

include<bits/stdc++.h>

using namespace std;

define int long long int

vector a,b; int n; bool check(int key,int ind) { int s=ind-1,e=ind+1; int buff=key+a[ind]; // extra people which can go to any site once their site is broken while(s!=-1 || e!=n) { int flag=0 ;// to check buff changes if(s!=-1) { if(a[s]+buff>=b[s]) { buff+= a[s]; s--; flag=1; } } if(e!=n) { if(a[e]+buff>=b[e]) { buff+= a[e]; e++; flag=1; } } if(!flag) return 0; } return 1; }

signed main() { int T; cin >> T; while(T--) { cin >> n; a.clear();b.clear(); a.resize(n);b.resize(n); for(int i=0;i<n;i++) cin >> a[i]; for(int i=0;i<n;i++) cin >> b[i]; vector ans(n); for(int i=0;i<n;i++) { int lo=(b[i]-a[i]),hi=1e12; while(hi-lo>1) { int mid=(hi+lo)/2; if(check(mid,i)) { hi=mid; } else { lo=mid+1; } if(check(lo,i)) ans[i]=lo; else ans[i]=hi; } } for(int i=0;i<n;i++) { cout << ans[i] << ' '; } cout << endl; } } ```

F — PAS Makeup

Idea: agrim07

Hint

Tutorial

  • $$$i$$$ denotes the number of turns left,
  • $$$p$$$ denotes the parity of Rajat’s score,
  • $$$q$$$ denotes the parity of Dr. S’s score, and
  • $$$turn$$$ is 0 if it is Rajat’s turn and 1 if it is Dr. S’s turn.

Let $$$p_{\text{even}}$$$ and $$$p_{\text{odd}}$$$ denote the probabilities of landing \text{even} and \text{odd} elements, respectively, among the first $$$n - 1$$$ elements of $$$a$$$. We will consider the scenario where $$$a_n$$$ is rolled on the die separately.

The transitions will be as follows:

If it is Rajat’s turn, then there are 2 additional cases:

Case 1: When $$$a_n$$$ is odd,

$$$dp[i][p][q][turn] = p_{\text{even}} \cdot dp[i - 1][p][q][turn \oplus 1] + p_{\text{odd}} \cdot dp[i - 1][p \oplus 1][q][turn \oplus 1] + p_n \cdot dp[i - 1][p \oplus 1][q]$$$
$$$[turn]$$$

Case 2: When $$$a_n$$$ is even,

$$$dp[i][p][q][turn] = p_{\text{even}} \cdot dp[i - 1][p][q][turn \oplus 1] + p_{\text{odd}} \cdot dp[i - 1][p][q \oplus 1][turn \oplus 1] + p_n \cdot dp[i - 1][p][q][turn]$$$

Similarly, for Dr. S’s turn:

Case 1: When $$$a_n$$$ is odd,

$$$dp[i][p][q][turn] = p_{\text{even}} \cdot dp[i - 1][p][q][turn \oplus 1] + p_{\text{odd}} \cdot dp[i - 1][p][q \oplus 1][turn \oplus 1] + p_n \cdot dp[i - 1][p \oplus 1][q]$$$ $$$[turn]$$$

Case 2: When $$$a_n$$$ is even,

$$$dp[i][p][q][turn] = p_{\text{even}} \cdot dp[i - 1][p][q][turn \oplus 1] + p_{\text{odd}} \cdot dp[i - 1][p][q \oplus 1][turn \oplus 1] + p_n \cdot dp[i - 1][p][q][turn]$$$

where $$$p_n$$$ is the probability of rolling $$$n$$$.

Code

include <bits/stdc++.h>

using namespace std;

define MOD 1000000007

define int long long

int binExp(int a, int b, int M){ int ans = 1; while(b){ if(b & 1) ans = (ans * 1LL * a) % M; a = (a * 1LL * a) % M; b >>= 1; } return ans; }

void solve(){ int n, k, even, odd = 0; cin >> n >> k; vector v(n); for(int i = 0; i < n; i++) { cin >> v[i]; if(v[i] & 1) odd++; }

even = n - odd;
int inv = binExp(n, MOD - 2, MOD);
if(v.back() & 1)
    odd--;
else
    even--;
even *= inv; even %= MOD;
odd *= inv; odd %= MOD;

int dp[k + 1][2][2][2];
memset(dp, 0, sizeof(dp));

for(int p = 0; p < 2; p++) {
    for(int q = 0; q < 2; q++) {
        for(int turn = 0; turn < 2; turn++) {
            if(p * q == 0)
                dp[0][p][q][turn] = 1;
        }
    }
}

for(int i = 1; i <= k; i++) {
    for(int p = 0; p < 2; p++) {
        for(int q = 0; q < 2; q++) {
            for(int turn = 0; turn < 2; turn++) {
                dp[i][p][q][turn] += (even * dp[i - 1][p][q][turn ^ 1]) % MOD;

                if(turn)
                    dp[i][p][q][turn] += (odd * dp[i - 1][p][q ^ 1][turn ^ 1]) % MOD;
                else
                    dp[i][p][q][turn] += (odd * dp[i - 1][p ^ 1][q][turn ^ 1]) % MOD;

                if(v.back() & 1) {
                    if(turn)
                        dp[i][p][q][turn] += (inv * dp[i - 1][p][q ^ 1][turn]) % MOD;
                    else
                        dp[i][p][q][turn] += (inv * dp[i - 1][p ^ 1][q][turn]) % MOD;
                }
                else 
                    dp[i][p][q][turn] += (inv * dp[i - 1][p][q][turn]) % MOD;

                dp[i][p][q][turn] %= MOD;
            }
        }
    }
}

cout << dp[k][0][0][0] << endl;

}

signed main() { ios::sync_with_stdio(false); cin.tie(0);

int tt = 1;
cin >> tt;
while(tt--){
    solve();
}
return 0;

} ```

G — ProbabliTree

Idea: pvtr

Hint 1

Hint 2

Tutorial

Make a function $$$f$$$, which takes the parent of a subtree and return the score of that subtree if both played min-max game.

Function f

And, $$$f_v = a_v + min_{ x \in child_v} f(x)$$$ if the chance is with Somani.

Store the optimal choices made by Rathi in an array — $$$next$$$, using the function $$$f$$$.

Now to calculate the expected score of a subtree rooted at $$$v$$$, we can define a function $$$g_v$$$.

Function g

And, $$$g_v = a_v + \frac{1}{sz} \cdot \sum_{x \in child_v} g(x)$$$ if the chance is with Somani, here $$$sz$$$ is the number of direct children of vertex $$$v$$$.

Now, the answer will stored in $$$g_1$$$

Code

include <bits/stdc++.h>

using namespace std;

define int long long

const int mod = 1e9 + 7; const int N = 2e5 + 10;

vector adj[N]; int a[N]; int dp[N][2]; int dp1[N]; int vis[N];

const int MAXN = 2e5; int SUMN = 0;

int pow_(int a, int p){ if(p == 0) return 1; if(p&1){ int k = a * pow_(a, p-1); k %= mod; return k; } int k = pow_(a, p/2); k *= k; k %= mod; return k; }

int dfs(int v, int chance, int p){ if(dp[v][chance] != -1) return dp[v][chance]; if(chance&1){ int ans = 1e18; for(auto &x: adj[v]){ if(x == p) continue; ans = min(ans, a[x — 1] + dfs(x, chance^1, v)); } if(ans == 1e18) ans = 0; return dp[v][chance] = ans; } int ans = 0; int next = -1; for(auto &x: adj[v]){ if(x == p) continue; if(dfs(x, chance^1, v) + a[x — 1] > ans){ next = x; ans = a[x — 1] + dfs(x, chance^1, v); } if(dfs(x, chance^1, v) + a[x — 1] == ans){ if(x < next) { next = x; } } } dp1[v] = next; return dp[v][chance] = ans; }

int solve(int v, int chance, int p){ if(dp[v][chance] != -1) return dp[v][chance]; if(chance&1){ int ans = 0; int nodes = 0; for(auto &x: adj[v]){ if(x == p) continue; ans += (a[x — 1] + solve(x, chance ^ 1, v)) % mod; ans %= mod; nodes++; } if(nodes == 0) return 0; int inv = pow_(nodes, mod — 2); ans *= inv; ans %= mod; return dp[v][chance] = ans; } if(dp1[v] == -1) return 0; return dp[v][chance] = ((a[dp1[v] — 1] + solve(dp1[v], chance ^ 1, v)) % mod); }

void clear(int n) { for(int i = 0; i < n; i++) { for(int j = 0; j < 2; j++) dp[i][j] = -1; dp1[i] = -1; adj[i].clear(); } }

void chk(int v, int p) { assert(vis[v] == 0); vis[v] = 1; for(auto &x: adj[v]) { if(x == p) continue; chk(x, v); } }

void solve() { int n; cin>>n; SUMN += n; clear(n + 5); for(int i = 0; i < n; i++) cin>>a[i], assert(a[i] <= 1e9 && a[i] >= 1); for(int i = 0; i < n — 1; i++){ int a, b; cin>>a>>b; assert(a != b); assert(1 <= a && a <= n); assert(1 <= b && b <= n); adj[a].push_back(b); adj[b].push_back(a); } for(int i = 1; i <= n; i++) vis[i] = 0; chk(1, -1); for(int i = 1; i <= n; i++) assert(vis[i] == 1); dfs(1, 0, -1); for(int i = 0; i <= n; i++) for(int j = 0; j < 2; j++) dp[i][j] = -1; cout<<(a[0] + solve(1, 0, -1))%mod<<"\n"; }

int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t; cin>>t; assert(t <= 1000); while(t--) solve(); assert(SUMN <= MAXN); } ```

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en32 English agrim07 2023-12-22 22:00:47 2 Tiny change: 'times 10 \leq 4$$\n\n' -> 'times 10 \geq 4$$\n\n'
en31 English agrim07 2023-12-22 21:06:17 182
en30 English Fremder 2023-12-22 20:44:37 0 (published)
en29 English Fremder 2023-12-22 20:43:04 5
en28 English Fremder 2023-12-22 20:39:48 49
en27 English Fremder 2023-12-22 20:38:56 47
en26 English Fremder 2023-12-22 20:37:25 189
en25 English Fremder 2023-12-22 20:33:28 48 Tiny change: '[### A &mdash; ' -> '###[A &mdash; '
en24 English agrim07 2023-12-22 20:27:49 380
en23 English agrim07 2023-12-22 20:26:38 500 Reverted to en21
en22 English agrim07 2023-12-22 20:26:20 500
en21 English agrim07 2023-12-22 20:25:45 1096 fix A
en20 English NirbhayPaliwal 2023-12-22 20:12:58 24
en19 English NirbhayPaliwal 2023-12-22 20:10:17 124
en18 English NirbhayPaliwal 2023-12-22 20:07:25 812
en17 English NirbhayPaliwal 2023-12-22 20:05:23 12
en16 English NirbhayPaliwal 2023-12-22 20:03:53 2
en15 English NirbhayPaliwal 2023-12-22 20:03:06 3
en14 English NirbhayPaliwal 2023-12-22 20:01:49 26
en13 English pvtr 2023-12-22 19:59:01 4413 Tiny change: '"Function f">\n$f_v =' -> '"Function $f$">\n$f_v ='
en12 English Fremder 2023-12-22 19:52:12 5
en11 English agrim07 2023-12-22 19:43:41 4 Tiny change: 'l\n\nIdea:[user:Nirb' -> 'l\n\nIdea: [user:Nirb'
en10 English agrim07 2023-12-22 19:42:43 2455 add F
en9 English Fremder 2023-12-22 19:37:38 27
en8 English NirbhayPaliwal 2023-12-22 18:55:29 92
en7 English NirbhayPaliwal 2023-12-22 18:51:44 1453
en6 English NirbhayPaliwal 2023-12-22 18:50:36 1210
en5 English NirbhayPaliwal 2023-12-22 18:49:41 2717
en4 English Fremder 2023-12-22 18:04:20 1311
en3 English Fremder 2023-12-22 17:36:42 1471
en2 English agrim07 2023-12-22 16:55:15 1768 Tiny change: '.' -> '`svdsd`'
en1 English Fremder 2023-12-21 11:30:27 22 Initial revision (saved to drafts)