Блог пользователя flamestorm

Автор flamestorm, 3 года назад, По-английски

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
Разбор задач EZ Programming Contest #1
  • Проголосовать: нравится
  • +100
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

flamestorm simp army assemble!

»
3 года назад, # |
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)

»
3 года назад, # |
Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

readable solutions:

A
B
C
E
F
G
H
I
  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    can you explain solution of problem H

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +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]$$$

»
3 года назад, # |
  Проголосовать: нравится +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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +7 Проголосовать: не нравится

      Thank you.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 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.

»
3 года назад, # |
  Проголосовать: нравится 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.

  • »
    »
    3 года назад, # ^ |
    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.

»
3 года назад, # |
  Проголосовать: нравится 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!

  • »
    »
    3 года назад, # ^ |
    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

»
3 года назад, # |
  Проголосовать: нравится 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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +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.

»
3 года назад, # |
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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 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.
»
3 года назад, # |
  Проголосовать: нравится 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<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 года назад, # ^ |
    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)$$$).