Russia joined APIO? -4 gold medals :(

I live in Asia, can I participate??

There will be 2 competition days(6 tasks) this year???Past APIOs only have one day and 3 tasks.

message from APIO 2014 host committee:

The practice session is online. Contest system address is https://82.200.146.22.

Your browser may complain about untrusted connection — this is ok.

Task statements for the practice session are provided via web interface. Tasks were taken from IZhO 2014 — the international contest that took place in Almaty, in January 2014 (http://izho.kz)

Practice session will be online until May 1. It's possible that we will have short downtimes, so don't worry if the website is not answering, just return in a few minutes.

Each contestant has limits similar to ones that will be used on the real contest:

Maximum number of submissions per task: 40.

Minimum interval between submissions for one task: 60 seconds.

Maximum number of user tests per task: 10.

Minimum interval between user tests for one task: 60 seconds.

however, I couldn't enter the practice session because I haven't received my username and password yet.

I tried to solve 2nd problem of APIO practice. (luxury-burrow)

I managed to get 56 points with O(N^2*M*log N*M) algorithm, but I can't get full score.

Can I get full score if I optimize the same algorithm? Or do I have to think up another one?

I think that the practice session could use more problems

The contest has finished in all the countries. Let's discuss the problems :-)

My solution:

A: Check whether all the substrings is palindrome. And calculate the rolling hash for substring [1,i].

With these datas, we can solve this problem with O(N^2 log N).(47 points)

And I heard that it's possible to get 100 points with SA+LCP, but I don't know details :-(

B: This problem is similar to 321E - Ciel and Gondolas.

So we can solve this problem with the same algorithm, but it's very difficult to avoid TLE and MLE.

I think getting 100 points is impossible...

C: This problem needs the correct observation. And with it, we have only to solve typical DP on tree.

I started imprementation with the wrong observation, so can't get any points :-(

(My score was 47-71-0)

When the results will be available?

Does anyone know, did anyone get full score? I mean 300 points

The contest has been finished.

let me discuss the solution of problems briefly:

palindrome:

first thing we need to support fast answering for this kind of queries:

given two numbers L and R you should tell how many times the substring str[L..R] occure is string str ( str is the input string)

this can be done in O(log n) per query using suffix tree or maybe something else.

second step is to search for palindromes in the string, we can do this by fixing the middle points then continue extending from left and right until the string is not palindrome anymore (note that the middle point of odd-length palindromes is a letter and for even length is between two letters) for example:

string: gabacaba

you want to search for palindromes that have the letter 'b' in index 2 to be the middle we start by 'b' obovouisly it's palindrome then 'aba' it is, then 'gabac' it isn't so we stop and continue the same thing with other middle points.

this is O(N^2) how can we do better?

instead of extending letter by letter we can use binary search and hashes to find the palindrome with maximal length in each middle point, but we have a problem , what if the optimial answer is a palindrome which isn't maximal length among palindromes with the same middle point?

actually , it's enough to check the maximal length palindrome for each middle point because the optimial choice is always a palindrome that is maximal length for some middle point because otherwise we can get a longer palindrome with the same number of occurrences.

time complexity O(N log N) which I think will get 100 points

‪sequence:

first observation that after we choose the K+1 parts it doesn't mattar the order of splitting it will give he same number of points , it's only mattar of choosing best K postion of splitting

I've noticed this during the contest but I had no idea about the proof.

this observation will lead immediately to very standard O(N^2 K) dynamic programming

dp[i][j] means the best points we can get after splitting i times (getting i+1 parts) with elements from 1 to j

let A be the partial sum of the input seqcence then the dynamic function is compute like this

dp[i][j]= max for all k<j (dp[i-1][k] + (A[j]-A[k])*A[k])

we can imporve the time complexity by using convex hull trick , this will make complexity O(NK) which is enough to get 100 points

if are familiar with convex hull trick you will find it easy how to apply it with this problem if you not you can read about it here

‪beads:

we can imagine the problem like that we have a tree each edge is red initially and we aslo have two types of nodes the first is red which is created by Append operation the second is blue which is created by Insert operation , blue nodes can change exactly two of adjencent edge to blue if this node is connected by at least one red node using those two blue edges.

this is solved by dynamic programming , first root the tree at some node then

dp[i][0] best solution for i'th node subtree and node i is red

dp[i][1] best solution for i'th node subtree and node i is blue and it changed two red child edges to blue (child edge is an edge leading to one of node i children)

dp[i][2] best solution for i'th node subtree and node i is blue and it changed the parent edge and one of red child edges (leading to a red child node) to blue

dp[i][3] best solution for i'th node subtree and node i is blue and it changed the parent edge and one of red child edges (leading to a blue child node) to blue (in this case the parent of node i must be red)

time complexity O(n)

those are my ideas I couldn't get 100 points for the first problem because I don't know how to build suffix tree in O(n)

and for second problem it seems my codes have bugs so I got 0 points for it :(

I got 100 point in A problem in 70 minutes after starting the competition.(SA+LCP+UnionFind) But I spend a lot of time at C problem ,and I couldn't get any point in C problem. My Score is 111 point(100+11+0).

Does anyone know when the results will be available?

I only got 73 points (23+50+0) I either don't know Manacher algo or how to build suffix tree (I couldn't get a solution just with SA) then I used map<string,int> and got 23pts! One participant near me used pascal and I watched him submitting again and again but always tle on subtask 2 , and only 8 pts...

I didn't know about convex hull trick before. After contest I read it but still can't find that equation of convex hull trick for problem B(( can anyone explain it or just give the equation. Thanks!!!

//82.200.146.22 i can still entire this site and still send a submission , why ?

I got 125 points(47+50+28).

O(N^2)(about 10^8) passed in A, O(KN^2)(about 2*10^8) passed in B, but O(N^2)(about 10^8) didn't pass.

What time complexity is expected in getting 57 points in C?

The APIO committee has a tough decision to make, should they give medals to the ones who scored 73 or not... I'm guessing that's why the results aren't ready yet (I say they should :D :D :D)

Sorry, where we can find results?

Contestants with 200 points and more — gold medals (15 contestants) Contestants with 122 points and more but less than 200 points — silver medals (33 contestants) Contestants with 73 points and more but less than 122 points — bronze medals (53 contestants)

results

When will test data come?

When will the tasks and the test datas be available?

For APIO Palindrome, there's a simple solution without palindrome tree or other complicated stuffs. First some things which are probably obvious:

1) Check if interval is palindromic. [rolling hash]

2) Find number of occurrences of substring in string [suffix array]

So now it reduces to finding all palindromic distinct substrings, then finding their occurences, and so on. Finding all palindromic substrings works like this: first fix the middle element(s) and then binary search how far out we can go whilst maintaining it as a palindrome. For instance, if we have aaabacac and fix the 'b', then we can expand out to length 3 (aba). If we fix the last a, we can expand out to cac. And so forth. So now we have a bunch of relatively long palindrome. But of course this does not comprise of all palindromes. To find all palindromes, we can compress our long palindromes by removing first & last characters. As we compress one by one, eventually, we will reach a palindrome we have already seen — we can stop there.

#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
#include <cmath>
#include <map>
#include <random>
#include <cassert>
#include <ctime>
#include <cstdlib>
#include <queue>
#include <limits.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
using namespace std;
 
int64_t binPow (int64_t x, int64_t y, int64_t MOD) {
    x %= MOD;
    int64_t res = x;
    int64_t ans = 1;
    while (y > 0) {
        if (y & 1) {
            ans *= res, ans %= MOD;
        }
        res *= res, res %= MOD;
        y /= 2;
    }
    return ans;
}
int64_t inv (int64_t x, int64_t MOD) {
    return binPow(x, MOD - 2, MOD);
}
vector<int64_t> powr = {1};
vector<int64_t> ipowr = {1};
struct Hasher {
    void resz (int mod, int base, string str) {
        int n = str.size();
        this->sz = n;
        this->MOD = mod, this->BASE = base;
        this->pref.assign(n + 1, 0);
        for (int i = 1; i <= n; i++) {
            pref[i] = (pref[i - 1] + (powr[n - i] * (str[i - 1] - 'a' + 1)) % MOD) % MOD;
            pref[i] %= MOD;
        }
    }
    int sz;
    int MOD;
    int BASE;
    vector<int64_t> pref;
    int64_t query (int l, int r) {
        if (l > sz || r > sz || l > r || l < 0 || r < 0) return -1;
        return (ipowr[sz - r - 1] * (pref[r + 1] - pref[l] + MOD) % MOD) % MOD;
    }
};
Hasher h1;
Hasher h2;
string s1;
bool isPalindrome (int l, int r) {
    if (l < 0 || r >= s1.length()) return false;
    return (h1.query(l, r) == h2.query((int)s1.length() - r - 1, (int)s1.length() - l - 1));
}
vector<int> suffix_array(string S) {
    int N = S.size();
    vector<int> sa(N), classes(N);
    for (int i = 0; i < N; i++) {
        sa[i] = N - 1 - i;
        classes[i] = S[i];
    }
    stable_sort(sa.begin(), sa.end(), [&S](int i, int j) {
        return S[i] < S[j];
    });
    for (int len = 1; len < N; len *= 2) {
        vector<int> c(classes);
        for (int i = 0; i < N; i++) {
            bool same = i && sa[i - 1] + len < N
                        && c[sa[i]] == c[sa[i - 1]]
                        && c[sa[i] + len / 2] == c[sa[i - 1] + len / 2];
            classes[sa[i]] = same ? classes[sa[i - 1]] : i;
        }
        vector<int> cnt(N), s(sa);
        for (int i = 0; i < N; i++)
            cnt[i] = i;
        for (int i = 0; i < N; i++) {
            int s1 = s[i] - len;
            if (s1 >= 0)
                sa[cnt[classes[s1]]++] = s1;
        }
    }
    return sa;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    while (powr.size() != 1e6 + 5) {
        powr.push_back(powr.back() * 31);
        powr.back() %= (int)1e9 + 9;
    }
    ipowr.resize(powr.size());
    ipowr[0] = 1; ipowr[1] = inv(powr[1], 1e9 + 9);
    for (int i = 2; i < powr.size(); i++) {
        ipowr[i] = (ipowr[i - 1] * ipowr[1]) % ((int)1e9 + 9);
    }
    cin >> s1;
    h1.resz((int)1e9 + 9, 31, s1);
    reverse(s1.begin(), s1.end());
    h2.resz((int)1e9 + 9, 31, s1);
    reverse(s1.begin(), s1.end());
    vector<pair<int,int>> vec;
    for (int i = 0;  i < s1.size(); i++) {
        int l = 0;
        int r = s1.length();
        while (l != r) {
            //cout << l << " " << r << '\n';
            int m = (l + r + 1)/2;
            if (isPalindrome(i - m, i + m)) {
                l = m;
            } else {
                r = m - 1;
            }
        }
        vec.emplace_back(i - l, i + l);
        //[...aa...]
        if (i == s1.length() || s1[i] != s1[i + 1]) {
            continue;
        }
        l = 0;
        r = s1.length();
        while (l != r) {
            int m = (l + r + 1)/2;
            if (isPalindrome(i - m, i + m + 1)) {
                l = m;
            } else {
                r = m - 1;
            }
        }
        vec.emplace_back(i - l, i + l + 1);
        //cout << i << " " << l << '\n';
    }
    map<int64_t,pair<int,int>> myMap;
    for (auto& p: vec) {
        pair<int,int> q = p;
        while (q.first <= q.second) {
            if (myMap.count(h1.query(q.first, q.second))) {
                break;
            }
            myMap[h1.query(q.first, q.second)] = q;
            q.first++, q.second--;
        }
    }
    vector<int> v = suffix_array(s1);
    vector<int> id(v.size() + 1);
    for (int i = 0; i < v.size(); i++) {
        id[v[i]] = i;
    }
    int64_t ans = 0;
    for (auto& p: myMap) {
        int tot = h1.query(p.second.first, p.second.second);
        int l = 0;
        int r = id[p.second.first];
        while (l != r) {
            int m = (l + r)/2;
            if (h1.query(v[m], v[m] + p.second.second - p.second.first) == tot) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        int L = l;
        l = id[p.second.first];
        r = s1.length() - 1;
        while (l != r) {
            int m = (l + r + 1)/2;
            if (h1.query(v[m], v[m] + p.second.second - p.second.first) == tot) {
                l = m;
            } else {
                r = m - 1;
            }
        }
        if (p.second.first - p.second.second == 2 && l - L + 1 == 10) {
            cout << p.second.first << " " << p.second.second << " " << l - L + 1 << '\n';
        }
        ans = max(ans, (int64_t)(p.second.second - p.second.first + 1) * (l - L + 1));
    }
    cout << ans;
}