Two funny images, why so heavily downvoted?

it seems you must get upvote then

I have never tried it so I am looking forward to it

Score distribution: 5000 — 5000 — 5000 — 5000 — 5000...

As far as I know, there already was one (I think it was one of the Hello / Good Bye rounds).

tourist was a writer of Hello 2018!

Here is all of tourist's problemsetting: (https://mirror.codeforces.com/contests/writer/tourist). Some rounds are written solely or almost solely by him.

Certainly not. You will not be considered as an official participant if you don't even make a single attempt.

yes

Yeah, sure, buddy. :))

You can already start upsolving it :)

Use int instead of long long

My submission 60129750 got 1497 ms (complexity is the same)

the shortest form of this problem: give you number Heads, list of blows and answer the fastest way to kill it (Heads<=0). There are 2 cases here: Result=1 and Result>1. When Result=1, you just simply pick the blow with the biggest damage value. When Result>1 (2,3...), you will notice that the moment the dragon die is before the the last rivival (Heads increase again) and number Heads become not positive so the last revival will not happen, If you have Result number time of blows, obviously, first Result-1 time you will change Heads by sum of (-damage+rivive), but for last you just change Heads number by minus damage value. So with case Result>1, you just simply pick the blow with the smallest (-damage+revive) for first Result-1 blows, and the last blow you just need to pick the blow with the biggest damage to end the fight. Hope you get it. I also struggled a lots to find out this logic, simple but hard to make it right in the center quickly. EDIT: So sorry, I made a mistake. I saw something about problem B so... Forgive me

I think it's because of digit function in your code. I think it's $$$O(q*digits^2*log(n))$$$ in worst case.

I also had the same complexity https://mirror.codeforces.com/contest/1217/submission/60133014 got tle at tc5.. can anybody tell why?

I got 1.996s on pretests and didn't realize lol.

$$$last$$$ can only be $$$0$$$ or $$$1$$$, so we can make $$$2m$$$ operations and do them offline.

u can also solve with using dynamic connectivity

if all d < h and has no d >= x — result -1

next chose a=max(di-hi) and b=maxd, last step max(a,b), all steps before last (b)

the shortest form of this problem: give you number Heads, list of blows and answer the fastest way to kill it (Heads<=0). There are 2 cases here: Result=1 and Result>1. When Result=1, you just simply pick the blow with the biggest damage value. When Result>1 (2,3...), you will notice that the moment the dragon die is before the the last revival (Heads increase again) and number Heads become not positive so the last revival will not happen, If you have Result number time of blows, obviously, first Result-1 time you will change Heads by sum of (-damage+rivive), but for last you just change Heads number by minus damage value. So with case Result>1, you just simply pick the blow with the smallest (-damage+revive) for first Result-1 blows, and the last blow you just need to pick the blow with the biggest damage to end the fight. Hope you get it. I also struggled a lots to find out this logic, simple but hard to make it right in the center quickly.

How to solve C with out gettin TLE on test 12 ??????????

First of all, if at a given index, s[i] == '1', then the index of the last good substring starting at i is at most (i + 20), otherwise the value of the binary number is larger than the max length of the string. So, for every index, we precompute the next occurrence of '1' and check the next 20 characters. Repeat.

my solution:

precalc zeroes-array: how many zeroes before ith element

next start from first (1) and count zeroes before (from precalc), if (f-length<=number of zeroes) result++. next shift left index to next 1-characker, if length > 20 (i think it is enough) you can break from cycle.

(for example 000101)

first step: 000[1]01

number of zeroes before before = 3, f=1 and 3 enough to add to result (1-1<=3)

next step go to 000[10]1

in this case your f=2, length=2, zeroes before=3 => result++

next step got to 00010[1] — same as first step (except zeroes before = 1, but also enought 1-1<1)

next step got to 000[101] — f=5, lenght=3, number of zeroes = 3 (5-3<=3) => result++

The boundary cases are little convoluted in the problem A, I guess.

Colour every back edge as black and the remaining edges as white. Since any cycle cannot contain all back edges, hence we cannot have a cycle containing all edges of the same colour.

If there is no cycle, answer is 1. Otherwise paint an edge $$$(u, v)$$$ white if $$$u < v$$$, else black.

• If there is no cycle the answer is 1
• Else you can use one color for the edges u->v where u < v and another for the edges u->v where u > v so the answer is 2

To find if there is a cycle in a directed graph, you can do a DFS marking differently vertex currently treated and vertex you finished treating. If you encounter a vertice still in treatment, it means it's an ancestor in the DFS and you have a cycle.

Incoming and outgoing edges colored differently ensures this. Question: Does Upper bound of 2 also hold for undirected given no multiple edges?

How to solve D if it is a undirected graph

You can check my solution, where I used binary serch.

I also used binary search

I also solved using binary search.

me too,binary search is more intuitive than pure math equation to me

No need for binary search, see my O(1) solution — https://mirror.codeforces.com/contest/1217/submission/60107664

not much work just find range [lb,ub] and ub-lb+1 is answer.a,b,c is input. x>=a and y>=b and x>y and x+y=a+b+c always which leads to x ranges from max(a,sum/2+1) to sum-b,now range difference are your total solution.

I did the same thing got tle

I am very very sad that my solution got accepted now (after the contest) just by using this implementation of segment tree.

So sad, that the implementation of the segment tree played a role in getting accepted for this problem. Was this intended ???? and why ??

I think you can do 1 query (but complexity remains the same). Just store two minimums for each digit. Constant will be much better than 3 * 10 separate queries.

i think alot of people checked for case where highest damage is more than number off heads but did not check when that it equal.

• 1
• 1 1
• 1 1

hacked 6 people with the same test case, one candidate master :)-

hell yah. it seemed like some easy formula and i didn't even think of binary search.

hell yeah missed c due to that.it was pretty easy, but A took time.but realised its simple inequality just find what range it could lie.O(1) solution in just 4 lines of code. link

which means (u, v) is considered different from (v,u).

I think it means that u can have an edge in both directions, but u can't have multiple edges from node u to node v in the same direction.

Thank you! I mistook the meaning of "ordered" as "sorted"..

I didn't have enough time to submit, but my idea is to build a segment tree for each digit. I planned to fill them in the following fashion: if $$$k$$$-th digit of $$$a_i$$$ is not $$$0$$$, then we put $$$a_i$$$ on place $$$i$$$ in the $$$k$$$-th segment tree, else some huge constant. To get the answer, you could take two minimums on each tree and choose the one with minimum sum.

Should pass in time, pure $$$O(n \cdot logn)$$$, albeit with a considerable constant.

for each position, build a segment tree, for each segment, maintain the smallest and second smallest number which both has non-zero digit in that position

For some reason I was thinking during the contest about maintaining something like merge sort tree for every digit position instead of just a normal segment tree through which you can get 2 minimums, and simulate non-existing numbers by large constants. Thanks all.

My solution ~ O(N): https://mirror.codeforces.com/contest/1217/submission/60132911 if you want to tutorial, inbox for me.

A good substring starting with '1' can be only '1' or '10' (the ones with length $$$x$$$ > 2 are at least $$$2^x$$$ and thus larger than $$$x$$$) — these can be checked with $$$O(N)$$$.

If a good substring starts with '0', there can be at most one good substring starting at given index (if it is of length $$$x$$$, and equals $$$x$$$, then already the next one will equal at least 2x > $$$x+1$$$). To find these for every given index, you can enumerate possible lengths (length can be from 2 to log2($$$2 \cdot 10^5$$$)), starting from the nearest following '1'. This is $$$O(NlogN)$$$.

Deliberate traps :{

THank you! Now I can go to sleep)

Hit em with (3, 1) 499999950 times, finally use the (11, 10...) to finish it. Are you suggesting there's a solution with fewer hits?

If there is no cycles in our graph we can simply use $$$k=1$$$.

For all other cases we can be done with $$$k=2$$$. Suppose we have edges in form $$$(from, to)$$$, we can paint all edges with $$$from < to$$$ into color $$$1$$$ and all edges with $$$from > to$$$ into color $$$2$$$. If we arrange all vertices of our graph into a sequence, edges that go left are of one color and edges that go right are of another color. Any cycle must start and end in the same vertex, so after making a first step left or right we need to move backwards, but we can only do it with edges of another color.

If exp + strength <= Intelligence , then there's no solution, answer is 0.

If exp + Intelligence < strength , then all combinations will work, the answer is exp + 1.

If exp + Intelligence = strength , all combinations except (strength, intelligence + exp) wil work , answer is exp.

now for the last case, the minimum exp that can be added to strength without disturbing the inequality strength > intelligence is the solution to:

Let x be the minimum exp required.

(strength + x) — (intelligence + (exp — x)) = 1

x = ceil((1 — strength + intelligence + exp) / 2)

the answer is exp — x + 1

Why not to say it from your real account, not fake one? Are you afraid of downvotes? Or afraid of us?

P.S.: I'm not arguing about the statement itself, just about people who can't honestly state their opinion.

You can easily extract the test case from the online judge. It says that the 73rd number differs, so, resubmit your solution, and print the 73rd query on the console. (Maybe at the start)

try 10 0 4

try 100 10 2 Answer is 3 but your output will be 46

Isn't this code very similar to this code: 60123155? Even the strangest of variable names like ee, uuu, vvv, te, etc., in the main code or just before it are the same.

First let's preprocess the array z, such that:

z[i] = number of zeroes to the left of i before the first 1.

For instance:

v: 0 0 0 1 1 0 1

z: 0 1 2 3 0 0 1

What the problem wants is the number of substrings s[l..r] such that the binary number in s[l..r] is equal to its range size r - l + 1.

Now let's say you're currently at index i and s[i] == '1'. You've already got your first answer, right? because s[i] == 1 and the range size is 1. Let's call our current value X and keep constructing new numbers using substrings that start in this index i and end at some index j (s[i..j]).

Notice that j < min(n, i+20). Because the maximum range size possible is 2*10^5 and you need less than 20 bits to construct that value.

Now let's add the next bit (at j'th position) and calculate our new value X, if the next bit is 1, X = 2*X + 1 and if the next bit is 0, then X = 2*X.

So for this substring to be good, we need it to have size X. Since we started at i and we're now at j, its size is currently j-i+1. But remember we have z[i] zeroes to the left! That means that if we could add those zeroes to its left (which doesn't change the value X) and make a substring of size z[i] + j - i + 1 such that z[i] + j - i + 1 >= X, then we found a new answer.

Hope that was well explained! :D

If graph is undirected this problem is about finding arboricity of given graph. This goes to matroid theory and is actually graphic matroid partitioning problem.

UPD: If someone is interested in practical introduction to this stuff, you may check out this tutorial.

UPD: Nevermind :(