### flamestorm's blog

By flamestorm, 6 weeks ago,

Thank you for competing! I hope you had fun in the contest. UPD: Implementations have been added.

103150A - Addition Range Queries

Short Solution
Editorial
Implementation

103150B - Arrowing Process

Short Solution
Editorial
Implementation

103150C - EZPC Sort

Short Solution
Editorial
Implementation

103150D - Moving Points

Short Solution
Editorial
Implementation

103150E - o

Short Solution
Editorial
Implementation

103150F - Palindromicity

Short Solution
Editorial
Implementation

103150G - Segmentation Fault

Short Solution
Editorial
Author's Note
Implementation

103150H - William Tell

Short Solution
Editorial
Implementation

103150I - X-OR XOR

Short Solution
Editorial
Implementation

• +100

 » 5 weeks ago, # |   +20 flamestorm simp army assemble!
•  » » 5 weeks ago, # ^ |   +13 flamestorm orz
•  » » » 5 weeks ago, # ^ |   +12 flamestorm orz
•  » » » » 5 weeks ago, # ^ |   +11 flamestorm orz
•  » » » » » 5 weeks ago, # ^ |   +23 flamestorm orz
•  » » » » » » 5 weeks ago, # ^ |   +9 flamestorm orz
•  » » » » » » » 5 weeks ago, # ^ |   +11 flamestorm orz. Glad to see you are purple now
 » 5 weeks ago, # | ← Rev. 3 →   0 I think problem B can be represented in an easier(more intuitive for me) way: we can look at >< as 10, and the problem can be represented as to sort a binary string, so we can iterate over horizontal and vertical lines and count zeros and ones on subsegments with the correct direction(>< on horizontal, v^ on diagonal)
 » 5 weeks ago, # |   0 Interesting problems!
 » 5 weeks ago, # | ← Rev. 3 →   +5 readable solutions: A#include "bits/stdc++.h" using namespace std ; void solve(){ int n,k ; cin >> n >> k ; vectora(n) ; for(int &x:a) cin >> x ; int mx=*max_element(a.begin(),a.end()) ; int mn=*min_element(a.begin(),a.end()) ; cout<>TC ; while(TC--) solve() ; }  B#include "bits/stdc++.h" using namespace std ; int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int n,m ,ans=0; cin>>n >> m ; vectora(n) ; for(string &x:a) cin >> x ; for(int i=0;i' ; if(a[i][j]=='<') ans+=c ; if(a[i][j]=='v'||a[i][j]=='^') c=0 ; } } for(int j=0;j') c=0 ; } } cout<>n >> m ; vectora(n) ; for(string &x:a) cin >> x ; for(int i=0;i' ; if(a[i][j]=='<') ans+=c ; if(a[i][j]=='v'||a[i][j]=='^') c=0 ; } } for(int j=0;j') c=0 ; } } cout<> n >> s>>t ; bool ok=0 ; for(char x:t) ok|=x=='o' ; cout<<(ok?"YES\n":"NO\n") ; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int TC ; cin >>TC ; while(TC--) solve() ; }  F#include "bits/stdc++.h" using namespace std ; void solve(){ int n,s=0,d; cin>>n ; char c='a' ; auto get=[&](){ int c=1; while(s+c*(c+1)/2<=n) c++ ; c-- ; s+=c*(c+1)/2 ; return c ; } ; string ans ; for(int i=0;i<10;i++){ d=get() ; while(d--) ans+=c ; c++ ; } cout << ans << '\n' ; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int TC ; cin >>TC ; while(TC--) solve() ; }  G#include "bits/stdc++.h" using namespace std ; void solve(){ vectorsm={0,0,1,7,4,2,6} ; int n ; cin >> n ; string mx,mn ; for(int i=0;i1){ if(n%7==1) mn[0]='1',mn[1]='0' ; if(n%7==4) mn[0]='2',mn[1]='0' ; if(n%7==3) mn[0]='2',mn[1]='2' ; } if(mn.size()>2&&n%7==3) mn[1]='0',mn[2]='0' ; cout<>TC ; while(TC--) solve() ; }  H#include "bits/stdc++.h" #define ld long double #define int long long using namespace std ; int po(int b,int p){ int r=1 ; for(;p;b=(b*b),p/=2) if(p&1) r=(r*b) ; return r ; } void solve(){ ld ans =0 ; int n ; cin >>n ; for(int i=0;i> a ; if(a>20){ ans+=2 ; continue ; } ans+=2-(ld)1/(ld)po(2LL,a-1) ; } cout << ans << '\n' ; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout << setprecision(20) << fixed ; int TC ; cin >>TC ; while(TC--) solve() ; }  I#include "bits/stdc++.h" #define int long long using namespace std ; void solve(){ int a,b,x=0,i=0 ;cin>>a>>b ; while(a||b){ if(a%2==0&&b%2==1){ cout<<"-1\n" ; return ; } if(a%2==1&&b%2==0) x+=(1LL<>TC ; while(TC--) solve() ; } 
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 can you explain solution of problem H
•  » » » 5 weeks ago, # ^ |   +4 From linearity of expectation, you can deal with each stack independently and then sum up each stacks' results. So for one stack. $\displaystyle\mathop{{}\mathbb{E}}[A_i]=\frac{1}{2}\mathop{{}\mathbb{E}}[A_{i}-1]+\frac{1}{2}.\mathop{{}\mathbb{E}}[0]+1$Since there is a 50% chance of reducing the stack size by 1 and 50%, we remove the entire stack. 1 is added for the current operation that we're doing Now since $\mathop{{}\mathbb{E}}[0]=0$ $\displaystyle \therefore \mathop{{}\mathbb{E}}[A_i]=1+\frac{1}{2}\mathop{{}\mathbb{E}}[A_i-1]$ $\displaystyle\implies\mathop{{}\mathbb{E}}[A_i]=1+\frac{1}{2}+\frac{1}{4}\mathop{{}\mathbb{E}}[A_i-2]$ $\displaystyle\implies \mathop{{}\mathbb{E}}[A_i]=1+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\dots+\frac{1}{2^{A_i-1}}$From Geometric Progression summation formula. $\displaystyle\implies \mathop{{}\mathbb{E}}[A_i]=1\times\frac{1-\frac{1}{2^{A_i}}}{1-\frac{1}{2}}$ $\displaystyle\boxed{\therefore\mathop{{}\mathbb{E}}[A_i]=2-\frac{1}{2^{A_i-1}}}$Now as we discussed above from linearity of expectation. The final answer would just be, $\displaystyle F= \sum_{i=0}^N\mathop{{}\mathbb{E}}[A_i]$
•  » » » » 5 weeks ago, # ^ |   0 Thank you.
 » 5 weeks ago, # |   +3
 » 5 weeks ago, # |   +9 For H you can precompute an array of the answer to the 1-stack problem for 1-100 apples then lookup arr[min(100, ai)] and add. The figures after that are negligible. That way you don't even need to find a closed form formula.
•  » » 5 weeks ago, # ^ |   +4 Yeah, the problem seems like it would be better if the calculation was done modulo some prime, though I think your observation is really nice, and honestly pretty funny
•  » » » 5 weeks ago, # ^ |   +7 Thank you.
•  » » » 5 weeks ago, # ^ |   0 Funnily enough, the reason why I didn't do it modulo some prime is that this was my original solution :P. However the testers showed me that you could use binary exponentiation and it would work, and I thought that would be a more "standard" solution, so that's the one I used in the editorial.
 » 5 weeks ago, # |   0 Can anyone plz. explain how to solve problem I. I don't get it from editorial . and also if possible plz. tell me the approach to solve the problem like this.
•  » » 5 weeks ago, # ^ | ← Rev. 6 →   +5 The 1-bit problem has 8 cases(a=0,1; b=0,1; x=0,1) so it can be worked out easily(replace a,b,x by 0 or 1 then check the equation x or a == x xor b). You see that if a=0 and b=1 there is no solution(neither x=0 nor x=1 work). Otherwise you can pick x=0 if a=0, b=0; x=0 if a=1, b=1 and x=1 if a=1, b=0 (notice that this is the same as the 'xor' function except when a=0 and b=1 that is when there's no solution). Because 'or' and 'xor' are bitwise operations, you can build the solution bit by bit (if ai=0 and bi=1 for some position i in the bit string you can stop and output '-1' if no bit pairs are like that you have a valid solution). Alternatively you can just realize that a xor b is a solution if any solution exists. So you check if x = a xor b satisfies x or a == x xor b. If it does you output x, otherwise -1. Also for a general approach, the hint of testing the 1-bit case probably generalizes.
 » 5 weeks ago, # |   0 I have a doubt, I am not able to understand: in the editorial of problem E, while calculating ai why we are taking last 1. I got that ai-1 will happen with probability 1/2 and 0 with 1/2 but I have a doubt in last 1. Anyone please help! Thank you!
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   +1 Let $E[n]$ be expected value for a pile of length $n$, then,$E[1]=1$$E[n]= 1+(E[n-1])/2$or $E[n]=2.(1-(1/2)^{n})$Since $(1/2)^n$<<<$10^{-4}$ for $n>=30$ so, for $n>=30$ , $E[n]=2$.So you just need to calculate $E[n]$ for $n<30$.120425307
 » 5 weeks ago, # |   0 flamestorm please bring more contests like these although I missed this one but today I was trying solving these problems and I really enjoyed it
 » 5 weeks ago, # |   0 I was able to solve 5 problems and got 65 rank. Is it good for a newbie or bad ?? I'm new so idk how to judge myself in unrated contest.
•  » » 5 weeks ago, # ^ |   +5 I think that's pretty good. If we rule-of-thumb that this contest was 3 A's 3 B's and 3 C's, that means in a regular contest you would expect to solve A and B most of the time (probably more, since instead of solving another AAB like you did here, you would be spending time solving the C). I'd estimate that would get you maybe 1500-1600ish rating.
•  » » » 5 weeks ago, # ^ |   0 Thanks for explaining this well. This kind of motivated me.
 » 5 weeks ago, # | ← Rev. 2 →   0 In problem E if string t has n o's and string s has (n -1) o's then I think it won't be possible to convert s to t because in such a situation if we choose two different indices in s then we will be converting one character to 'o' and other character as non — 'o' so it doesn't matter how many operations we perform we will be left with one non — 'o' in s while t is having all o's and answer should be NO. I don't know where I am going wrong because editorial says t should have atleast on 'o' for answer to be YES. Please help
•  » » 5 weeks ago, # ^ |   0 The second character you convert can also be an $\texttt{o}$, since the statement says: pick two characters in different positions, replace one of them with $\texttt{o}$, and replace the other one with any lowercase English letter.
•  » » » 5 weeks ago, # ^ |   0 flamestorm that means I can convert both the characters at different indices to 'o' right ?? Oh man sorry for bothering I misunderstood the problem statement and thought that if I replace one character with 'o' I can't replace other with 'o' btw thank you very much for clearing this doubt.U r amazing please bring more contests like these.
 » 4 weeks ago, # |   0 I think this is a better solution for Problem A: Just sort the vector and without considering the value of k just take absolute difference of first and last term. #include using namespace std; #define endl '\n' #define ll long long int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); ll t;cin>>t; while(t--){ ll n,k;cin>>n>>k; vector v(n); for(int &x:v){ cin>>x; } sort(v.begin(),v.end()); ll ans=abs(v[n-1]-v[0]); cout<
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 I think this is the same as the editorial, but is a bit slower theoretically (finding minmax in $\mathcal{O}(n \log{n})$ as opposed to $\mathcal{O}(n)$).
 » 4 weeks ago, # |   0 void solve(){ll a,b; cin>>a>>b; if(b>a){cout<<-1<