flamestorm's blog

By flamestorm, 3 years ago, In English

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
  • Vote: I like it
  • +100
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it +20 Vote: I do not like it

flamestorm simp army assemble!

»
3 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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)

»
3 years ago, # |
Rev. 3   Vote: I like it +5 Vote: I do not like it

readable solutions:

A
B
C
E
F
G
H
I
  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    can you explain solution of problem H

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      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]$$$

»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +7 Vote: I do not like it

      Thank you.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    3 years ago, # ^ |
    Rev. 6   Vote: I like it +5 Vote: I do not like it

    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.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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<bits/stdc++.h>
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<int> v(n);
        for(int &x:v){
            cin>>x;
        }
        sort(v.begin(),v.end());
        ll ans=abs(v[n-1]-v[0]);
        cout<<ans<<endl;
    }
    return 0;
}
  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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)$$$).