Dunno about you all but this is imo very confusing descrption:

Why use words sequentially? Why use "strictly after". If there werre not example input/output I would think that you have to find years p, p+1, p+2, ..., p+n such that first sign happens on p, second sign happens on p+1 and so on.

I've got no idea why my code for D doesnt pass the official test.

It says that it expects output '12' (instead of '11) on test number 2.

But when I run this test locally I get result '12' :O

Maybe it's possible to kinda optimise number of edges in some way.

Eg. have a quick way of checking whether an edge even makes sens (ie. no point for this edge to exist because going through some circle first will always be better).

interesting indeed

dijkstra comes to mind, but it's too slow right

I'm not sure whether I understand your code correctly, but I think that in a scenario where res is not 0, you have to move 2 guys to next level, but you're moving only one

Thanks, I was thinking about a wrong problem -.-

I thought that the labels of participants can be permutated (ie. 1 doesn't have to play 2 at the beginning)

but how

you're right, nice I didn't understand the code (didn't have time to in the morning).

however what I usually do is calculate all inversions independently — this can also be done in linear time

This is good but you can count inversions in linear time instead of nlogn

I think I'm missing something, either way you have to multiply each one of them

why would that be smarter

no no no

You don't calculate newtons binomial like that :)

you dont divide by n!, you multiply by inversions of every number between [2 ... n], so

inv(2) * inv(3) * ... * inv(n) (of course keeping everything in check using modulo)

I'm on mobile. Ill answer tomorrow if nobody else explaons

C needs more explanation. It s not obvious that pitting all opening brackets before closing ones gives us best chances of forming rbs.

Dont misunderstand me, i know how to prove it now.

I like both, when it comes to the old ones I would definitely add berserk. (but berserk manga is so good that it's hard to fck up, though possible :))

Anybody knows the solution for B if all ai were to be distinct between one another?

(meaning that for any l <= i, j <= r and i != j: ai != aj)

Dang really nice solution.

Hmm maybe it would be easier just binsearching min and max for each segment :D?

Hmm, D doesn't budge for me :D.

Any tips? Only thing I've realized is that we always know where 1 is but other than that it may depend :<

Hmm probably depends on what kind of integers and what kind of doubles we're talking about right?

Because double has gaps between very big integers and for sufficiently big integers we could probably use that.

put it in spoiler

His/her brute force will catch it though :)

Yea should pass, why not

div2C is you either guess solution or you don't

turns out the letter that occurs odd number of times (over all t's) is the solution.

For rows:

store in set every value that is not covered by any rook.

initially this set is obv full.

to know whether there exists a row between x1 and x2 that is not covered you make use of set.lower_bound()

if lower_bound(x1) is set.end() or its value is > x2 then all cells between x1 and x2 must be covered

same for columns

It can be solved with c++ set

Put it in spoiler and don't spam?

I've done this problem the same way as you (logic wise). You can look at my submission.

However, I used C++'s set and its 'lower_bound' function. I guess you can find something similar in python :)

Maybe there is even some simpler way to solve it but I can't think of anything.

I mean you have those two loops in your code:

for i in range (q):
  for i in range (a[1], a[3]+1):

Aren't you iterating over rows and columns for each query though?

Which tasks required segment trees? I only looked at A, B, C and D and none of them required it (or anything similar like Fenwick)

I would argue that 'cost of removal' is pretty ambiguous in C.

I myself understood it as a cost of single move — mainly because plural form 'removals' was used in previous sentence.

But I think that task descriptions were fine.

6 101000

and

4 1011

Dang, that problem B though :P

I think it should be swapped with C (looking at point distribtuion)?

yes, E, my bad :)

In E we can choose any vertex to be root, right? And max xor will always be n, where n is number of vertices?

Dang, I think I was really close to solving E for the first time. It's a pity I now have to wait for system test to end in order to test my solution :(

Maaaaaaaaybe, but contests this year were all reaaally good so that woudln't be anything bad.

Problem A was too hard — that's for sure.

Problem B was kinda boring, but implementation heavy and bug prone (at least in my case).

Problem C was really nice though.

Problem D was nice as well.

Not sure about rest as I didn't read them.

I had such a hard time solving A. Hopefully my last submition goes through system testing XD

nice observation, but solving B in a straighforward way is implementation heavy

DANGGGGGGGGGGGGG, I didn't think of using anything smaller than 2x2. Thanks.

How to solve C -.-?

no more than one means either 0 or 1

it was written in bold so problem writers cannot be blamed for it :D

It won't work

Edit:

Actually I don't know.

Edit2:

I've coded it — it doesnt find the minimal value correctly.

Would this idea work for D?

Maybe it's not hard actually.

Like I don't know, I guess once you see similar problem you're going to link it to inversions pretty fast.

But maybe if you've never seen anything similar (both in cs and math) then it might be hard, I agree.

I mean with the operation given in task you never change parity of inversions.

So if initially parity of inversions is odd it will never be even and the other way around.

So I guess linking the task to inversions is fairly forcing.

What's hard is 'proving' that from every odd state you can reach every other 'odd' state.

it's pretty standard tbh

Lol nice one :D

It's not only about counting inversions — if there are two values that are the same then you don't have to care about parity of inversions.

But here is my code if you want it: https://atcoder.jp/contests/arc136/submissions/29743627

ah didn't know — but still it's not needed

Or is my solution wrong? (it got AC)

B can be solved in O(n^2) time (when counting inversions).

If we had to use some kind of tree (eg. Fenwick) to get nlogn it would have been way harder.

which n gives the highest chances for hacking? :D

Yes.

What is the number of possible distinct colorings if you know grid is n x m, there are k colors and you know that q coloring operations were performed (but you don't know anything about those operations).

But I couldn't really figure it out.

Version in which no coordinates are given.

Just n, m, q and k in input, nothing more.

A — D, were great (didn't read E or F yet).

It's a pity I didn't read D thoroughly and was thinking about a way harder problem (one in which we're not given coordinates of operations — just q)

Yea, going to be speedforces for me unless I get enlightened by algod.

Problemset was godlike, only problem that wasn't that good was D, because it was heavy implementation based.

But other problems? Really nice.

(look at my submission history :P)

Replace endl with "\n"

But after its increased to 1000, someones gonna say why not increase it to 2000 and so on

Tbh it gives those t-shirts some prestige right?

The only real programming problems (E and F) turned out to be too hard for me :/

In E I guess that if one array has more than one occurence of certain number we can put half of them in L and other half of them in R, right?

Problem A was great imo :)

This is the moment our future is going to be decided.

We either dominate those ridiculous bots or they're going dominate us in the future.
I need one hundred percent effort from each one of you participating.
We need to freaking crush them once and for all.

Everybody focus this round — this time it's not about rating, it's about something bigger.

Good luck humans

I might be misunderstanding something but as far as I understand as long as gcd > l — r + 1 we increase our r.

The moment gcd becomes smaller than l — r + 1, we have to build new gcd and we do that by going back from r. Now if we manage to find a bad segment this way then everything is fine as we'll be able to move our l pointer to r + 1.

But what if we only find segment [new_l, r] such that l < new_l < r and

gcd(new_l,...,r) > r — new_l + 1

and

gcd(new_l — 1, ..., r) < r — new_l + 2

Then we have to continue analyzing from l = new_l and r = r + 1

yes, but what about case where we don't find any bad segments in go back step? Then we cannot move our left pointer entirely to the right.

I've solved it exactly this way during contest, however I was sure it was O(n^2).

Seems like the proof has a lot to do with the fact that when we go back gcd can decrease up to log times.

Maybe if I get some time, I'll try to prove it

:(

Is this even possible to create a solution for D that exceeds time limit?

I have no idea why my solution to B passed pretests :OO

This is a correct logic as far as I understand it.

If tree is a line then you simply assign 2, 5, 2, 5 ...

If it's not a line it's impossible.

Okay, I overestimated your solution. To make up for my mistake here is a test where your solution is failing :).

1 1 10 abcxcdxdcx abcdcdcdcd

No, this is correct, you must have made a mistake somwhere.

I've done something very similar and it fails only on big tests (tle).

I have idea :)

Actually my solution to that problems is O(n * m * n). Does anybody know how to solve this variant in better time?

Can be also solved greedily.

Count occurences of letters in original string and count number of singles and doubles.

(doubles — how many pairs of letters there are, singles — number of letters minus doubles * 2).

Knowing singles and doubles values you can calculate solution.

DAAAMN, I had so much fun solving E (although I didn't quite finish it).

I thought that out of all solutions we were supposed to pick one that has least segments — which imo is even better problem (not sure if harder then original though).

Okay, definitely not — 1rst case scenario

Hey, ive solved c with binary search but was wondering whether this would work as well:

First we find sufix that has minimum average value. Lets say that this value is some k.

Does it stand that the answer is k, k-1 or k-2? Or sth similar?

but ur first soluition isn't really accepted it only passed pretests

yes

man what a solution :D

please I dont want to talk about this problem anymore.

But basically if abs(a — b) > 1 then you can't construct it.

I'm gonna have nightmares about B. Daaamn it took me so long to to get it.

your sieve is O (n ^ 2) and it should be linear (most likely — I don't know what task is about)

And what is the result? sum of all dp[][] values?

Indeed it has

eg. if I run this code

double x = 0.1;

cout << (x * 3 == 0.3) << endl;

result is 0 (false) for me

Wasn't it stated in problem description that here you can take any sequence? edit: nvm

why?

I believe you can now solve it on your own now.

(Hint I can still see 2 subsequences that are invalid)

(Hint 2 — 81267 is not prime)

(1,7) is not valid as distance between two next elements is not e (2)

Are you talking about problem C?

If yes you didn't understand task properly. You're not supposed to find pairs (unless they fulfill certain conditions) — instead you have to find subsequnces.

Would that be possible to solve D for n ~ 10^6?

I realized n was small very late into the contest and was thinking about variant in which n can be bigger :/

Yea me too. In theory XOR has the same abstract complexity as AND and OR. But I feel like our (at least mine) minds don't understand XOR the same, natural way they understand AND and OR. Also XOR has so many weird characteristics that aren't easy to come up with on spot.

We have to postpone contest a bit. No way I can wake up that early

aaah, smart

wait, what? XD I need to think about it