Всем привет!
Завтрашний раунд пройдёт на наборе задач Московской олимпиады школьников по программированию для 6-9 классов. Пусть вас не смущает возраст участников, московская методическая комиссия постаралась отобрать для олимпиады разнообразные и интересные задачи. Непосредственной разработкой задач занимались feldsherov, ch_egor, halin.george, ipavlov и GlebsHP.
Надеемся увидеть вас завтра в таблице результатов!
P.S. Будет использована стандартная разбалловка.
UPD Поздравляем победителей раунда!
UPD2 А вот и разбор задач.
Auto comment: topic has been translated by GlebsHP (original revision, translated revision, compare)
Этот раунд рейтинговый? Просто в тексте не было информации об этом!
рейтинговость раунда определяется состоянием системы codeforces)
the rating you get is the rating than CF just want to give)
programming competition for school students of grades from 6 to 9.
I was playing Mario when I was in the sixth grade
God bless my childhood
I practice for typing when I am grade 6. Who bless my childhood? please!
G0D_FaTHER what were we doing when we were in 6th class ? I remember spending time in school ground!
some of this students are red on codeforces. for example voidmax he is 9 grade btw (he was red)
Oh no...
maybe they have to make a div1 round for them not div2
Man ,I didn't have PC when I was in the sixth grade :(
I didn't know what's a computer when I was at 6th grade!
That's nothing! When I was in 6th grade, we had to walk to school 30 kilometers every day, uphill both ways!
As a kid I lived in Manhattan and it was mandatory to walk a different route every day!
that's when you realised how important dp and graphs are.
both ways uphill? :) I had only one way uphill
I started learning programming at 5th grade because our "modern" PC died and qBasic was about the best "game" I managed to find for the older one xD
Why is my 3rd hacking attempt still waiting while my 5th attempt has been judged?
LOL
this isn't the blog of the round #400
Oh sorry
Can you change the contest time, please? .. In Egypt we have a weekly prayer time in that time, an hour after that will be perfect.
The contest time is bounded by the time of onsite competition. It should start after the onsite competition has started and finish before it has finished. I'm sorry, but there is no way we can change the competition time.
I hope to change the time as it time of prayer in most of arabic countries
This is the worst timing you can put for arabic muslims :D
The round is not for Muslims.
number of problems ?
Email says 5.
Seems like the King got resurrected .
change the time please. it's our week pray time .
Then do not pray.
will the contest be rated???????
These days number of problems <= number of problem setters. Get prepared to read long problem statements and strong pretests. I wish I perform well :)
It seems like I am the ONLY arab who will participate in this contest
Why aren't you in the same situation as the others?
not the same religion
I wanna take a moment of silence to thank god who created me an atheist so i can peacefully take part in today's round :D
Canada I am coming.
Why canada?
Why Nicky Minaj?
EZ Silicon.
FYU, Nicky Minaj is "QUEEN OF RAP"
you will notice a decrease of contestants because of the Arabian issue
hope to change the time of the contest
Please, keep in mind that Codeforces always tries to vary competitions time to give more people an opportunity to participate in at least some of the contests.
Exactly. As much as the typical time may work well for arabs, russians and other europeans, the contest usually ends at 2-5am in Korea, Japan, etc. This is a global community and any time chosen would not work for some people. Also it is well explained above why this time cannot be changed as it has to work around the on-site competition.
But when most of competitions carry out in night time for east regions, it's ok for you and you don't have any problems. Think about others sometimes.
This happens when you don't thank MikeMirzayanov, warning! :P
To all the people who have pray time during the contest: which one is more important, Codeforces or praying in the name of some god who might or might not exist? I personally think that skipping one day of prayer is justified ;), this can be a secret between you and me, nobody else has to know.
Hey!!!
Why you are not legandery grandmaster god :p
god is a specialist in screwing my life up. Thank you so much :)
I like you!
Thank God I don't believe in God.
Since the king is back, I hope this round will go smoothly :)
I don't like long problem statement , please try to keep it short like atcoder!
How many to problemset?
Only one problemset :D
LOL
Can you change the contest time, please? An hour after that will be perfect.
Before writing such comments, pls read the previous comments about it! There are only 39+1 comments till now.
P.S sorry for my poor English :)
Is this round will be rated?
Yes this round will be rated....
Will CF beat the tortoise today?
Will CF beat the tortoise today?
Rating prediction for this contest could be found here (after contest begins)
Extensions:
About CF-Predictor
Good luck & high rating for everyone!
I hope the round will be interesting.Good luck to all participants!
points distribution?
why scoring is not updated yet?
How to solve D?
Come from back and do this : string s = v[i]; while(s > v[i+1])s.pop_back(); v[i] = s; I don't know whether this will pass sys tests
Iterate from (n-1)th string to 1st string, go on comparing with next string and trim this string till it is not greater than the next one.
But since n can be 5*10^5 and length of string can be 5*10^5,
won't that solution with its ~ 2.5*10^11 operations be waaaay to slow? (in worst case)
sum of lengths of all strings is 5e5
Thanks, apparently I need to pay closer attention to the problem statement.
Best Div2 Round ever?
I think B is harder than D ...
If RoyalWyvern above is correct I agree. Had only 13 minutes left after A, B and C. Normally I quit, but I thought what the heck... Past pretests on D... |-)
I had only 10 minutes left after A,B,C. I finished coding D 1 minute late.
Well, at least you solved D 2 minutes quicker than I did!
My first comment....Please Upvote me
How to solve E?
Make a set of a,b,h using set < pair<ll,pair<ll,ll> > >
where first element of pair is b and second is pair(a,h)
then sort the set.
Then apply dp a[next_i] < b[i]
check for the maximum possible height.
I don't think, this greedy choice will work here.
Sort by B values. Then dp[i]=dp[next[i]]+height[i] where next[i] is the nearest ring to the i'th ring such that a[next[i]]<b[i]. Incase no such next[i] exists then dp[i]=height[i].
Then the answer is the maximum of dp[i] where i varies from 1 to n.
What do you mean by the "nearest". What is the order on ai?
Sorry if my answer was not clear. The ordering on rings is on the basis of b values. Nearest ring for i'th ring is j'th ring such that j>i and j is the least number such that a[j]<b[i]. Here the indices i and j are after the sorting according to b values.
Here is the link to my code if it helps : http://mirror.codeforces.com/contest/777/submission/24976225
My exact same solution gave me AC in c++ whereas it was giving me TLE in python. This wasted my 15 mins and also 1 incorrect submission
My correct output is weirdly getting wrong answer on 1st test case itself -_-
Looks like CF knows dark magic to make correct output wrong.
Is D to be solved with trie? I constructed the trie from nth element to first.
not needed ... keep the last string as it is... then greedily check the max prefix you can keep from bottom to top
Why WA in pretest 1 in D? all samples matched... :/
Same with me.
First test may be different from the first example.
No it's not. I asked them. In custom invocation also, it's producing wrong answer instead of correct one for sample test case 1. Something's wrong with CF server.
It might be that CF compiler does not give the same answer for the test as yours.
It may be because the way you outputed the strings. Initially i was changing all the characters that shouldn't be outputed to '\0' and it didn't work,but the next time I just printed the characters I had to and ignored the others(and passed the pretests)
I checked that too. The problem is with server. I ran custom invocation, and my variables are getting incorrectly assigned on CF servers. I had a variable whose value I explicitly set to 0, but CF is taking it to be 1.
i dont think there is a problem w cf server if it is only your code that is running wrongly. Maybe there is some ambiguity somewhere? why not share your code for us to find out?
http://ideone.com/w9V6KY
Run this code on test case 1.
My output from custom invocation is this
5 8 4
sid=3 len[sid]=1 i=0
0x2140dfc8
2sid=2 len[sid]=1 idx=1
2sid=1 len[sid]=1 idx=1
1 1 1
1 1 1
#
#
#
===== Used: 0 ms, 16220 KB
Задача E : Почему мой алгоритм неправильно?
sort honoi by outcome radius non-increasing order.
dp[i] — maximum sum of heights when must use i-th honoi (after sorting) and some j<i honoises.
//there I use segment tree. dp[i] = h[i] + maximum( d[j], 0 <= j < i, and a[j] < b[i] ).
ans = maximum(dp[i], i = 0..n-1);
First div 3 round :)
I disagree. For me it was
Div 1.89=)So you are claiming this is harder that the usual div 2 round?
Yes, for me it was harder than usual.
I think A and B are harder than usual but D and E are easier.
i tried to hack a solution using generator but it was showing some return 3 error from validator.exe
Here is the program ,what is wrong in it
what is wrong with it???
After sync_with_stdio(false), you cannot mix cout and stdout. Calling fflush(stdout) might be the problem
EDIT: Nevermind, it seems to be another problem
endlautomatically does that. Why did he even used that. :Pno ,initially fflush was not there, I added fflush when it was showing error
I feel there are extra spaces at end of rows of input
Does i care about those extra space?
There shouldn't be extra spaces in the end of the line. Validator checks for it.
When you spend all your time solving C and then realize that D was easier(atleast for me) and should have tried that.
Cannot agree more. Even E is easier than C
I just saw the problem E. Is it graphs and CC?
I cannot code it in time (cuz my stupidity makes me waste around 40+ mins on problem C). However, I am pretty sure it is sorting, dp and segment tree.
Its on simple greedy and sortings
How do you solve C without using bitsets? They make the total complexity of my submission O(k*m/64), and that probably won't pass in 1 second ;( upd: yep, it did not
I used segment trees with range max query and it passed pretests.
Overkill
How did you do it ?
For each row i calculate min row that can be reached, call it mni. Then if mnr <= l then answer is yes else no.
p[i] — the first index where an increasing sequence begins, which comes to the i (this sequence can go on). Then check
if (p[r] <= l) answer is Yes;
Oh, thanks, now I feel really stupid...
You can store in the array the ranges with the maximum size, that contain sorted column.
how do you compute range[]? Isn't computing it O(n^2) making it TLE?
what I ment was O(n*m) making total running time O(n*m*k) ~ 10^10
But you only need to compute it once, which gives the time of O(n*m + k)
Thanks, I think I need to go back to sleep.
Look at the example. We can split this matrix into disjoint sorted columns:
We read this matrix from top to bottom, row by row. When we encounter a value which is smaller than the previous value in that column (
if (val < prev_val[col])) that means we have just met the right end of some sorted range. For example, look at the first column:1 3 4 5 4. After reading first 4 values1 3 4 5we encounter a value4which is smaller than the previous value5. Now when we've found boundaries of the sorted interval1 3 4 5, we should record them. We know that this interval started at l and we know that it has finished at r. We do a loopfor (int i = l; i <= r; i++)and record what we have discovered:How many times will we touch an element of the matrix? At most 2 times. The first touch happens when we read it. The second touch is when we record the interval with a
forloop.Thank you for the amazingly detailed answer.
I think we can even go bottom-up from n-1 to 0 for each column j, so that every time we descend we remember the largest row index we started descending from and update each a[i][j] accordingly, only needing a single for loop.
Thanks again!
When we go top down, we don't need to store the original matrix. So top-down traversal should have a smaller memory footprint than bottom-up.
I understand range[l]>=r but why range[l-1]>=r?
I don't know :)
In the original idea I came up with during the contest I wanted to find 2 intervals which are closest to the given index l. So, I have thought about the following configuration: [l1, r1] l [l2, r2].
I wanted to check that I fall inside of either the first interval or the second interval.
But in the algorithm that I have described we need to check only one interval. I will edit my comment.
I solved it by just traversing the 2d array
and maintaining a index of minimum and maximum element
http://mirror.codeforces.com/contest/777/submission/24969962
You can use Dynamic Programming. You have dp[i][j]-the longest non-decreasing subsegment(continous subarray) of the j-th column that ends in the i-th line.To get it,you simply look in dp[i-1][j] and check if a[i-1][j]<=a[i][j]. If it's true,dp[i][j]=dp[i-1][j]+1,else dp[i][j]=1. Also,you need best[i]=the maximum of dp[i][k] with k in range 1..m At each query,you check if best[r]>=r-l+1 and print the answer depeding on the condition.
store in one dimension array
3 cases: 1) n==1 YES for all requests 2) m<=1000 you can over 1000 colomns all one in O(1) * 100 000=k so it take O(10^8) 3)m>1000 ,so n<= 100 so I just build table answer[100][100] for all possilble l and r
http://mirror.codeforces.com/contest/777/submission/24975294
Is it okay to ask some questions here? I have joined the contest now and also yesterday but I was unable to submit atleast one solution. I wonder why my rating didn't go down yesterday. Will my rating go down now?
If you haven't made any submissions, your rating will not change.
Your rating wont be effected if you dont submit anything.
Unless you have at least one submission you are not taken into consideration for rating changes.
"one submissions" xD
Yeah, happens :D
KAN please look into what's weird with D? Correct solutions are getting wrong answer!
Can you please highlight an instance ?
I've explained it here
and in this thread
What was the 4th pretest of E about?
sorting by bi > bj, ai < aj not ai > aj
But why the order of a matters? Doesn't the prefix length where we search for the maximum depend only on b? Since any processed aj lesser than b should be ok.
Yes, it does matter. Unfortunately, I only realized it in the last 2 minutes of the contest. Consider rings with the same b, then we should end the segment with the smallest possible a so that we can use more rings later.
Edit: nvm.
This order matters because, since a smaller ai can cover many more rings to come, hence, for same 'b', a ring with smaller 'a' should come later, so that it adds up to a greater dp value. Otherwise, your answer can be lesser than it should be.
Thank you!
Couldn't figure it out till the end,was checking my segtree implementation for every WA. Anyways, it was easy but good problem.
When you about to click submit button for D and the contest ends. Hope my solution was wrong.
With some Arabs praying and some other people sleeping or working Codeforces was deliciously responsive today! Thanks!
The test should be at most 256 kb .
Then how can i hack o(n*m*k) solutions at C or o(n*l) solutions at D?
Write generator.
Looks like the Div.2 rank.1's solution was written by multiple people.
ha ha... 5 codes and 4 different templates :p They could've atleast used the same template.
Очень хороший раунд, задачки на логику.
My request to feldsherov, ch_egor, halin.george, ipavlov, GlebsHP and KAN
Please look into D. Something's wrong with CF server!
Here's proof
http://mirror.codeforces.com/contest/777/submission/24975275
http://ideone.com/Mxgyyt -> exactly same node, not even a character has been changed. You can compare diff if you want.
Results are so different!
I don't want to lose points because server's fault. Please look into it!
Thanks!
It's not server's fault. You have UB somewhere.
No. I have checked with custom invocation. My array len[] is getting incorrectly assigned inside insert function.
You are blue, but u talk like a complete newbie. By now, you should know that compiler versions differ on different Online platforms, and thus produce different outputs.
Don't u feel like taking a second off and thinking about what may have gone wrong before blaming the CF server and taging all admins ?
This is sheer stupidity, and complete newbie attitude. How many times have we seen this same query from multiple multiple people ?
I challenge you to find a UB in my code! If you do, then you can call me newbie :) Deal?
If you can't find bug, then you by default admit I am right, and I should get my ratings back.
You used the memory returned by malloc without initializing it, which may behave differently by environments.
Okay fine. But I've also tested the code with explicitly initializing present = 0 and all children set to NULL in custom invocation. The bug didn't go away.
No. As I just tested, changing malloc to calloc killed the bug. Besides, your code is TLE even after fixing the bug.
http://mirror.codeforces.com/contest/777/submission/24980602
What a strange contest for me :/
Thank god for TLE XD
Anyone else solved E with sorting and a stack? I can explain my solution if there is interest.
Really? How? I used segment tree + heap, but I'm pretty sure BIT can be used instead of segment tree.
Well, here's a description of my solution:
First, you sort the disks in a descending order, prioritizing the variables in the order b, a, h. (Note: my code actually swaps the names of a and b) Then, you go through the disks in the sorted order. You remove as many disks as you need to from the stack, until you can place the currently processed disk on top. You maintain the current total height of the stack, and also a maximum achieved height. The maximum height is the answer.
I couldn't come up with a proof for this, but neither could I come up with any counter-example, and it surpassed all the tests. It just felt like it could work.
I also have no idea why that works :)
I was 30 minutes late to the round. I solved from a fake id. I did this way :)
This is not cheating :P I didn't submit from multiple id's :P
I am sorting according to outer radius (bigger outer radius first).If outer radius is equal ,then sort by inner radius (again bigger inner radius first ) . Now let's say I have kept two data in my stack for every element (the inner radius and the height) . I maintain a global height variable 'gh'. What I do in every step is that I pop the stack elements till I get the top of stack element whose inner radius is lesser than the current element's outer radius.And then I come out of the loop and push the current element on the stack. In every push and pop operation I update the global height variable gh. And in every iteration of loop I update the final answer.
Why this would work ? Everytime one pops an element whose inner radius is greater or equal to the current element's outer radius , it's guaranteed that the popped element can't be used in the future as we have already sorted by outer radius so the element's coming later on also won't fit on top of this ring.
Complexity : NlogN for sorting and N for the main loop with stack operations.
My solution
same here :)
Этот раунд самый удачный — 777
The first time I have solved 4 problems.
So, I assume you used 0-based indexing when you said that?
My skill is like Petr's or tourist's when they were in 6th grade.
I think tourist was much better when he was in 6th grade :P
tourist won Belorusian olympiad when he was in 6th grade. Look
tourist got 225/600 in Belarusian Olympiad when he was 7 years old. What the fuck?
When God made tourist
"A spoon of kindness... perfect"
"A bit of handsomeness... incredible!"
"And just a pinch of coding skills..... oops fuck. I messed it again"
A: AC
B: FST (WA)
C: FST (TLE)
What happened to my brain?
A:WA
B:WA
C:AC
what happend to my brain??
How to solve E with segment tree?
Compress the inner and outer radiuses so that all radiuses are less than 200000.
Sort all the rings by outer radius in the decreasing order. In the case of a tie, sort them by the inner radius, also in the decreasing order.
For each ring, calculate the maximum height of a tower with that ring on top. This is obviously the height of the ring + maximum height of towers where the top ring has inner radius less than the outer radius of the current ring. Solution with segment tree becomes obvious now.
I am shocked by the programs of THE RK1. I don't think a people will code in more than FOUR different code styles. I don't mean he has cheated,just curious.
I know a little about the rank 1[user:Mr.Stream] but I know he is about 60 years old. What an unbelievable achievement!!! Could i make friends with you? Thx!
you will make friends with 4 people QwQ
Although the rank 1 is used the name of XianYou Xu,but I guess he is not the 60 years old man,maybe it is just a joke by his student.
I'm too stupid.I use memset and strlen() in the for loop.And I got TLE in C and D
Contest was easier than usual, D was little easier than C.
About the Rank 1...
There was a legendary man called HangZhou Blade Master...
and now you see that...
Actually i can't why My E Programme TLE ON 13..... And i want to say congratulation to rk1[Mr.stream]
D is the worst question, why is it D, I think A is harder than D, liked solving C. Why is it like that.
A shoutout to all those who stumbled at pretest #4 in problem E cuz of the sort :D
When can we see the solutions？
Could anyone please tell me why my solution on E got a Wrong Answer on test 39? I tried to solve it by using set and multiset instead of a segment tree,but it failed. Is it possible to solve E this way?Thank you! Here is my solution : http://mirror.codeforces.com/contest/777/submission/24972634
I came up with a group of input to prove my code incorrect. And I found the elements I intended to put into the set actually failed to be inserted. Can anybody tell me why?
Here is the data:
5
2 3 1
2 4 1
2 5 1
2 8 1
1 2 1
The expected answer is 4,but I got the incorrect answer 5.
Some interesting bug I discover. So my submission 24970450 got wrong answer on pretest one. But when I run it on custom invocation, I got the same answer.
#b
#big
#big
Whereas the output from the judge is
#b??
#big
#big
I know the error comes from my failure in resizing the string, but shouldn't the custom invocation gives the same output as the judge?
I guess, that "??" is just to show, that there are space characters. In custom invocation there are 2 spaces instead of "??"
but why does whitespace matter when u print? i can always print excess whitespace at the end of the line and still get AC
'\0' and ' ' are different.........
that should make my code even more correct. cause cout will automatically ignore everything after '\0'...
char[] and string are different. string won't ignore '\0'.It records the length directly.
read link
It says there "This function overloads operator<< to behave as described in ostream::operator<< for c-strings, but applied to string objects."
If you dont believe me, try writing something like:
the result would be just Chestnut.
char[] ends with '\0',so when you convert char[] to string,it will only convert chars before '\0'.
You can try this
ok, looks like i am wrong then. This is indeed interesting, I got ChestnutZun when I print to my terminal(which looks like '\0' being ignored) but I got 4368 6573 746e 7574 005a 756e 0a when I print to a file. Do you have any idea why?
Maybe '\0' was ignored by your terminal.It looks like a space on mine(Windows cmd).
i run it on my terminal, cf and ideone though.all of them ignored '\0'
most of browsers ignore it too..... Custom invocation and online ide don't escape '\0',but submissions page do....
oh ok, thanks.
Is it possible to use fenwick tree instead of segment tree for problem E? I'm got AC with segment tree but WA with fenwick. However, I've used fenwick on prefix RMQ problems before (i.e. when we query for prefixes only) and they've all passed. So now I'm wondering if it's possible or not?
24965518
Maybe this is a stupid question, but why was it necessary to group a and b into the same array and operate fenwick on that array? Wouldn't it be correct to update on the indices of the given array from input?
The values are large enough and distributed randomly, so maybe this is a stupid question, but how can we use indices instead of real values?
Maybe my algorithm is stupidly wrong, but this is what I did so far 24985290. Code is easy to read IMO
Can anyone explain me the complexity analysis of my solution to problem C. Submission Link
My approach was to store all the increasing sequences in in each column ans push the starting and ending points int the map, along with size of sequences and the column in which it occurs. I also store the length of increasing sequences in "pts" vector. This vector is then sorted and duplicates removed from it. Now, for a given query, I simply iterate for all possible length >= (r-l+1) and check if I can get an answer from it. For a given "j", the answer exists only when the pre-computed range covers the entire length. This can be broken down into 3 cases (Similar to linear inequalities). If answer is found at any point of time, I stop the process else I brute force for all possible values of "j" and all possible positions in the matrix.
I think this solution of mine can give TLE on some cases where number of answers "NO" is very large. But even I was not able to come up with a test case where my solution fails. (I have tried this technique in few questions earlier too, but never failed). But still can anyone help me in analysing the complexity of my solution. ?
Yeah, This does seem like it should have TLE'd. Since your query answering time can possibly be linear. So your complexity should be n*m*Log(n*m) + n*m*k
Former is for the preprocessing on finding non decreasing sequences, while latter is for query answering. As for each of the K queries, in the worse case you might have to iterate through all of the n*m (max possible number of sequences) to find your answer.
Now, I feel the complexity analysis can go as follows. The are sqrt distinct values below given N. So, in most cases, it perform query in O(sqrt(n)). But there is one particular case where it will TLE. The case is as follows. All the columns should be strictly decreasing. So cnt in this case is 1 everywhere. Now, if each query is (n, n), then k in my case will be 1 and I will have to iterate through each of the (n-1)*m grid points to tell the solution.
I don't get how you got sqrt distinct values ? sqrt(n) distinct values of what ?
Number of distinct values in "pts" vector.
Only iterating distinct values >=(r-l+1) isn't gonna get you the answer right ? You need to know the starting point too. So in the worse case it is still n*m*k right?
Even if for each distinct size length the list of starting indices is sorted so you can binary search for the query start. It still adds another Log factor to the sqrt, which shouldn't pass the time limit.
There has been some time since a saw sneaky pretests like these. They were all really light weighted and I forgot how painful it's to discover it after the contest is over.
Yesterday I was Specialist, today I'm sad.
=(
What's about announcing the winners of the contest?
It's annoying when you are in Top 5 of Div. 1 participants, but author announced only winners from Div. 2.
I think, it was on purpose just because of my comment.
Waiting for the editorial! Someone please tell me how to do problem C??
My solution solves the queries offline.
For each row x find the minimum row i, such that the interval [i..x] on some coloumn is non-decreasing.Then iterate through all the queries which end in x and if i < q[x].l , then the answer for the query q[x].order is "Yes" , else it's "No".Thus the complexity is O(n * m + k).
Check my code for better understanding.
About problem E. Many people thought why greedy solution works. The answer is simple: tests are weak.
I wrote my greedy by sorting on bi in non increasing order and ai in non decreasing and failed pretest 4. Then I changed the order on ai to be non increasing too and it passed. I was angry that I did not notice that during the contest. Here is the submission: http://mirror.codeforces.com/contest/777/submission/24979922
I did not notice that property, as it does not work. Here is the counter example, where sorting by ai in non decreasing order gives a better result:
The answer is 6, but my program returns 3. It is a pity that these tests were so weak and so many incorrect solutions to the hardest task were accepted.
This is an invalid input because bi must be greater than ai.
Right. In that case greedy works as you would be always able to cover all coverable ai, with bj.
Edit. How to solve the task with ai <= bi?
Note that if we place some ai = bi ring, we cannot stack any rings more on it (contradiction: bi >= b_(i+1) > ai = bi) So first we solve the problem with ai < bi rings, and process ai = bi rings later.
I think Greedy Works always :)
I faced a nearly same problem as you
24985372 WA on test #22.. Using
>=in sorting.24985387 AC only removing that
=sign :(But I don't know why... Shouldn't I sort in Non-Increasing Order?
The 'less than' operator should follow the strict weak ordering. So '>' is the right choice because it should return false with any two same arguments. See also: http://en.cppreference.com/w/cpp/concept/Compare
Got it .. Thanks :) :D
А разбор будет?
My solution for problem E gave WA, but I can not understand what I did wrong. Here is my approach:
Sort the rings with respect to 'b' in descending order.
Now consider the rings in the sorted order.
For the ith ring, get the maximum height achieved by i-1 rings with 'a' less than 'b' of the ith ring (used coordinate compression and segment tree for this).
Add the above height to the height of the ith ring and store this value for the ith ring.
Maximum achieved height by all rings after all of them have been processed is the answer.
Link to the solution : http://mirror.codeforces.com/contest/777/submission/24974400
click
Thanks...but now I dont understand why Pretest 4 did not cause a problem for me. My solution failed on test 20.
I think because in that test a's are sorted initially in correct order
Разбор этих задач вообще будет?
Nice problemset good work man!!
UPDATE: Sorry...wrong thread...it should be under round 402
http://mirror.codeforces.com/blog/entry/50658?#comment-346176