ANUBGC question :)

general
,
1

Hi,

Awesome cook-off and hats off to setter for so many good problems!!

I know that the solution for this problem must rely on the “constructive/deterministic side” i.e. we must be able to construct solution by placing digits in some smart way and play with the numbers in that fashion…

But, is there any possibility that a randomized solution would work?

I mean, we do some trials, say K, where we “simulate” the process of opening a page of a book for N times.

Every time we see that a page contains a digit we increase some answer variable.

In the end, we divide that answer value by the number of our trials and we should have an approximate answer (and I did…Sadly I was running out of time and couldn’t tweak the parameters any longer), but, I am just wondering if this was a feasible way?

Here’s the code I was attempting to use:

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <string>
#include <map>
#include <random>
#include <chrono>
#include <limits.h>
using namespace std;

bool contains(long long int N, int digit)
{
	while(N>0)
	{
		if(N%10==digit)
			return true;
		else
			N /= 10;
	}
	return false;
}

int roundUp(int numToRound, int multiple)
{
 if(multiple == 0)
 {
  return 0;
 }
 else if(numToRound % multiple == 0)
 {
  return numToRound;
 }

 int roundDown = (int) (( (double) numToRound / multiple ) * multiple);
 int roundUp = roundDown + multiple; 
 int roundCalc = roundUp;
 return (roundCalc);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t;
	cin >> t;
	while(t--)
	{
		unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
		int N;
		cin >> N;
		default_random_engine generator(seed);
		uniform_int_distribution<long long int> MaxP(1,N); //number of pages
		uniform_int_distribution<int> digit(0,9); //digits
		long long avg = 0LL;
		int limit = 1000;
		for(int xx = 0; xx <= 24; xx++){
		int ind = 0;
		int ans = 0;
		while(ind < limit)
		{
			long long int page = MaxP(generator);
			int numero = digit(generator);
			if(contains(page,numero))
				ans++;
			ind++;
		}
		avg+=ans;
	}
	avg /= 25;
		int gcdAns = __gcd((int)ceil((double)avg/100), (int)ceil((double)limit/100));
		cout << ceil((double)avg/100)/gcdAns << "/" << ceil((double)limit/100)/gcdAns << endl;
		
	}
	return 0;
}

PS: I still want to learn the “proper” method to solve such kinds of questions, but, I’m just curious if randomization was a possible way out for this problem with the given constrains…

Best,

Bruno

2

Hi,

You can find the deterministic solution here - ANUBGC - Editorial - editorial - CodeChef Discuss

About randomization, I doubt it will work.
One input case has the following answer

149192013869605253/181607469507365620

So for a randomized solution to work, you will need to do atleast 181607469507365620 trails. Which is clearly not possible.

1 Like
3

I think randomization will not work here. Simple reason is that if the answer was to output in the form of a decimal, then it MIGHT have worked. But here we were required to give the answer as a proper fraction, which implicitly demanded perfect solution. Also, as N<=10^17, we cannot go linearly with each number. The problem is obviously based on algebra and bit of combinatorics.

For example : let n = 2351. then dividing it into [1,999], [1000,1999], [2000,2299], [2300,2349] ,[2350,2351], we can calculate the number of numbers having 1s,2s,3s,… in these intervals.

Also P=P(0 selected) * P(0 comes)+P(1 selected) * P(1 comes) + P(2 selected) * P(2 comes)…
But selecting 0,1,2,… is equally likely = 0.1
So, P=1/10 [P(0 comes)+P(1 comes)+P(2 comes)+…]
=(sum of number of numbers having 0,1,2,…9)/10N
P(0 comes) = floor(N/10).
Others are to be calculated using the intervals as above.

Another way (which I did not try) is to observe that
P= (sum of number of distinct digits in numbers from 1 to N)/(10*N)
Again, some generalization ought to exist for number of distinct digits in a continuous range of numbers.

4

Hmm… I knew it was a long shot going for the non-deterministic approach :slight_smile: I will take next few days to learn and incorporate digit DP in my arsenal of techniques :smiley:

Thank you very much!!

5

I took too long to type. The question was marked closed when I submitted my answer :stuck_out_tongue: