Can anyone give tests data or some discription?


Edited by author 01.11.2023 14:24

1000000000 1000000000 300
answer: 97395891

7 8
1 2
1 3
1 4
5 6
6 7
7 8
7 5

Hello,
I am trying this question, however, I am unable to understand how to construct the solution. My Dp is weak so I thought to practice here, however I am having a tough time.
Can someone please help in describing how to start thinking about such problems?

we have 12 hours on clocks

If you have WA10, make sure you don't have 'I' as a card value instead of 'T'. For some reason it was very easy for me to mix these letters in the statement...

u can search for intersections instead of looking for cutouts, just invert the segments of the second function
use min max instead of a lot of conditions and you get a very simple code :)

My idea is to reverse the operations of adding characters and doubling a string. I have an iterative algorithm in O(n * log(n)). At each iteration, I count dp - the length of the maximum substring ending with index i, obtained by the doubling operation. Then I look for the maximum among the maximum substrings and truncate the current string to leave this substring. But this is a greedy solution. Is it possible to come up with a counterexample to it?

admins, could you pls fix this?

My first attempt use string hashing to check the palindrome with Segment Tree lazy prop.
O(Q*K*logK*logN), esp. for the update query and it's TLE 11

However, using Manacher algorithm with Segment Tree you can achieve O(Q*(K+lgN))

Little help:
- WA#3 : You're likely answering too much. (K involved)
- WA#9 : N=10^5, overflow somewhere

Help!
What is wrong?


[code deleted]

Edited by moderator 05.11.2023 02:38

var N: integer;
begin
readln(n);
if (abs(n)>10000) then writeln('Îøèáêà ââîäà') else
if N>=0 then writeln(((1+n)*n)/2)
else writeln(((1+n)*(abs(n)+2))/2);
end.

var
  a: integer;
  b: real;

begin
  readln(a);
  if (abs(a) < 10001) then
  begin
    if (a < 0) then
      b := (a + 1) * (-a + 2) / 2
    else b := 0;
    if (a > 0) then
      b := (a + 1) * a / 2 else
    if (a < 0) then
      b := (a + 1) * (-a + 2) / 2
    else b := 1;
    writeln(b);
  end;
end.

Read article: convex hull of n*(n-1)/2 intersection points of n lines

Implementation is very easy.
But the proof is cool to read.

spell the months correctly

try kookko
ans: kook

#include <iostream>
#include <limits>
#include <cmath>

bool isPrime(int n) {
    if (n <= 1) {
        return false;
    }

    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            return false;
        }
    }

    return true;
}

int lowest_trivia_number (int I, int J) {
    double min_trivia = std::numeric_limits<double>::max();
    int res = 0;
    for (int i = I; i <= J; i++) {
        int sum_of_own_denominators = 1;
        for(int j = 2; j <= std::sqrt(i); j++){
            if(i % j == 0) {
                sum_of_own_denominators += j;
                if(j != i / j) {
                    sum_of_own_denominators += i / j;
                }
            }
        }

        double cur_trivia = sum_of_own_denominators/i;
        if (cur_trivia < min_trivia) {
            min_trivia = cur_trivia;
            res = i;
        }
    }
    return res;
}

int main() {
    int I, J;

    std::cin >> I >> J;
    if(I == 1) {
        std::cout << 1;
        return 0;
    }

    int largestPrime = -1;

    for (int num = J; num >= I; num--) {
        if (isPrime(num)) {
            largestPrime = num;
            break;
        }
    }

    if (largestPrime != -1) {
        std::cout << largestPrime << std::endl;
    } else {
        std::cout << lowest_trivia_number(I, J);
    }

    return 0;
}

Although can be solved in O(N^3)
Here's the interesting paper: Optimal Area Triangulation
https://core.ac.uk/download/pdf/226134402.pdf
(haven't read yet)

Hint: Also include O(N^3) solution

I precalculated digits for segment from 1e5 to 2e5, then i computed all digits from 1 to 1e5(if n >= 1e5), then i stepped from 1e5 to n with step size = 1e5. And after all this I computed digits from last step to n. It does about 1e9/1e5 steps and works 0.015 sec.

I think that it's dumb solution, so I want to know, how to solve this task in O(log10(n)) or smth similar.

I wrote two programs, one AC, one WA.
I run these two programs for many times but they always make
the same answer.
Is it strange?