Why was B unusually hard for me?

What a fst round :(

Test case 73!

Video editorial for problem C: https://youtu.be/7uXOxPAej7Y

fstforces

Why downvoting? The problems were great and the editorial is clear. It just has weak pretest. Even so why not to downvote the announcement instead of editorial?

I know pretests of problem D were weak but otherwise it was a good contest. I don't think it's right to downvote it's editorial.

ch_egor, can you translate the name of the problem E to English in the bottom of the editorial? It is in Russian now.

FSTforces。:(

My answer to A is $$$\min(a-p\bmod a,b-p\bmod b,c-p\bmod c)$$$. Maybe the idea is easier?
UPD: You need to check that if $$$p\bmod a=0$$$ or $$$p\bmod b=0$$$ or $$$p\bmod c=0$$$.

Why for 0 1 0 in problem D answer will be No while 1,1 satisfy the given condition

Thanks for fast editorial and good problems.

my easy answer E

randomly select elements from arrays and test it is real.×100times

https://mirror.codeforces.com/contest/1492/submission/108293277

UDT this is very easy to hack, i tried some another way to pass, but maybe random can't

You wrote special case a = 0 for problem D in editorial but no pretests for this? Seems someone likes to see fst

CDE are nice, B is kinda "guess-by-sample" problem, and A just boring.

Great contest overall

The system tests of problem E are weak too. Some random solution like https://codeforces.ml/contest/1492/submission/108282677 can be hacked by this test case:

62500 4

1 1 1 1

1 1 1 1

1 1 1 1

...

2 2 2 2

Problems were really interesting and looks like pretest were really strong as many solution got failed during system testing. Superfast editorial as well .....

Although I didn't count how many people failed to pass the system test on some problem, I found that my rank changed from 1238 to 764.

This round was really Fst forces!

only if a+b-2==k testcases were included in pretests for D :()

Everyone's commenting "Fstforces". What does it mean?

Can anybody explains to me how B can be implemented in O(N)?

This gives me RE on pretest 5

FOR(i, m) {
		ll j = sp[t[i] - 'a'];
		to_which[i] = cp[t[i] - 'a'][j];
		while (i > 0 && to_which[i] < to_which[i - 1]) {
			to_which[i] = cp[t[i] - 'a'][++j];
		}
		sp[t[i] - 'a'] = to_which[i] + 1;
}

whereas this gets AC on pretest

FOR(i, m) {
		ll j = sp[t[i] - 'a'];
		assert(j < (ll)cp[t[i] - 'a'].size());
		to_which[i] = cp[t[i] - 'a'][j];
		while (i > 0 && to_which[i] < to_which[i - 1]) {
			++j;
			assert(j < (ll)cp[t[i] - 'a'].size());
			to_which[i] = cp[t[i] - 'a'][j];
		}
		sp[t[i] - 'a'] = j + 1;
}

I have changed only this much part of the code and nothing else. Someone please help me out in debugging the error.

UPD: I got the mistake I was doing. Thank you all.

Solve D in ten minute, WA after two hours.

in C

what if we just find the right dp array and iterate over s from left to right and keep updating our answer for each s[i], like:

ans=max(ans,max_possible_right_for[i+1]-current_t_i);

Editorial of E seems incomplete :(

[Deleted]

My performances during the contest

Quite awful. I opened the problem pages, after a couple of minutes, I finally see the statment of A, I think I spent little time solving it, but I forgot to save the code after I have a few changes, and I submit the code without realizing it. So I got a wrong attempt.

The following story is boring, until I try to solve D, at first I think there is only one way to make the answer have digit 1 ：1000-0001=0111. Obviously some cases were left behind, so I got WA on pretest #8. I suddenly find the problem, and I deside to recode — that is, to delate the original one and to solve the problem again from zero.

That is proved to be a bad idea, for the method when I recoded havn't been design carefully. So I finally WA in main test #64, and I didn't get in the first 1000.

But if I didn't recoded and chose to mend the code I write first, everything may be changed.

So I got a lesson after the contest: Think twice, code once.

Lots of contestants passed E with a random algorithm like 108293277. There is a hack test:

50000 5
1 1 1 2 2
1 1 2 2 1
1 2 1 1 2
1 2 1 2 1
1 2 2 1 1
2 1 1 1 2
2 1 1 2 1
2 1 2 1 1
2 2 1 1 1
rand() rand() 1 1 1
rand() rand() 1 1 1
...

The answer is 1 1 1 1 1 but if you randomly choose the answer from every sequence, the accuracy is $$$O(\frac{1}{n^2})$$$.

Really thank you for the GREAT pretests with Problem D.

Please make pretests STRONG next time.

FST Round The pretests of D are too weak :(

Let s be codeforcescontest704d and t be fst, the maximum width of p is 7 XD

Learning from Problem A especially for JAVA users :

i think my solution to the Problem A was correct,but my submission to it didn't pass the test cases. Could you pls hava look over over it and correct me if i am wrong and where did i go wrong???? https://mirror.codeforces.com/contest/1492/submission/108247518

How can I optimize my B solution? My solution
Any help would be appreciated.

For problem A, this was my following code:

from math import ceil
for _ in range(int(input())):

    p,a,b,c = map(int,input().split())
    print(min(ceil(p/a)*a,ceil(p/b)*b,ceil(p/c)*c)-p)

It is giving me WA on pretest 2. What am I missing?

Alternative solution for 1492E - Almost Fault-Tolerant Database is following: find any two vertices of diameter, then try all 2^(diffs) variants. Is it wrong? Can someone prove it or hack it? 108299916

tests are wonderful!!!!

Can somebody please tell why my solution for C failed .. - I have calculated max, min possible indexes for each t[i] keeping my mind p1<p2<p3 .. - where max of every index is smaller than max of i+1 - and min of i is greater than min of i-1. - and calculating the ans as the max of (max[i+1]-min[i]) for valid indexes. - and if we get answer from certain i, we can use max of each indexes >i+1 so that given condition is verified. Here is my submission: https://mirror.codeforces.com/contest/1492/submission/108280740

upd: got AC now :)

When Problem D is doable in O(n), why restrict the limits to $$$2\times 10^5$$$? The editorial doesn't even mention DP or any alternative solution that only works below $$$2\times 10^5$$$.

Я отправлял такое же решение в A, но оно не проходило 2 претест. Что я делал не так?

import math
 
for i in range(int(input())):
	p, a, b, c = map(int, input().split())
	a = math.ceil(p / a) * a
	b = math.ceil(p / b) * b
	c = math.ceil(p / c) * c
	
	print(min(a - p, b - p, c  - p))

Codeforces Round #704 (X)

Hackforces & FSTforces Round #704 (O)

why am I getting runtime error in this soln

E is such a nice problem.

Good questions and fast editorial.

Personally, leaving some unexpected spaces for hacks is ok.

But it seems like this contest is another lesson for the authors that it's important to keep an eye on the chances for using randoming algorithms (or other tricks like brute force + #pragma)to pass the tests...

How to solve problem E's bonus 2? I can only come up with $$$O(nm+k^kn)$$$.

Simple solution for D:

Make x as a zeroes and b ones

Make r as k ones and max(a-k, 0) zeroes

Then if x-r >=0 and x-r contains a zeroes and b ones we found answer, otherwise no solution

108313076

Bonus1 seems to be the same as the original task.

In Bonus2, intuitively split nm into 2 cases , where n <= 500 or m <= 500 , to reach the sqrt time complexity.... But have no idea how to keep on :(

Hope to get some hints.

Doubt in problem E editorial :

We can ignore each other array that differ with the first array in no more than 2 positions

Take following input : n=3 m=3 , 1 2 3 , 4 5 6 , 3 3 7

We can see that 3 5 3 will work .

Now if input was : n=4 m=3 , 1 2 3 , 4 5 6 , 3 3 7 , 1 3 7

Then according to editorial 3 5 3 should work as answer because we ignore the 4th array . But then 3 5 3 differs from fourth array at 3 positions.

can anybody tell me why am i getting WA after using same logic for question : https://mirror.codeforces.com/contest/1492/problem/C my solution : https://mirror.codeforces.com/contest/1492/submission/108314097

test case 64!

Why are some editorials in english and some in russian?

some people have used randomized solution for problem E . Could someone please explain how to solve problem E using that.

Can someone explain how to approach the problem B if we have random numbers in the array. If we have test cases of random numbers like [9,10,1] then the greedy logic fails

Thanks in Advance.

I cannot understand why my submission for C got the wrong answer on Pretest 5.Can anyone please provide me a simple test case (for which my program will fail) so that I can understand my error.

Here is my submission : C.Maximum Width

Hi, for problem E, can anyone explain a little bit what does the variable cnt mean in the dfs() function of this submission?

https://mirror.codeforces.com/contest/1492/submission/108321457

Thanks for help.

In the editorial of problem C, I think the answer should be $$$\max_{i=1}^{i=m-1}\textit{right}_{i+1}-\textit{left}_{i}$$$ ($$$n$$$ is replaced by $$$m$$$.)

Problem C, 108446832 is getting WA on test 7. Can anyone provide a testcase?

Hello, can someone please explain how the solution to E is not 6^2 * (n*m) ^ 2? The way I understand it is like this: We go trough the list o(n * m), for every single guy, if he has more than 2 differences we go into the maximum of 6 ways of completing him (so times 6). For every one of those n * m * 6, we go trough the list a maximum of one more time, to look for another array that has a difference of more than 2 with our current solution array. So n*m*6*n*m. o((n * m) ^ 2 * 6) so far. Now once we find one we have a maximum of 6 ways to change our solution array so o((n * m) ^ 2 * 6 ^ 2) is our final complexity. Where am I misunderstanding?

Мне понравилось, топчик.

I am unable to find out what wrong am I doing here: https://mirror.codeforces.com/contest/1492/submission/108491871

Can someone explain the recursive backtracking solution for Problem E?

Can somebody help me why I am getting Time Limit Exceeded Error https://mirror.codeforces.com/contest/1492/submission/108665110

Can somebody point out the mistake in my solution to the problem C? Here's my solution: https://pastebin.com/yE5tDG5s

Why am I getting WA on test 5 — 141222690 :(

even full test cases of D are extremely weak for example this sub-optimal solution almost passed in fact it failed in the very last test 93rd test is the final one which I saw in my AC solution ,also there can be numerous counter easily makable tests