Glad for another Div1!

Why do you ask?

Usually,the problems "C""D""E" in div2 are the same as the problems "A""B""C" in div1,respectively. As a result,there are three problems shared between div1 and div2.

same to me :(

Your comments be like:

so real

See this Quora answer by I_love_Tanya_Romanova

Just wait for another 30 mins. And you will have the answer to your question.

5 problems

Participants in each division will be offered five problems and two hours to solve them.

Dude, please read the announcement.

I used binary search from 0 to m for O(nlog(m))

Yeah me too

Use something like a binary search...

Say we can use k operations to make it non-decreasing. We can obviously do it in k+1. So search for value where it will be impossible to do in lesser steps.

See this Solution

what about a binary search for the answer?

The way I did it was using binary search because the answer is in [0, M]. Checking if a value is a valid solution means doing a greedy: attempt to turn the input array into a non-decreasing array with a set of operations, lesser than value X. If value X is valid, then you might find another answer lesser than X; otherwise, the answer is surely bigger than X.

That greedy verification implies going from left to right through all the numbers, and at a given number, you try to approach the maximum of the array as much as possible; that means either not doing anything with the number, or otherwise, you can always set it to that maximum of the array.

Well, I hope this logic works, still waiting for hacks

Which bruteforce?

I did that in the end,but how to prove it fits in TL?

For each i and bit position b compute the smallest index minReachable(i)(b) >= i such that a(minReachable(i)(b)) has bit b set and minReachable(i)(b) is reachable from i.

Processing the query: reachable if there exists bit b set in a(y) such that minReachable(x)(b) <= y.

54686628

Thanks:D

I was able to hack two with this — 7 7 1 2 6

I feel the same every time I see TAK/NIE in polish tasks.

It's because 300iq is learning Chinese recently.

C is cool and B is standard? Didn't you swap the problems?

const string yes =..., no =...;

Oh, i thought that it won't be a problem..

I'm sorry if it spoiled the fun of the contest for you :(

Btw, why is D tedious? The intended solution has a very short implementation in ~100 short lines.

Sorry I missed this part, either increase arr[i] or decrease arr[i-1]

Each valid solution should contain a number that occurs in at least half of all the given pairs. There can't be more than 2 numbers with this property. Attempt to use each one and then you can check if that is possible going in any order through the array; the first time you find a mismatch with another pair, try to take one value from it.

choose a[0] and check that the remaining pairs whom values aren't equal to a[0] share a commun number, if not check for b[0].

My solution is for every pair of leaves check if you can change question marks accordingly. But actually it's the other way around, first change ?s then every pair should satisfy the condition. I got WA and it's not a proper solution(found a testcase afterwards) Maybe also other people tried this?

The statement looked some simple that I immediately started googling some keywords but couldn't find it :/

I am so sorry! I thought that my problem is original :(

https://mirror.codeforces.com/blog/entry/67189?#comment-513710

Litreally your username ,binary search for ans from 0-m

Not in Division 2, but I think this works. We do casework. Obviously, one of the two numbers in the first pair must be x or y. WLOG, let the first pair contain x, and split into two cases based on which number is x.

For each possible x, iterate through the remaining pairs. One of the two numbers in the first pair that does not contain x must be y. Iterate through both of these possible values for y to check whether they work.

As we have four cases and can check each case in O(N) time, this will easily work within the time limit.

Check which pairs of numbers contain a[0] and then check if there is some number contained in all the other pairs (you can use map for that). Then do the same for b[0]. My solution

My approach :

• take an array temp and push 1st pair

• push another pair which does not have any elements same as 1st pair

• if there is no other pair then 1st pair is our answer else

• now pair(x,y) must be one of the pairs of this 4 elements

• take every pair and check

• if we find at least one pair then return YES else NO

solution : https://mirror.codeforces.com/contest/1169/submission/54683336

Pretests can't be too strong :)

There's no such thing as pretests that are too strong! (There are sometimes pretests that take too long to run though)

It's normal because people with rating from 1900 to 2099 participated in div 1

Больше не писать в системе IDEONE

According to the rules your last submitted solution will be considered even if your previous gave AC and the last solution gave WA.

Only the last correct submission is considered for testing. The rest are skipped.