When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

crypt1k's blog

By crypt1k, 4 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;
	}
}
  • Vote: I like it
  • +23
  • Vote: I do not like it

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

LOL, so pruning sometimes works ....

  • »
    »
    4 years ago, # ^ |
    Rev. 9   Vote: I like it -37 Vote: I do not like it

    LOL. You didn't know that?

    Don't think that everything has to be solved by polynomial time/theoretically efficient algorithms. That's a very bad mindset implanted by Competitive Programming on novices. Many algorithms have bad worst case runtime but they run fast in practice. For example, Dinic's algorithm (without any hueristics). Another example is Simplex.

    Just in case you wish to emphasize about algorithms that depend mainly on pruning to improve runtime, I have seen (and used) a $$$\mathcal{O}(2^N)$$$ algorithm to solve a problem where the intended time complexity is $$$\mathcal{O}(N*K)$$$ (where $$$K$$$ is of some reasonable size). In fact, the runtime of the "pruning" algorithm is much faster than that of the "efficient" algorithm too. In case you are interested in which problem I am referring to, check problem E of AtCoder educational DP contest.

    Lol. You definitely need to get a Computer Science education. Life is too complicated to be handled by polynomial time algorithms only.

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

      I think you are not wrong, but you don't need to say "LOL. You didn't know that?" or "Lol. You definitely need to get a Computer Science education." There are better ways to share your knowledge.

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

        Guess you're right. Sorry for my harsh tone. I just cannot help being triggered whenever I see naive comments from people, that insult the work of Computer Scientists.

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

It's likely weak tests and it's only easier to squeeze stupid things with their multiple-test-cases format. Even if your solution works 10s on one or two tests, you're fine.