AIIO 2006 Problem 3

Problems and Contests
#1

This is the problem: ORAC — Hard Drive , and my code is attached below

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<long long> vll;
#define speed() \
ios::sync_with_stdio(false); \
cin.tie(0)
#ifndef DEBUG
#define open(name) \
speed(); \
freopen(#name "in.txt", "r", stdin); \
freopen(#name "out.txt", "w", stdout)
#else
#define open(name) speed()
#endif
#define all(x) (x).begin(), (x).end()
#define _forI(var, start, end) for (int var = start; var < end; var++)

const int MOD = 1000;
vector<vi> dp;
int cr(int n, int blocks) {
        if (blocks == 1) {
                return 1;
        }

        if (dp[n][blocks] != -1) {
                return dp[n][blocks];
        }


        int count = cr(n, blocks/2);

        if (blocks >= 4) {
                count = (count + cr(n, blocks / 4) + cr(n, blocks / 2 - blocks / 4)) % MOD;
        }


        dp[n][blocks] = count;

        return count;
}


int main() {
        open(drive);
        int n, m;

        cin >> n >> m;

        dp.resize(n + 1, vi(1 << (n + 1), - 1));

        int ans = cr(n, 1 << n);

        cout << ans % m;

        
        return 0;
}

i don’t get why it doesn’t work, i did get some test cases but there are also MLEs and wrong answers. Please help

Thanks

#2

Your code is much too slow as it is O(2^N) (note that N can go up to 10^7, this time complexity is acceptable for N<20ish) and also appears to be double counting some items. The correct recurrence is dp[i] = dp[i-1]*dp[i-1]+dp[i-2]*np[i-1]*dp[i-1] +1 and np[i]= dp[i-2]*dp[i-2]*np[i-1]+1 where dp[i] represents the number of ways to divide a hard drive with 2^i blocks. It is the sum of the case where you do the first operations (it is just the product of the ways to divide each half), the case where you divide it using the second operation but don’t ever divide the array in the middle hence the np terms times the ways to divide the other two blocks, and where you don’t do any operations on the array. The recurrence for np reflects how you cannot do the first operation (because then you’d divide it in the middle) but you can either do nothing or do the second operation.

#3

Thanks a lot for the help, I managed to AC