https://en.wikipedia.org/wiki/Benford%27s_law

It's more probable to have 1 as a first character then any other. Why? You have two randomizations — one randomizes upper_bound, the second randomizes number itself. Let's check just the digits. You can see that number 1 can be achieved for every upper_bound, and number 2 cannot be achieved for upper_bound equal to 1. You can generalize it even further, I don't have a formal proof.

I did exactly the same but I have no idea why my solution got WA on second test set :( can anyone help me find my bug please?

#include <iostream>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <map>
#include <vector>
#include <set>
#include <algorithm>
#include <sstream>
#include <queue>
#include <cctype>
#include <cmath>
#include <fstream>

using namespace std;

typedef long long ll;
#define REP(i,k) for(int (i)=0;(i)<(k);(i)++)
#define INF ~(1<<31)
#define CLR(a) memset((a),0,sizeof((a)))
#define EPS 1e-9
#define DBG 1
#define D(s,v) if(DBG) cout<<(s)<<": "<<(v)<<endl;
#define DVEC(s,v) if(DBG) {cout<<(s)<<": "; for(int i=0;i<(v).size();i++) cout<<(v)[i]<<" "; cout<<endl;}
#define DARR(s,v,n) if(DBG) {cout<<(s)<<": "; for(int i=0;i<n;i++) cout<<(v)[i]<<" "; cout<<endl;}

int main(){
    ios_base::sync_with_stdio(0);
    int T; cin>>T;

    for(int cs=1;cs<=T;cs++){
        int U; cin>>U;
        set<char> letters;
        map<char,ll> freq;

        for(int i=0;i<10000;i++){
            int M; cin>>M;
            string s; cin>>s;
            for(int j=0;j<s.size();j++){
                letters.insert(s[j]);
            }
            freq[s[0]]++;
        }

        char res[10]; CLR(res);

        set<char>::iterator it;
        for(it = letters.begin(); it!=letters.end();it++){
            if(!freq.count(*it)){
                res[0] = *it;
                break;
            }
        }

        map<char,ll>::iterator it2;
        vector<pair<ll, char> > v;
        for(it2=freq.begin();it2!=freq.end();it2++){
            v.push_back(make_pair(-it2->second, it2->first));
        }
        sort(v.begin(), v.end());

        for(int i=0;i<v.size();i++){
            res[i+1] = v[i].second;
        }

        cout<<"Case #"<<cs<<": ";
        for(int i=0;i<10;i++){
            cout<<res[i];
        }
        cout<<endl;

    }
}

Me too, but I think O(n * log(n) * d * d) is possible:

Store all a[i] in a map as reduced fractions — (a[i]/1) pairs.

Try each unique slice (s) D times — from (a[i]/1) to (a[i]/D):

• Try all multiples of s from 1 to D O(D*log(N)) in increasing orders as we benefit from fewer slices to get s value.
• If you need additional slices try to get them from the next D biggest that are not multiples. O(D+log(N) which is smaller than above)

There are nd possible slice sizes, as you've noticed for the n^2d solution. The trick for nd^2 is to save, for each slice size, a list of the original pancakes that can create that size of slice. This can all be done in nd time plus some sorting. To test whether k cuts are possible, we only have to consider slice sizes with at least d-k pancakes in the corresponding lists. While these lists may be large, we never have to consider more than the k smallest pancakes in each, hence the runtime.

I solved post-contest in $$$O(nd \log nd)$$$

There are two things you want to know about each of the $$$O(nd)$$$ possible slice sizes: first is the maximum number of cuts you can "save" by choosing that size, second is whether it is possible to even make enough slices of that size. It's easy to obtain these properties in $$$O(n)$$$ per slice, but we can do better.

For the first subproblem, pre-sort $$$A$$$. When generating the slice-size $$$\dfrac {A_i} k$$$, you already know $$$A_i$$$ is evenly divisible by it, so you save a cut as long as the number of slices for that size hasn't exceeded $$$d$$$ yet. A couple of hashmaps will store these statistics fine — be sure to reduce each fraction to lowest terms via the GCD before using them as keys.

For the second subproblem, collect all generated slice-sizes, sort them (recalling how to compare fractions), then binary search for the largest slice-size that can make enough slices.

Input is randomly chosen, it's not hand-made

Maybe overflow when you calculate the mean. I think it can happen that the sum of all numbers with an incorrect digit map can exceed 2^64 (I've tried the same solution at first, but it was to slow... Ho did you implement permutations? I've used next_permutation from STL)

I tried testing it locally, even with number of queries upto $$$10^6$$$ the probability of this working is only $$$90\%$$$

In 1A my rank increased around by 70 after review.

You are reading a number from the input that has the length bigger then the accepted length of the maximum value of a unsigned int. I suppose that the reading truncates and some part is left over and this messes up the rest of your reading. I am not sure what the name of this behaviour is, but I dont think it is overflow.

High level approach: solve it the same as any other problem, except that when you want to discard any idea because it is not going to solve some of the tests, you should first think about what are the properties of the tests that break your idea, and how likely are they to be generated randomly.

You may look around and find some problems of this kind for practice, so that you'll learn the most common observations about random tests (e.g. "randomly generated permutation will have relatively short LIS" or "randomly generated tree will have relatively small depth").

TLDR: If all is really random the frequency of first digit being 1 is bigger than first digit being 2 which is bigger than first digit being 3 ... first digit being 0 has probability of 0 on the other hand.

Tony first, then conor

My solution for the first problem was as the following:

Keep track of the xy coordinates of Peppurr's after each move. If the Manhattan distance between the xy coordinates and the origin became less than or equal to the move count then at this moment they will meet. If the distance is always greater than the move count then it's impossible.

For example if we considered the first sample case:

4 4 SSSS

After the first move the distance = |4| + |3| = 7 > 1 (can't meet)

After the second move the distance = |4| + |2| = 6 > 2 (can't meet)

After the third move the distance = |4| + |1| = 5 > 3 (can't meet)

After the fourth move the distance = |4| + |0| = 4 = 4 (can meet)

Then the solution equals to 4

Here is my code for this problem. This is the only problem I could solve completely correctly in this round :"D

M and many other things need to be long long