Oct 2023
1 / 6
Oct 2023
Nov 2023
jhonspapa_2
Oct '23

I’ve been struggling with the JUSTAPAL task for a long time.
and I can’t understand where in my code there is an error. The answer on the base sample is correct but I get WA. My code is below

#include<cstdio>
#include<algorithm>
#include <cmath>
#include <cstring>

using namespace std;
#define maxn 1100000
#define h1 107 char s [maxn]:
unsigned long long h[maxn];
unsigned long long h2[maxn];
unsigned long long H[maxn];
int n;
char s[maxn];
#define h1 107

int id(int i) {
    int idx = s[i] - 'a';
    if (s[i] >= 'A' && s[i] <= 'Z') idx = s[i] - 'A' + 26;
    return idx;
}

int solve(int p1, int p2) {
    if (p1 < 1 || p2 > n) return 0;
    int l = 0, r = min(p1, n - p2 + 1);
    while (l != r) {
        int mid = (l + r + 1) >> 1;
        if (h[p1] - h[p1 - mid] * H[mid] == h2[p2] - h2[p2 + mid] * H[mid]) l = mid;
        else r = mid - 1;
    }
    return r;
}
int pre[55], suf[55];
int main() {
    int t;
    scanf("%d", &t);
    H[0] = 1;
    for (int i = 1; i <= 1100000; i++) H[i] = H[i - 1] * h1;
    while (t--) {
        scanf("%s", s + 1);
        s[0] = 'a';
        n = strlen(s) - 1;
        h[0] = 0; h2[n + 1] = 0;
        for (int i = 0; i < 55; i++) {
            pre[i] = n + 1; suf[i] = 0;
        }
        for (int i = 1; i <= n; i++) {
            int idx = id(i);
            h[i] = h[i - 1] * h1 + idx;
            pre[idx] = min(pre[idx], i);
            suf[idx] = max(suf[idx], i);
        }
        for (int i = n; i >= 1; i--) {
            int idx = id(i);
            h2[i] = h2[i + 1] * h1 + idx;
        }
        int ans = 0;
        for (int i = 1; i <= n; i++)
            for (int j = i; j <= i + 1; j++) {
                if (j > n) continue;
                int len1 = solve(i, j);
                ans = max(ans, len1 * 2 - 1 + (j - i));
                if (i - len1 >= 1 && j + len1 <= n) {
                    int p1 = i - len1, p2 = j + len1;
                    int len2 = solve(p1 - 1, p2 + 1);
                    int id1 = id(p1), id2 = id(p2);
                    int mins = min(pre[id1], pre[id2]);
                    int maxs = max(suf[id1], suf[id2]);
                    if (mins < p1) {
                        int len3 = i - max(mins + 1, i - len1 - len2) + 1;
                        ans = max(ans, len3 * 2 - 1 + (j - i));
                    }
                    if (maxs > p2) {
                        int len3 = min(maxs - 1, j + len1 + len2) - j + 1;
                        ans = max(ans, len3 * 2 - 1 + (j - i));
                    }
                    int p3 = p1 - 1 - len2, p4 = p2 + 1 + len2;
                    if (p3 >= 1 && p4 <= n)
                        if ((id(p1) == id(p3) && id(p2) == id(p4)) || (id(p1) == id(p4) && id(p2) == id(p3))) {
                            int len3 = solve(p3 - 1, p4 + 1);
                            ans = max(ans, (len1 + len2) * 2 - 1 + 4 + (j - i) + 2 * len3);
                        }
                    if (j == i && (s[i] == s[p1] || s[i] == s[p2])) {
                        ans = max(ans, (len1 + len2) * 2 - 1 + 2);
                    }
                }
            }
        printf("%d\n", ans);

    }
    return 0;
}

  • created

    Oct '23

  • last reply

    Nov '23
  • 5

    replies

  • 532

    views

  • 4

    users

  • 2

    likes

15 days later
defrager
Nov '23

General tip: If you have WA and can’t find case where solution is wrong, just create another slow but correct solution and test them both against all possible strings.

Here checker I used:

string s;
int maxPalSlow() {
  int ans = 1;
  for (int i = 0; i < s.size(); i++) {
    int l = i;
    int r = i;
    while (l > 0 && r + 1 < s.size() && s[l - 1] == s[r + 1]) {
      l--;
      r++;
      ans = max(ans, r - l + 1);
    }
    if (i + 1 < s.size() && s[i + 1] == s[i]) {
      int l = i;
      int r = i + 1;
      ans = max(ans, 2);
      while (l > 0 && r + 1 < s.size() && s[l - 1] == s[r + 1]) {
        l--;
        r++;
        ans = max(ans, r - l + 1);
      }
    }
  }
  return ans;
}

int solveSlow() {
  int ans = 0;
  for (int i = 0; i < s.size(); i++) {
    for (int j = 0; j <= s.size(); j++) {
      swap(s[i], s[j]);
      ans = max(ans, maxPalSlow());
      swap(s[i], s[j]);
    }
  }
  return ans;
}

void CheckAll(int pos) {
  if (pos > 0) {
    int res = solveFast();
    int res2 = solveSlow();
    if (res != res2) {
      cout << s << endl;
      cout << res << " want: " << res2 << endl;
      assert(false);
    }
  }
  if (pos == 10) {
    return;
  }
  for (char i = 'A'; i <= 'D'; i++) {
    s = s + i;
    CheckAll(pos + 1);
    s.pop_back();
  }
}

That checks all possible strings with letters {A,B,C,D} with all possible lengths from 1 to 10. if your solution answers correctly to all of them your solution has high chance to be correct.

lightbizz
Nov '23

Hello. this is out of topic but can i ask some question about POCALC2 problem ? . it is an assigment for my uni :sob: , but i can not get it correct. My approach is to convert all number including decimal to fractions then do the operation. But i’m still getting wrong answer. i think i’m converting decimal to fraction in wrong way. Do you have some test case that i can match the output or sort of checker ? Thank you

simes
Nov '23

Then why not create your own topic in a new post?

lightbizz
Nov '23

i want to but sadly i can’t. there is a chance my professor will see my post. he is quite active in here

simes
Nov '23

How will he know it’s you? if he knows your username, create another