Hello Codeforces!

On Nov/13/2019 17:35 (Moscow time) Educational Codeforces Round 76 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be **rated for the participants with rating lower than 2100**. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given **7 problems** and **2 hours** to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

**Attention Codeforces!**

*Calling on all tech disruptors, data specialists and computer science pioneers.We are offering fully-funded international scholarships for exceptional tech specialists from around the world. Accelerate your career by becoming an industry expert capable of making key data-driven decisions that add value and drive innovation within tech industries.*

**Harbour.Space University** has partnered with **SCG**, a leading business conglomerate in the ASEAN region, to offer exceptional tech specialists the opportunity to work and study in two of the most dynamic and vibrant cities in the world. **Join our progressive two-year program based in Bangkok, with 6 of the 24 months in Barcelona**, to develop the international mindset needed to accelerate your career and redefine how data drives the businesses of the future.

**Tuition fee:**

*2 years | €45,800*

**Education:**

*3 hours of study per day | 15h per week*

**Work Experience:**

*4 hours of internship per day at SCG | 20h per week*

**Living Allowance:**

*€16,800 euros | €700 per month living allowance*

Congratulations to the winners:

Rank | Competitor | Problems Solved | Penalty |
---|---|---|---|

1 | neal | 7 | 182 |

2 | kmjp | 7 | 216 |

3 | saketh | 7 | 218 |

4 | KrK | 7 | 225 |

5 | ivan100sic | 7 | 244 |

5 | pwild | 7 | 244 |

Congratulations to the best hackers:

Rank | Competitor | Hack Count |
---|---|---|

1 | Decayed | 39:-10 |

2 | liouzhou_101 | 59:-58 |

3 | dzhiblavi | 15 |

4 | Rian_5900 | 31:-40 |

5 | Fyodor | 10:-2 |

And finally people who were the first to solve each problem:

Problem | Competitor | Penalty |
---|---|---|

A | amnesiac_dusk | 0:00 |

B | Siberian | 0:02 |

C | Bohun | 0:03 |

D | LJC00118 | 0:16 |

E | jjang36524 | 0:23 |

F | DeadlyPillow | 0:19 |

G | black_horse2014 | 0:19 |

**UPD:** Editorial is out

Hope to become expert in this contest......

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

Best Of Luck .

seems he is going to do so

he is bot for sure or god

Strange that there's only one comment in 14 hours. Anyway, it's a PikMike contest so I'm excited. Hope I can finally get candidate master lmao.

hope to become specialist in this contest.

hope to become unranked in this contest)

hope to become headquarters after the round.

Hope to become Batman... after this round...

Hope to find Girlfriend after the round.

Make your handle GF_in_Three_Months

Me too, I made a bet with my friend and I should find a girlfriend in the next 40 days. ;)

It's fair easy for you. Just pass her some solutions :P

And marry her if she could hack them.

Dammit I'm only expert.

Hope to become 1500+ this contest.

Good Contest.

Were Segment Trees necessary in D? I had to do some maximum queries on the monster array, was too scared to try my solution without the tree.

Well, i did a sparse table

Oh yeah, right! Well thought!

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

I've done that. I said maximum queries on the

monsterarrayNot 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)

[D][IS][Greedy] [IS] [RIGHT]

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.com/contest/1257/submission/64838220

How to solve C?_

The answer is the minimal distance between two equal elements.

why

If you check the subarray that is the answer to the task, you will see that it's first and last elements are equal (because it is the most optimal). And all the elements between them are all different.

Sorry for my poor (maybe) English.

If you look at two equal elements in an array then the only case where it is not dominant is if there is at least another pair of two inside. The equal elements that have the minimum difference between them cannot contain another pair because that would contradict that the elements we found have the minimal difference.

because when you take two elements with minimum distance then between these two other element appear at most one.

1231 if there is repeated value between two 1 then distance between 1 can't be minimum.

Consider you have two suquences

1 4 3 2 4 1

Now here, we can choose the first 2nd and last 2nd element in a segment. That will form the minimum.

and other,

1 4 3 3 4 1

Now here, if we choose the same indexes as an upper example, it would be wrong. Because we can still minimize the segment to {3,3}.

So we can conclude that all we needed to do is minimizing the difference between equal elements. Hope you understood.

why result is 4, 5, 4 for 4 1 2 4 5 4 3 2 1 and not 4 4 for example

Because choosing a subarray should be contiguous.

I see now :) thanks

****The subarray of a is a contiguous part of the array a, i. e. the array ai,ai+1,…,aj for some 1≤i≤j≤n.****

you missed this line.

Wow, I feel dumb now jury-rigging a two-way multimap keeping track of element counts and number of elements with the maximum count

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

Implementation works: link

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

In question D, codeforces giving different output than other platforms like hackerrank, onlinegdb for the same code. Output on codeforces is coming as 0 and -1 for the 1st test case but it is correct on other platforms. Does someone know why is it so

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.Thanks a lot bro. code worked after handling this case

Seems not sorted by difficulty...

RIP my rating.

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

F is just btuteforce, LOL. 100e9 in 2 seconds))

UPD 1: Hacked.

UPD 2: Added set, Accepted.

UPD 3: Passed final tests in 2.5 seconds.

UPD 4: More stable program with a run time 1.9 seconds: Link.

Can you elaborate a little more please?

Just implement the dumb checking described in the statement with some optimizations (pragma`s, shuffle, set and popcount is enough). Code.

Not enough anymore xd

Now enough)

how does adding set help?

Still not enough xD

Kindly please tell how does adding set help in increasing speed?

Bruteforce way can be Hacked, test cases are weak.

Try to hack my solution)

Good test cases on F, I tried my best to make random solutions pass and failed.

You are an idiot.

How to solve D???

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

Can anyone please elaborate on this? How to choose the hero who can beat most monsters? I did something in my solution but I find that to be too messy.

Binary search on the hero. Solution

I saw people's submissions where they were obtaining the suffix maximums over the max. powers needed for a fixed endurance value. I find that idea to be much less on code. I'd like to know about that idea as I am still not able to think about it.

UPD: I have mentioned the idea in one of my comments below.

Just sort the {power, endurance} array. Then start with the first monster and check maximum power needed to defeat the dragon(Binary search), also I have maintained a suffix array that will store maximum endurance. If we can defeat the dragon then try to take one more dragon on the same day otherwise start with a new day. Link to my Solution

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.

We still are in the hacking phase, someone might try to break your code so it gives TLE, hopefully not!

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.com/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

Hey roll_no_1, I did a similar thing as well, but in the other direction, so just putting my strategy here as well

: If there is a hero with more power and more endurance, he is always better than anyone with both of these lower.InvariantSteps:Create an array that has the best weapon for each endurance -> update bestHero[endurance] = max(bestHero[endurance], power) and then place the suffix maxThis step would mean that at every value of endurance, the best value of power that is greater than or equal to the power for the range having more endurance is taken. (Greedy choice)

Move from the back and kill the current monster, if you can't kill the current monster, along with the suffix, add 1, else, keep expanding the array backwards updating the maximum.

Overall an order of O(n+m)

I did solve with the same concept but with binary searching. keeping a max suffix array is much more cleaner. Thanks for sharing, I learnt something cool.

You can solve the problem without using segment tree or binary search. http://codeforces.com/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.

Given the huge TL, I imagine my solution for G is off, but is it something like finding number of solutions to $$$\sum_{i=1}^d x_i = k$$$, where $$$d$$$ is the number of distinct prime divisors and $$$k$$$ is the minimum power of one of the prime divisors?

k is actually floor(n/2).

Upon further thought, it makes sense that it shouldn't be the minimum power of the prime divisors, but it's not at all clear to me why floor(n/2) encodes the proper information. Can you elaborate?

EDIT: Just tried to verify this on the samples. Unless I'm misunderstanding what you mean by n/2, this doesn't seem to work.

EDIT2: My implementation was wrong, tried to use stars and bars where I couldn't. My bad.

It's theorem 1 in this link: https://pure.tue.nl/ws/files/4373475/597494.pdf

n is number of prime divisors given in the input.

Lets say (p1,p2,..,pd) are the distinct prime factors and (a1,a2,...,ad) are the powers of prime factor. Now you can represent these tuple of powers (a1,a2,..,ad) for each divisor as a partially ordered set (poset).

The goal is to find the longest antichain which is the width of the poset.

You can notice that sum(ai) represents a distinct level.

Lets say the number is 2^4*3^2.

(4,2) represents level 6. (sum=6)

(4,1), (3,2) represents level 5. (sum=5)

(3,1), (4,0), (3,1), (2,2) represent level 4. (sum=4) and so on.

Its kind of intuitive that the poset is symmetric about mid level (level=n/2) and that should have the maximum cardinality. I dont know a proof.

Thus the answer to the problem is the number of solutions such that sum(ai) = floor(n/2).

This can be solved by fft.

My submission

I see; thanks, that explanation makes a lot of sense!

Can E be solved using this idea:

1) Iterate from i=0 to n. i is the last problem of first-person.

2) Then do a ternary search for getting the answer among 2nd and 3rd person.

Is this idea correct?

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.

ExampleLet, the initial owners of problems are: 2 3 2 3 2 3. And you have fixed that coder no 1 will take no problem (as you are iterating on number of problems taken by 1). Then coder no 3 will definitely take some suffix (maybe empty). Say suf[i] = cost that coder 3 takes problem no i...n. Then suf[] = 3 2 3 2 3 2 3. suf[1] = 3 as coder 2 will give all his problems to coder 3. suf[3] = 3 as coder 2 will give problem no 3 and 5 to coder 3, coder 3 will give problem no 2 to coder 2.

But it can be done using segment tree.

I'm not sure if it was intentional, but E could be solved by ordering the three lists, concatenating them, and then running a very well known LIS (Longest Increasing Subsequence) algorithm.

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.

LIS size is the most objects you can remain unchange

But why it's working?

Sort each array independently. Given this LIS size, you know maximum amount that are in place. The goal is to get whole array sorted, and each operation increases that number by 1 (place the element out of order to its position), so we will need that amount of operations. This is not a formal proof but an intuition of how I see it

It's actually exactly COCI lista

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 seems so obvious and easy once we understand the idea.

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.

How to solve G?

Hint: It turns out 'finding' the subset is easy but 'counting' it is hard. Can you prove a certain subset must be maximal?Decompose \forall x \in S as \prod_{i} x_i ^ e_i. Observe that x could be partitioned into equivalent classes according to \sum(e_i), and by simple combinatronics the reader may prove that \sum(e_i) = n/2 is one of the class with the largest size.

Hint: OK, can you count it?Rewrite all primes as generating functions: When there is only 1 prime (with e_i copies of it), represent it as a generating function of [1]^e_i, i.e. the size of the equivalent classes.

When there are more than one primes, simply divide the workload into half and solve recursively (DnK DP), and convolute the final results with NTT.

Why has CF started giving T test cases for every problem like codechef does?

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

Yeah, but then i need to care about resetting global variables and arrays when problem has T test cases and it increases my chances of making a mistake.

Wouldn't that be caught on the sample cases?

Well most of the times it doesn't.

You don't have to use global variables. They are evil.

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.

If this is the case I highly agree with you.

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

Good Contest.How to solve problem C?

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 be the time complexity? Will it be O(n^2)

Depends how you implement, I did it using pair and map in O(n).

English lesson: волшебная палочка — magic wand. :)

(Don't try to look it up on Google — you'l get the wrong idea. :)))

Finally gained some confidence, Thank you so much for the contest.

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

only single line error in solution of problem D drop my dream of Expert.

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

how to solve F?

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.

Does this fit in time limits?

There will be like 2^15*100*30 operations if you use hashmap.

Done!! thanks

I wonder if it's possible to do a hash collision attack to force lots of deep equality checks if your hash function is deterministic

Simplex!

I also tried to solve the problem by constructing equations and inequations but didn't know how to solve the system. Can you please provide some useful resource to learn the simplex method and also to understand how to code it? Thanks.

Can anyone point out what the mistake could be for test-case 2 on problem D ?

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

i just have solved problem 1257C - Dominated Subarray — in Greedy solution in just O(n) ; why you did'nt include Greedy tag ! this is my submission : 64830934

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

Didn't you notice that those 2 std::map's were never used? ;)

IWMG my friend did you read my solution !!!?

i never used std: map in it but just called it . i have used just one loop to read Input and an array to store last position for an element ! why it is O(n log n ) !

Yeah, im sorry for it, i thought you use only maps. Then you're right, your solution works in O(n)

In problem D, we have to take input from the users which is O(n). So total TC would be minimum O(t*n) which is the order of 10^12. How is it passing?

*Order of 10^10.

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

I can only solved 2 problems... kinda have feeling my rating will be decreased again XD. I hope I can get better next time T_T. Gotta learn more frequent.

Any clue about the 18th sub-test of test case 2 in problem D ?

Edit: I was writing min in place of max in Sparse Table. XD

Who else, first, thought of Binary Search for C? xD

:-/

I thought and did it that way only.

Yeah, but you applied binary search to get the index where a[i] occurs next. I was applying it to find the optimal length.

Yes.

Maybe.

Submission

Nice solution. I was checking if there exists a subarray of length exactly

midsuch that it is dominated, if no, I assumed that there will not be any dominated subarray with length less than or equal to mid, which clearly is wrong.Whats the DP solution for E?

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]

For all of you that want something to uphack but can't: 64856439. This shit really shouldn't pass, it should get WA or TLE or both.

Try to hack my $$$O(n*2^{30})$$$ solution to F: Link

How does this runs in less than 2 seconds?

It does, my approach takes approx. 3 seconds on the judging server of CF(I used vectors and cins and stuff), yet it took forever to run on my own computer.

However, I am getting WA 92 for some strange reasons, and since my logic is very similar to his, maybe he will get WA on the same tese(just my guess).

I went through his judgement protocol and saw that he has only been tested with tests 1 to 83.

Oh, somebody already put into the effort to tinker the constant and break it lol.

The reasonThink from the setter's POV: First, to break brute force solutions, I should design test cases with only 1 solution, such that the coder has to search through the entire solution space.

Then, to break code with only pruning implemented, the integers that are close to each other should share quite a lot of bits so that there are a lot of potential X that results in similar b[i] = a[0]^X. However, as you have very few solutions in the solution space (or else naive brute force goes through), integers that are far from each other should share very few bits. With randomization you bring integers that are far from each other together and makes pruning work efficiently.

Vaguely speaking, if there are 2x more solutions, naive runs 2x faster; if there are 2x less solutions, pruning converges 1 iteration earlier.

What on earth is test $$$92$$$ of problem F? I kept getting WA for it using the most naive brute-force algorithm.

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.

I don't think that causes WA though? Although he/she is reading elements out of bounds, no writes were performed so the data should not be corrupted, and more reads (albeit corrupted) could only cause more "bad" cases to show up, hence this issue should not lead to false positive.

I also think so. I mean, well, I am not doing anything to the out-of-bound indexes, and changing it to a.size() causes TLE3

I will hack you!

Can D be solved using binary search ? If yes can anyone share their approach?

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.

no systest?

How to sol D?? I need help..

Help needed in Problem E

My approach is getting WA on test case 6 and I don't know why. Please can someone tell me why it is coming wrong.

My Approach :

I will try to make all possible prefixes for A(first person) i.e. (from 0 to N) where N = k1+k2+k3. I have maintained a set of elements for all three of them. Now suppose prefix of A is "i", so I will remove all the elements less than equal "i" in the set of first, second and third person and for it, I am maintaining the count in a variable name "taken". Now the problem is to solve for B(second person) and C(third person), and this will be equal to the minimum of the count of (elements in C which smaller than the largest element in B) and (elements in B which bigger than the smallest element in C) this can be done using BIT(In which I delete the elements according to the prefix). Note that I don't have to give the remaining elements of A to B and C first and do the computation as we can assume that A was given to them in the correct order.

So the final answer for the prefix "i" = taken + "remaining element in A(as he has to give it to other)" + min(element B give to C, element C give to B). And the minimum of all the prefixes will be our answer.

My Submission

Thanks in advance!!!

Hi, check this case:

The answer should be 18. Hope it helps.

Yep Got it!

Thanks

E can be solved using dp.But some people solved it using binarysearch,how to solve it using binarysearch?

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?

dp[i][1] means the smallest cost which all [1,i] number return to its correct position and the i-th number(which is exactly i) belongs to the first Programmer.

dp[i][2] means ... belongs to the second Programmer. dp[i][3] means ... belongs to the third Programmer.

the ans is the smallest number among dp[n][1], dp[n][2] and dp[n][3].

if id[i]==1 and you want to let it still belong to the first Programmer, it cost none. Otherwise you will cost 1 unit.

Can you plz explain the transitions?

dp[i][1]=dp[i-1][1]+cost(i,1); dp[i][2]=min(dp[i-1][1],dp[i-1][2])+cost(i,2); dp[i][3]=min(dp[i-1][1],dp[i-1][2],dp[i-1][3])+cost(i,3);

cost(i,j) means the cost if let the i-th problem be solved by the j-th programmer. Easily to know that cost(i,j)=1-(id[i]==j).

dp[i][1] from dp[i-1][1] means let [1,i] problems all be solved by programmer 1.

dp[i][2] from dp[i-1][1] means let [1,i-1] problems all be solved by programmer 1, but the i-th problem start to become be solved by programmer 2.

It means when you start to assign i-th problem to programmer 2, you cannot assign all j-th problem (j>i) to programmer 1.

Can anyone confirm whether my approach for D is correct.

Sort the soldiers with inc power. For every ith monster, do B.S and find the soldier whose power >= power of monster, let be at index

idx, then I will choose the soldier with maximum strength from indexidx to n(as all soldiers after idx have greater power than idx). Let's call this soldier as'X'.I will kill as much monsters with this soldier as I can. Now two case arise-

`1. Number of monster killed by x becomes equal to its strength, i.e., x.killed == x.strength`

`2. It's power is less than current monster.`

For the first case I will increase the count of day and again iterate as done in first step.

For the second case, I will B.S and find the soldier whose power >= power of monster, and has the most strength(among those having power greater than the monster), let's denote it by

'Y'.Now 2 conditions arise,

`1. x.killed < y.strength`

For this case I can safely say that instead of chosing X in the first place I could have chosen Y and killed more monsters than X, so I update my current soldier from X to Y (as X.power=Y.power, X.strength=Y.strength).`2. x.killed>=y.strength.`

For this case I increase count of day , udate my X and iterate forward(X.power=Y.power , X.strength=Y.strength, X.killed=1).I am getting WA for 2nd test case.

Here is my solution : 64836864

The color of the name seems to be wrong

Yeah, I have the same problem, I hope it's gonna be fixed soon

Yeah,I have rating above 1600.I am still specialist!!!

++

Does anybody have a $$$O(n)$$$ approach to solve D?

I don't think an O(n) solution is possible for this problem. O(nlogn) is needed at least.

UPD: oh there is a clever O(n) solution. watch roll_no_1 's comment.

You are also Chinese, so you can see this.

https://www.cnblogs.com/KisekiPurin2019/p/11854682.html

You can use dp to get the highest power of heroes which has at least i endurance.

p[i] is the highest power which can beat i monsters in just one day.

and then you can use greedy, each day try to move as more as possible.

It means you have already beaten i-th monster, and you want to beat the j-th monster, today you move j-i blocks so the highest power is p[j-i], if p[j-1] < a[j], you need to wait until tomorrow and use your highest power hero p[1] to try to beat it.

Does anyone know about this anomaly

Right, Me too.

me too

When will be an editorial?

What was the approach for D apart from Segment Trees/Sparse Table ?

Sort by endurance and find for every endurance suffix maximum instead of using segment tree, and just compare maximum of monsters with this suffix maximum

you sort array of pairs <endurance, power>. Then you try to kill in one day as much as possible so you iterate through $$$a_i$$$, count the number of monsters you want to kill this day as $$$cnt$$$ and memorise the most powerful monster this day as $$$max\text{_}pow$$$. You go further and further until there is a hero with $$$s_j \ge cnt$$$ (it can be checked by $$$lower\text{_}bound$$$) and a hero with $$$p_j \ge max\text{_}pow$$$. To check the last condition you can look at max hero power on suffix $$$[j..m - 1]$$$ and you can do it in $$$O(1)$$$ by precalcing an array $$$max\text{_}suf$$$ where $$$max\text{_}suf_i$$$ is the maximum power of hero in suffix $$$[i..m - 1]$$$ in sorted array

Why don't you read above there have been atleast 10 comments about D solution !!!

My Screencast for this round.

https://www.youtube.com/watch?v=g5n6eW7uwVY

Jesus! Where is the solution(

ok. i just want to know how to solve problem G

I just made a brief writeup above.

UMMMMMM!!! OK XDD

I have a question about the problem D. In this question,a special example

Input:

1

5

1 2 3 4 5

3

1 10

2 10

5 1

for this example,the right answer should be

`4`

,not`5`

.And I found that a lot of the output through the AC code was 5.Why?awoo

I found that some code can't even pass the simple data below： 1 2 1 2 1 2 2 Some of them AC code output -1,I think the background test data is too weak.

s_i should be less than or equal to n, so {1, 10} and {2, 10} are invalid inputs

Can anyone explain solution of F briefly? TIA

Check this out

When will the editorials be available ?

PS:Hints on div 2 C,D,E,F,G please ... I am new:)

How to solve E?? I think in E many coders used different techniques to solve it..

Here are some in the comments.. more are welcome. https://codeforces.com/blog/entry/71362?#comment-557767

https://codeforces.com/blog/entry/71362?#comment-557863

Using LIS https://codeforces.com/blog/entry/71362?#comment-557658

Editorial?

When will the editorial of the problems be posted?

How about editorials???

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).Color display still not fixed ?

I can't see my friends standing of this contest. (It's not for sign in problem)

Let me know if I only facing this problem...

Why Difficulty of this round in Problemset is None

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).Please also include pwild as the 5th place winner, we had the same penalty.

Whoops, sure. Funny enough my script got pwild into the rus version of the table and you in the eng one :D

I was wondering why I got a message saying I was mentioned in some topic, but then not actually finding my name in the text.