Amir_Parsa's blog

By Amir_Parsa, 18 months ago, In English

Hello Codeforces!

Thanks for participating in the round, We hope you liked the problems!

Also huge thanks to EndlessDreams for preparing the editorial.

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

»
18 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Wow! fast editorial, thanks for these nice contests.

»
18 months ago, # |
  Vote: I like it +11 Vote: I do not like it

What is the proof for $$$F$$$? I had some intutions. First, I translated this problem into an equivalent problem:

You have an array of positive integers. In one operations you select two adjacent elements, subtract $$$1$$$ from both of them. If any element becomes $$$0$$$ after this operation, remove it from the entire array, otherwise just put the remaining element back into its place. Can you remove all the elements of the entire array?

Now obviously if any element $$$a[i]$$$ exists (I call this element the "majority" element) such that $$$a[i] > sum - a[i]$$$ where $$$sum$$$ is sum of all elements of the array then clearly its not possible to remove all elements of the array.

Otherwise we will try to select adjacent element such that after applying operations the condition above (majority should exist) holds false. So obviously, after applying operation $$$sum$$$ will surely decrease by $$$2$$$ no matter what, so we will obviously try to apply operation on the maximum element $$$a[i]$$$.

However, (this is the part which I'm having confusion with) if multiple such maximums exist then we should try to apply the operation on that element whose adjacent element is also maximum (in the hope that adjacent element is also the global maximum so, we will reduce two maximums by $$$1$$$). Still, this doesn't guarantee that by following this strategy we will complete our task of deleting all the elements.

However, when I just checked the existence of majority element it simply got AC! I have no idea why this is the sufficient condition.

»
18 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Great contest! Thanks to the problem setters for providing such interesting problems.

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can some one explain E?

»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My way of solving problem 104349E - Shift in TheForces.

Well, the first character of lex-min-shift must be minimum character.

Imagine iterating from every start. All those are candidates for the answer.

If some candidate has the next character bigger than others, then that candidate is out. Otherwise, all still present candidates keep up by having the same string.

a b . . . a b a b . . . . a b

x . . . . x . x . . . . . x .

> < . . . > < > < . . . . > <

And now the key idea: if the candidate expands to another candidate, then he remains and the other quits.

a b . . . a b a b . . . . a b

< . . . . > > < . . . . . > >

That is true, from my point of view, for the following reason:

The candidate that remains will have string [cur][cur][rest]. And the candidate that quits will have the string [cur][rest]. Those two strings have common beginning, so

compare([cur][cur][rest], [cur][rest]) = compare([cur][rest], [rest]).

And [cur][rest] beats [rest], I think.

Each element of string will be examined not much time, so time complexity, is fine, not more than n*log(n), maybe. If we examine a cell at point of time t, then the length of candidates is already t and we need to go through all of it by some other candidate. 1 + 2 + 4 .. k times .. <= n. So k is O(log(n))


code
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

anyone explain me the authors code for D