crypt1k's blog

By crypt1k, 5 years ago, In English

This is Third Question from Kickstart Round G — https://codingcompetitions.withgoogle.com/kickstart/round/0000000000050e02/000000000018fd5e

Normal 3^n recursion with two cases handled — when no further cases need to be considered, and when all cases are right, passes in the time limit.

I'm not sure if it is just weak test cases or we can prove complexity of the solution.

int n,h;
vector<pair<int,int>> a(21),suffixSum(21);
int ans = 0;

int power3[21];

void dfs(int s1, int s2, int index) {
	if(index==n) {
		if(s1>=h&&s2>=h) ans++;
		return;
	}
    
        // No combination will be right
	if(s1+suffixSum[index].f<h||s2+suffixSum[index].s<h) return;

        // Any combination after this are right
	if(s1>=h && s2>=h) {
		ans += power3[n - index];
		return;
	}

	dfs(s1+a[index].f,s2, index+1);
	dfs(s1,s2+a[index].s, index+1);
	dfs(s1+a[index].f,s2+a[index].s, index+1);
}

signed main() {
	int t = 100;
	cin>>t;

	power3[0] = 1;
	for(int i=1;i<21;i++) power3[i] = power3[i-1]*3;

	for(int a0=1;a0<=t;a0++) {
		cin>>n>>h;

		for(int i=0;i<n;i++) cin>>a[i].f;
		for(int i=0;i<n;i++) cin>>a[i].s;

                sort(a.begin(), a.end(), greater<pair<int,int>>());

		ans = 0;

		suffixSum[n-1] = a[n-1];
		for(int i=n-2;i>=0;i--) {
			suffixSum[i] = {
                                          suffixSum[i+1].f + a[i].f,
					  suffixSum[i+1].s + a[i].s
                                       };
		}

		dfs(0,0,0);

		cout<<"Case #"<<a0<<": "<<ans<<endl;
	}
}

Full text and comments »

  • Vote: I like it
  • +23
  • Vote: I do not like it

By crypt1k, 6 years ago, In English

It would be great if CF could allow virtual participation in Live Contests. If user isn't in a mood of giving the whole contest or doesn't want his/her rating to be affected, it will be nice for them. It will also decrease the number of secondary accounts people maintain for giving contests for practice.

Full text and comments »

  • Vote: I like it
  • +24
  • Vote: I do not like it