Ibrahim-Elsayed's blog

By Ibrahim-Elsayed, history, 3 years ago, In English

i recently solved this problem: https://mirror.codeforces.com/contest/1097/problem/B,

I know that it's an easy problem with a brute-force solution but, I'm curious how to solve it for $$${1 <= N <= 10^5}$$$, I'd appreciate your help, thanks in advance.

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

| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It's actually possible using dynamic programming, where the state is number of turns used and the degree of the pointer:

// Problem: B. Petr and a Combination Lock
// Contest: Codeforces - Hello 2019
// URL: https://mirror.codeforces.com/contest/1097/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

bool dp[15][360];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    cin >> n;
    vector<int> vect(n);
    for (int i = 0; i < n; ++i) {
        cin >> vect[i];
    }

    for (int i = 0; i < n; ++i) {
        if (i == 0) {
            dp[0][vect[i]] = 1;
            dp[0][(360 - vect[i]) % 360] = 1;
        } else {
            for (int j = 0; j < 360; ++j) {
                if (dp[i - 1][j]) {
                    dp[i][(j + vect[i]) % 360] = 1;
                    dp[i][(j - vect[i] + 360) % 360] = 1;
                }
            }
        }
    }

    cout << (dp[n - 1][0] ? "YES\n" : "NO\n");
}

See more about dp here.