Lemur95's blog

By Lemur95, history, 5 months ago, In English

Hello CF community,

I was solving problem 3 (Balancing Tree) from last USACO round, when I encountered some sussy behaviour. I submited my code, which in local testing passed both the examples, but upon grading, it passed only 1, the other one being WA. I have locally tested another subtask, with the same result (local testing led to a good result, but WA on grading).

Here is the code and here is the problem link. Hope I was clear enough with my issue and thanks in advance!

Have a good day!

Read more »

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

By Lemur95, history, 10 months ago, In English

Hello CF community,

I just stumbled upon this weird (at least for me) behaviour. I was trying to solve 1605C - Dominant Character, I set the compiler to C++ 20 and sent this code 135233345 but got C.E. for whatever reason. Then I thought of switching back to C++ 17 and this time I got accepted 135233454 (Note that it is the same code).

Can someone tell me why this is happening?

Read more »

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

By Lemur95, history, 2 years ago, In English

Hello again Codeforces community!

I'm back with another problem, which I'm not able to solve. I don't have any link, it isn't from any site.

You are given a permutation of size N and Q queries. In 1 query, you are given x and y, and you need to swap the values on position x and y (formally, you need to swap v[x] and v[y]). After every query, you have to print the number of prefixes of the permutation, that are permutations.

For example, if you have array A = [2, 1, 3, 4], the answer is 3 (permutation at index 2, 3 and 4).

Example:

Input:
4 3
1 4 3 2
2 3
2 4 1 2

Output:

2 3 2

1 <= N, Q <= 100000.

The only approach I could come up with was brute force. Could anyone help me?

Read more »

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

By Lemur95, history, 3 years ago, In English

Hi Codeforces Community! I have been struggling with a problem that I find quite hard. Unfortunately, I don't have a link to the English version. I will try to make a short description of it.

You have 2 strings A and B, of length N and M. The strings contain only lowercase Latin letters. For every substring S of B, you have to find the length of the longest common prefix of A and S. Print the sum of these lengths.

1 <= N, M <= 2 000 000
Time Limit: 1.5 seconds
Memory Limit: 32768 kbytes

Examples:

If A = aa, B = abaa, then the answer is 8. If A = aab, B = acaabada, then the answer is 32.

I tried an approach with hashes and binary searching, but I got TLE. Is there any faster way to solve this problem? Thanks in advance.

P.S.: I will explain my approach, if needed.

Hope you'll have a great day, Protroll

Read more »

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