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 | TripleM5da | 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 monster array
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)
[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://mirror.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.
****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
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 energyday
or more left.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)
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://mirror.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
Invariant: If there is a hero with more power and more endurance, he is always better than anyone with both of these lower.
Steps: Create an array that has the best weapon for each endurance -> update bestHero[endurance] = max(bestHero[endurance], power) and then place the suffix max
This 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://mirror.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.
Let, 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?
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.
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)
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?
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 mid such 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.
Think 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
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?
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 index idx 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
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.
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
,not5
.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
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.