oj.uz

Submission #243450

# Submission time Handle Problem Language Result Execution time Memory
243450 2020-07-01T08:03:08 Z dolphingarlic Necklace (Subtask 1-3) (BOI19_necklace1) C++14
85 / 85
 279 ms 106264 KB 
/*
Baltic 2019 Necklace
- Firstly, assume WLOG that we can't flip the necklace.
    - If we do flip it in the optimal solution, just reverse B and run the
      same solution again
- Notice how we'll have A = ...XY... and B = ...YX... where X and Y are substrings
- lcs[i][j] = Longest common suffix of A[:i] and B[:j]
            = lcs[i - 1][j - 1] + 1 if A[i] == B[j] else 0
- dp1[i][j] = Longest suffix of A[:i] that's also a prefix of B[j:]
    - First, dp1[i][j - lcs[i][j]] = max(dp1[i][j - lcs[i][j]], lcs[i][j])
    - Next, dp1[i][j] = max(dp1[i][j], dp1[i][j - 1] - 1)
- dp2[i][j] = Longest prefix of A[i:] that's also a suffix of B[:j]
    - We compute this similarly
- To get this down to O(N) memory, notice how dp[i] only depends on lcs[i]
  and lcs[i] only depends on lcs[i - 1]
- Complexity: O(N^2) with O(N) memory
*/

#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

int lcs[3001][3001], dp1[3001][3001], dp2[3001][3001];
int mx_len, best_i, best_j;

void solve(string A, string B, bool reversed) {
    memset(lcs, 0, sizeof lcs);
    memset(dp1, 0, sizeof dp1);
    memset(dp2, 0, sizeof dp2);
    FOR(i, 1, A.size() - 1) {
        FOR(j, 1, B.size() - 1) {
            lcs[i][j] = (A[i] == B[j] ? lcs[i - 1][j - 1] + 1 : 0);
            dp1[i][j - lcs[i][j]] = max(dp1[i][j - lcs[i][j]], lcs[i][j]);
            dp2[i - lcs[i][j]][j] = max(dp2[i - lcs[i][j]][j], lcs[i][j]);
        }
    }
    FOR(i, 1, A.size() - 1) {
        FOR(j, 1, B.size() - 1) {
            dp1[i][j] = max(dp1[i][j], dp1[i][j - 1] - 1);
            dp2[i][j] = max(dp2[i][j], dp2[i - 1][j] - 1);

            if (dp1[i][j] + dp2[i][j] > mx_len) {
                mx_len = dp1[i][j] + dp2[i][j];
                best_i = i - dp1[i][j];
                if (!reversed) best_j = j - dp2[i][j];
                else best_j = B.size() - j - dp1[i][j] - 2;
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    string A, B;
    cin >> A >> B;
    A = "." + A + ".", B = "." + B + ".";
    solve(A, B, 0);
    reverse(B.begin(), B.end());
    solve(A, B, 1);
    cout << mx_len << '\n' << best_i << ' ' << best_j;
    return 0;
}

Compilation message

necklace.cpp: In function 'void solve(std::__cxx11::string, std::__cxx11::string, bool)':
necklace.cpp:20:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, x, y) for (int i = x; i < y; i++)
necklace.cpp:31:9:
     FOR(i, 1, A.size() - 1) {
         ~~~~~~~~~~~~~~~~~~              
necklace.cpp:31:5: note: in expansion of macro 'FOR'
     FOR(i, 1, A.size() - 1) {
     ^~~
necklace.cpp:20:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, x, y) for (int i = x; i < y; i++)
necklace.cpp:32:13:
         FOR(j, 1, B.size() - 1) {
             ~~~~~~~~~~~~~~~~~~          
necklace.cpp:32:9: note: in expansion of macro 'FOR'
         FOR(j, 1, B.size() - 1) {
         ^~~
necklace.cpp:20:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, x, y) for (int i = x; i < y; i++)
necklace.cpp:38:9:
     FOR(i, 1, A.size() - 1) {
         ~~~~~~~~~~~~~~~~~~              
necklace.cpp:38:5: note: in expansion of macro 'FOR'
     FOR(i, 1, A.size() - 1) {
     ^~~
necklace.cpp:20:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i, x, y) for (int i = x; i < y; i++)
necklace.cpp:39:13:
         FOR(j, 1, B.size() - 1) {
             ~~~~~~~~~~~~~~~~~~          
necklace.cpp:39:9: note: in expansion of macro 'FOR'
         FOR(j, 1, B.size() - 1) {
         ^~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 106104 KB Output is correct
2 Correct 80 ms 106112 KB Output is correct
3 Correct 77 ms 106104 KB Output is correct
4 Correct 72 ms 106104 KB Output is correct
5 Correct 83 ms 106108 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 106104 KB Output is correct
2 Correct 80 ms 106112 KB Output is correct
3 Correct 77 ms 106104 KB Output is correct
4 Correct 72 ms 106104 KB Output is correct
5 Correct 83 ms 106108 KB Output is correct
6 Correct 82 ms 106104 KB Output is correct
7 Correct 75 ms 106104 KB Output is correct
8 Correct 73 ms 106104 KB Output is correct
9 Correct 74 ms 106104 KB Output is correct
10 Correct 84 ms 106232 KB Output is correct
11 Correct 76 ms 106104 KB Output is correct
12 Correct 77 ms 106056 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 106104 KB Output is correct
2 Correct 80 ms 106112 KB Output is correct
3 Correct 77 ms 106104 KB Output is correct
4 Correct 72 ms 106104 KB Output is correct
5 Correct 83 ms 106108 KB Output is correct
6 Correct 82 ms 106104 KB Output is correct
7 Correct 75 ms 106104 KB Output is correct
8 Correct 73 ms 106104 KB Output is correct
9 Correct 74 ms 106104 KB Output is correct
10 Correct 84 ms 106232 KB Output is correct
11 Correct 76 ms 106104 KB Output is correct
12 Correct 77 ms 106056 KB Output is correct
13 Correct 252 ms 106104 KB Output is correct
14 Correct 224 ms 106232 KB Output is correct
15 Correct 279 ms 106104 KB Output is correct
16 Correct 230 ms 106104 KB Output is correct
17 Correct 202 ms 106264 KB Output is correct
18 Correct 206 ms 106232 KB Output is correct
19 Correct 235 ms 106104 KB Output is correct
20 Correct 251 ms 106120 KB Output is correct
21 Correct 251 ms 106232 KB Output is correct