Is it rated?

IMO pretests are sometimes too strong these days (especially with multitest), rendering hacking virtually impossible. I'd actually prefer to see a contest where it can pay off to search the room for hacks. As for now, sadly, this feature, once a funny part of Codeforces contests, is becoming less and less usable.

Knock knock modafaka

It is what it is.

Honestly, we intended to make a Div 1 + Div 2 round when we started, but we just had 2 problem ideas for the Div1 exclusive problems , which didn't seem to be interesting enough , hence we left the plan of combined round and rather focused on arranging a good Div-2 only round . We hope people find the current set of problems interesting .

Why is it bad?

Incredible Database XO

Thanks for the info. I should probably skip this contest or attempt A,B,C very cautiously. But I seriously hope they learnt their lesson and this time pretests are stronger.

Whelp, not hackforces this time

.

Hackforces eh m8?

Sorry to disappoint, we didn't have sufficient interesting ideas for Div 1 exclusive problems.

We have tried our best to make sure pretests are strong enough.

IIT Hyderabad may be the one, but just clarifying in case you are mistaken, we are IIIT Hyderabad.

As this is an Indian round, the correct way to say would be:
"OMG, i am afraid of giving this round now"

If contest is unrated you can't get any point/you can't rank up...

True

you are so lucky!

I am stuck in B but C was easier than I thought but I did terrible mistake beforehand.

Luckily I am out of competition so that my rating will not decrease.

I'm glad to know that there are at least 1525 math majors doing contest right now.

The logic is Hell Simple.

It might not have clicked to you, then.

But, yeah, the problem seems suitable for Div.2 C Problem.

In fact, many people were able to do "C" before "B".

Like how the hell does nationality come in? If it's a bad contest, it's a bad contest. A mathy one, then it's a mathy one. Blame the problem setters. Downvote the announcement. But why the hell are you pulling their nationality into the picture??

I don't see it bad IMO.

Could you explain your opinion?

I fell confident now (no offense) that I was able to do Problem C. Link : https://codeforces.net/contest/1316/submission/72456579

Observe that each term of the resultant polynomial is a sum of product of some terms taken from polynomial a and polynomial b, for ex — x^3 can be x^3.c or x^2.x.For the term to be divisible by p all the sums must be divisible by p. Find a term from x not divisible by p and same from y when you multiply them you get degree t(x)+t(y) and it is sure to be not divisible by p.

Transform each coefficient to $$$1$$$ if it is not divisible by p, and $$$0$$$ if it is. There will be $$$a_i$$$, $$$b_j$$$ such that $$$a_i = b_i = 1$$$. The answer is $$$i+j$$$.

Here is my solution : https://codeforces.net/contest/1316/submission/72456579 Find an element in A not divisible by p and same in B. Ans will be the sum of index of those elements.

smallest i such that ai%p!=0, smallest j such that bj%p!=0, answer is i+j.

gcd = 1 means they're all co-prime. But I didn't know how to use that to solve the problem.

Hint: gcd = 1 ensures that there is at least one coefficient not divisible by p in each polynomial

The question is based on Gauss Lemma for Polynomials. https://en.wikipedia.org/wiki/Gauss%27s_lemma_(polynomial) You need to find two numbers each from ai and bj such that ai%p!=0 and bj%p!=0, ans is i+j;

If you are having TLE then you might want to check if you are using fast IO method or not.

Thought process and proof of C :

think about how c[0], c[1], c[2]... these are formed, c[0] = a[0]*b[0], c[1] = a[0]*a[1] + b[0]*b[1], c[2] = a[0]*b[2] + a[1]*b[1] + a[2]*b[0] ... c[n] = a[0]*b[n] + a[1]*b[n-1] + a[2]*b[n-2]...+a[n-1]*b[1] + a[n]*b[0]. You need to find ct which is not divisible by p, means ct = p*x + y, where x can be any integer and y % p != 0. So we find the very first coeffcient of f(x) and g(x) that is not divisible by p, let's call them a[i] and b[j] respectively. We know a[1],a[2]...a[i-1] and b[1],b[2]...b[j-1] all are divisible by p. If I choose ct to be the coefficient of x^(i+j) then ct = a[0]*b[i+j] + a[1]*b[i+j-1] ... a[i+j]*b[0]. Here every term has some part of a[0] to a[i-1] or b[0] to b[j-1] except for exactly one term that is a[i]*b[j] and neither a[i] or b[j] is divisible by p. And as p is a prime number and we are just multiplicating two numbers a[i]*b[j], hence it is not divisible by p. So ct can be written as ct = p*x + y. So coefficient of x^(i+j) is indeed our answer.

GCD 1 makes it sure that at least one element is there which is not divisible by the given prime. So, the answer always exists.

your code has complexity n^3. You are running a loop of size n, then inside there is a call to the function that is running another loop of size n, and inside there is reverse function that itself is of O(n) complexity.

Please upload your video in higher quality, its max is 360p only.

sort the people by A in decreasing order dp(i, msk) = max try to take person i for each non taken position and iff (i — popcnt(msk)) < k then you can use him for support

What is the solution of C?

What did you googled?

T-shaped tetris is possible!! for example -
RDL
XUX
that was I missing.

For any {-1,-1}, it's enough to point it to a neighouring {-1,-1}. If there is none, no solution exists.

Unfortunately, I got TLE because of an extremely dumb mistake (re-initialising the NxN visit matrix every iteration...), but I think this should work.

$$$O(nlogn+p\times 2^{p}\times n)$$$ with SoS DP?

O(n * 2 ^ p * p) with standard dp

https://codeforces.net/blog/entry/74432?#comment-585757. No need of fft

probably because you are not using '+=' for the string concatenation

I also got a tle. Optimized a bit (still n^2) and pretests were passed. Don't know why?

Can you explain how did you solve E?

It's really hard to implement it precisely, even though the code "only" around 180 lines.

(well at least for me)

What is IRS?

Apparently finding all possible solutions and sorting them got past the pretests....... the hard part was finding the trick to find the solution without n^2. for me i just failed to realize that this solution wouldnt get tle..

For B, I think violence will time out, so I turned to finding the rule. After writing a few, I found that when I value K, the composition of strings after operation is like this. First, it is from a [k] to a [len]

Then judge whether the parity of K and Len is the same, and then continue from a [1] to a [k-1]

The difference is from a [k-1] to a [1]. I hope my approach can help you

You need to find a way to quicken the loop over reversing all substrings.

It is to rotate the whole string, and reverse the last k-1 chars if parity is odd. See solution codes https://codeforces.net/contest/1305/submission/72330015

No, it should not pass.

N is max bounded by 5000 . So max operations won't be 10^9