If you'll do so you will make another record on codeforces .
Best Of Luck .

hope to become unranked in this contest)

Dammit I'm only expert.

Well, i did a sparse table

we can take the suffix max after sort the hero on the basis of its power and then take lower_bound.

Not necessary, Although I thought about Segment Trees first

Overkill segment trees was not needed at all.

no

I think if you sort heroes' by power, you can calculate the maximum endurance for each suffix in O(m)

I did it without Segment tree. Solution. Just sort, binary search and array for suffix maximum endurance

Not at all. Just sort the heroes by endurance O(MlogM), than in O(N+M) build an array that stored at element i what is the maximum power between heroes with at least i endurance. Then simply loop the monsters array O(N) and with a single lookup it can be found if the current monster could be beaten up during the same day or it is needed a new day

I did not use a segment tree or sparse table for this problem. You can check my solution: http://codeforces.net/contest/1257/submission/64838220

The answer is the minimal distance between two equal elements.

you have to find minimum difference between two repeated value. save the last position you get for each value and when you get it again take difference and update position of last appearence. then take minimum of all diference.

We note that, there is a answer if and only if some number is repeated otherwise ans is -1.

The shortest such subarray will be |start of that number(x) — another instance of that number(x)| so just count how many repeated numbers are there and print the minimum distance b/w them

I used two pointers which I later realized to be difficult to solve that problem.

It's an undefined behavior. For example if you donn't fill a local array explicitly, it doesn't have to be filled with zeros, it may be filled with anything depending of compiler.

See diagnostics in your submission: "Error: attempt to dereference a past-the-end iterator." I had a similar solution with the same bug. That lower_bound returns the end of the map when there's no heroes with energy day or more left.

It seemed very sorted to me. I won't say they were easy though, I might get hacked when I least expect it

Can you elaborate a little more please?

Bruteforce way can be Hacked, test cases are weak.

You are an idiot.

Greedy.Every day,choose a hero who can beat most monsters.

I implemented O(m*n), and though in worst case scenario there is no way it passes TL, it somehow got accepted.

I sorted heroes in descending of their stamina, and for each hero in this order I tried to find maximum of monsters he can beat if he enters now (i.e. iterate mosters one by one and increase counter if monster is weaker and hero's stamina is not exceeded). I break cycles if I find a hero with lower stamina than my current maximum.

My approach is, at first I sort all the heroes in basis on their power and then endurance in decreasing order. Then I try to find out maximum power for every endurance. It always proves that endurance[i]>=endurance[i+1]. Finally, at every step, I just try to pick the longest endurance(using binary search) which can able to kill all the monsters on that range.(I use segment to find out the maximum monster value on that range). If there is any monster whose value is greater than the maximum hero's power then the answer is -1.

My solution -> https://codeforces.net/contest/1257/submission/64846739

I finally managed to understand the easy way to solve the problem by going through people's submissions. I'll try to explain.

First, if we are currently at the $$$i$$$th monster, we have to choose a hero that can kill the largest no. of monsters. The only tricky thing is choosing that hero. Let $$$cnt$$$ denote the current no. of monsters that we can kill from the $$$i$$$th position. Initially, $$$cnt = 0$$$. Now, $$$cnt$$$ can be extended to $$$1$$$ iff there exists some hero whose endurance $$$\ge 1$$$ and the power is more than the power of the $$$i$$$th monster. Using this logic, we'll be extending $$$cnt$$$ as much as we can. To extend $$$cnt$$$ by $$$1$$$, we have to check to see whether there exists a hero whose endurance is $$$\ge cnt + 1$$$ and whose power is $$$\ge$$$ power of all monsters within the range $$$[i, i+cnt]$$$. If there does exist one, we can extend $$$cnt$$$ to $$$cnt + 1$$$.

To check this thing, we can have an array we store the maximum power of a hero whose endurance is $$$\ge i$$$. This can be computed by taking suffix maximums on an array where the $$$i$$$th element is the maximum power of a hero whose endurance is $$$i$$$.

Also, since we are always extending $$$cnt$$$ by $$$1$$$, we can instead keep a running maximum of monster's powers instead of using a data structure to obtain the maximum within that range.

Code

You can solve the problem without using segment tree or binary search. http://codeforces.net/contest/1257/submission/64838220 Just a map and lower_bound is required

I did a greedy solution. 64832445

Explanation — sort heros according to endurance and allocate each monster a hero starting from max endurance, than start making maximum group possible.

k is actually floor(n/2).

isnt binary search enough? I did not code it, I am a binary search code noob

I don't think this solution is correct. As the cost of distribution between 2nd and 3rd is not necessarily unimodal.

The answer was simply (K1+K2+K3) — N, where N is the length of the longest increasing subsequence.

Can u help me prove it why is it LIS? The idea intuitively seems correct.

But why it's working?

This is beyond my knowledge. Never knew LIS would be this powerful. This not only works for 3 arrays. The intuition is you want to maximize the amount of element to stay in its segment. What an elegant solution. to restore the steps of the answer, youll simply make the LIS related elements stay and move the rest greedily.

It wasn't intended (model solution uses some math and prefix sums), but the solution is really cool nevertheless!

Amazing solution!!

this is a good source for people who dont know LIS to learn how it works.

Now it's easy for us to run all the sample cases at once

It's a common solution for ERs (and, it seems, div3) because it's too much burden for the system to check 20-30 tests (and 30 tests are not enough sometimes) per each submit especially on tasks like A, B, C.

I highly prefer it this way. You get to have much better test coverage without insane queues.

You just need to find the minimum difference of i and j, of same element. If no such i and j exist ans=-1;

What will you say when all your solutions are hacked? lol

Don't worry. We hope you will expert very soon.

Use meet-in-the-middle, split x into first 15 bits and last 15 bits, and use map to check if there is second half.

Simplex!

Try something like this: 2 6 1 2 3 3 3 3 3 3 3 6 1 1 6 (ans = 2) 6 6 1 2 3 4 5 3 3 3 6 1 1 6 (ans = 4). These tests helped me to find out my mistakes

std::map works in O(log), not in O(1). So, your solution is O(nlogn)

It is guaranteed that the sum of n+m over all test cases does not exceed 2⋅10^5

:-/

I thought and did it that way only.

dp[i][j]: I'm looking at element i, at group j.

I can either start the next group -> dp[i][j]=dp[i][j+1]

or add element i to existing group -> dp[i][j]=(i is not in group j) + dp[i+1][j]

How does this runs in less than 2 seconds?

You remove duplicates from the vector a but still loop up to n, not to the size of a, accessing elements past its size. It doesn't necessarily segfault since the vector had size n+1 before, but It seems something problematic happens in that test.

Try greedily defeat more monsters, so we need to binary search how far we can reach.

Suppose we need to defeat K monsters and the highest power among them is P, we need to have at least one hero with p>=P and s>=K, which could be precalculated, in such a form: maxp_i = the largest power among heros which has s>=i. Thus we could easily check whether maxp_K>=P.

Binary search such K and get the answer, to find P, is a problem of RMQ，use ST.

Yes, there is a way. First sort all the heroes by power. Then create an array of suffix endurances for the sorted array of heroes. Suppose you have to kill k monsters on a particular day. Then find the maximum of those monsters and do a binary search on sorted heroes to find the suffix which includes all the heroes that have sufficient power to defeat the k monsters. Now, look at the maximum endurance of that suffix which we already calculated. If this endurance is at least k then we can kill k monsters. So you can check for each k whether we can kill k monsters or not in log(N) time.

Hi, check this case:

10 10 10
10 29 14 28 18 9 20 7 23 22
30 19 2 25 12 17 8 15 11 21
6 13 5 1 4 16 3 24 26 27

The answer should be 18. Hope it helps.

And also How to solve using segment tree because I have seen some has done by segmeent tree

using dp mean using LIS or something else?