Доброго времени суток!
31 октября 2016 года в 17:05 MSK (время московское) состоится очередной раунд Codeforces #378 для участников из второго дивизиона. Традиционно, участники из первого дивизиона приглашаются поучаствовать в соревновании вне конкурса.
Этот раунд будет необычным: будет предложено 6 задач и 2,5 часа на их решение. Обратите внимание на необычное время начала раунда!
Хотелось бы сказать большое спасибо Николаю Калинину (KAN) за помощь в подготовке задач, Татьяне Семёновой (Tatiana_S) за перевод условий на английский и Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon, а также за помощь в подготовке контеста и идеи нескольких задач.
Это мой первый раунд, надеюсь, раунд оценят по достоинству.
Разбалловка: 500-1000-2000-2000-2750-3000.
Поздравляем победителей!
Div. 2
Div. 1
Давайте уже 17:05 не называть необычным временем)
"6 задач и 2,5 часа" тоже))
So, Delinur is back as a translator at Codeforces :D
OK, yesterday in the announcement it was mentioned that Delinur translated the problems, today it is written that Tatiana_S did the translation, I want my up-votes back, it's not my mistake :(
I hope your first round will be a great round.
Good luck
Unusual rounds.. unusual rounds everywhere
I'm sure It'll be a very beautiful round <3 _ <3
Solved A,B,C,D :3 Told you it's a beautiful round :D :D
although i was late a bit :3
same room :)
I hope you make next contests on sundays, since most people can't participate on mondays.
I wonder if anyone is going to get raided by treat or trick while competing.
Anyways, Sunday round should be much more better, and I am pretty sure that many people are going to hang out on Hallo... Wait...
I agree, Sunday is the safest option.
I was hoping for special Halloween round, but it seems in vain
I like six-problem rounds, my top 3 best rounds are all six-problem rounds :D
KAN — третий координатор раундов Codeforces?
A bad time for the Chinese...QAQQQ However, happy Halloween!
I believe it's much better than the usual time for the Chinese:)
oh, bl!
Can't play 'trick or treat' on the Halloween EVE.. So sad! :(
Only treat you will get is negative change
i hope it will be a beautiful round
I hope problem difficulties are gradual.
I am interested about your handle. Can somebody pronounce it to me? I have not seen this type of names earlier.
Finally, Happy Halloween contest to all! Hope to see some scary
hardeasy problems :DDamn!!
where is the CF rounds for div1 only
about 40 days since last div1 round
Canada cup was for DIV.1 and DIV.2.
Which part of "div1 only" you didn't understand :\
Finally a regular codeforces round after two weeks. Thanks Kniaz for preparing this round. Hopefully everything will be fine :D
but i dont think it unusual .. because the current three contests are similarly : six problems with two and a half hours .. but i hope i can do better than my previous contests..
Good Luck!
Thanks for this contest!
Does Codeforces plan to change its format (or it has already changed it)? All recent contests have 6 problems and 2.5 hours.
I think it is just a coincidence that recently the problemsetters have sets of 6 problems :)
Possible, but with this one it's 5 Div2 rounds in a row (counting Technocup too) with 6 problems.
Technocup 2017 — Elimination Round 2 after three weeks is just two hours length...
Thank this unusual time i can go to sleep early
Score distribution ?
updated
where is this guy "is it rated" :P
In Problem A the statement says that the grasshopper can jump on vowels of English alphabet, yet the image and the paragraph below the image feature letter Y among as a vowel. AFAIK, Y is not a vowel, but a consonant.
I am not sure if this incorrect translation can be remedied at this point, but please consider any possible steps you may take in order to prevent quite a few people like myself being victims to errors in translation. (there are 4 people in my room who considered the phrase "English vowels" to only mean 'A', 'E', 'I', 'O', 'U')
Did the pretests not cover Y being a vowel? Were you able to hack them?
Yes. Pretests were not having Y. I hacked one such solution.
Yeah, I hacked 3.
I just realised you can continue hacking the same person's solution as long as they're uploading new submissions :(
I was hacked because of 'Y'...
Me too
It said "The following letters are vowels: 'A', 'E', 'I', 'O', 'U' and 'Y'." right below the picture in Problem A. In this https://simple.wikipedia.org/wiki/Vowel wikipedia page it says that vowels can be: "A, E, I, O, U, and sometimes Y".
As it's explicitly written in the statement which characters are vowels as you said, there's no point of arguing about it, everyone should follow the statement in order to solve the problem. Also https://en.oxforddictionaries.com/explore/is-the-letter-y-a-vowel-or-a-consonant.
Чтоб автора пожизненно просили восстановить ответ в каждой задаче.
Why so butthurt dude?
The reason for butthurt 21930212 :)
Educational rounds are really useful!
Dang, I knew I'd seen a similar problem before! I guess that's why you should always upsolve...
Which problem above link refers to in todays contest?
F.
How to solve C?
I use greedy and prefix sums!
I divided A into contiguous blocks mapped to each index of B, such that sum of the block is equal to element at that index in B. Then picked the largest element in the block such that at least left or right of it has a smaller value and then made this monster eat all monsters to its left followed by all monsters to its right, or vice versa depending on which side has a smaller value than the largest element.
ACCEPTED ?
Actually, I didn't finish it in time during contest. I submitted in practice, and I was printing it wrong. Logic is correct though.
Yes your logic is correct.I implemented the same logic during the contest.
You should choose m segments such that i-th segments sum is equal to b[i].
Consider first element of ending array. It must be formed by first elements of original array (else where does first monster go?). So it suffices to solve the problem in the case of ending state a single monster (then apply this to each range by precalculating partial sums). This can be done by identifying a monster of maximum size that is bigger than at least one of its neighbors (if none exists, then solution does not exist), and having it eat everything.
Notice that you can only convert the initial array into arrays which contain elements which are contiguous sums of elements of the first array. Now, in order to generate the procedure, all you have to do is in every subsequence, find the largest element and go left and right to consume all the others (as it will only become larger, it will not create problems). You also have to take care of cases when the largest cannot go either left or right.
Здравствуйте, пытался сделать свой первый взлом! Когда отправил программу-взломщик, получил такой вердикт:Validator 'val.exe' returns exit code 3 [FAIL Expected EOLN (stdin)]; Что это значит? Заранее спасибо!
Тест не подходил под условия (вероятнее всего)
спасибо
how to calculate max vol for k=1 in D
It will be min(a,b,c)/2
PLease tell me how to solve C and D!! I only solved A and B I tried to solve D in O(n^2) bruteforce but it got tle of course....
D is enough to maintain hash of (pairs -> list of third dimension) for all 3 possible pairs (first sort the dimensions for each brick).
Why hash, you need no hash, sort the array and check neighour bricks.
Of course other solutions may exist. Hashing is simply the most natural one.
D
Imagine the shape described by the problem. It becomes obvious that the sphere is limited by the edge that has minimum length. You have block A that you are considering. To use A and B (another block) the value of some area must be the same (both in size of the area and shape). But there's something more: if you put A and B together, you are basically increasing the length of the edge that you didn't use to get the area. So this length that you are increasing needs to be the minimum length of block A and B, otherwise some length you used on the common intersection is already limiting the volume of the sphere and you already have the maximum volume you could get using this union. The max volume in this case will be limited by the minimum between the sum of the edges that A and B aren't using and the minimum edge of the intersecting area (because if the sum is greater than this, now this is the limiting factor of the volume of the sphere).
Now, to get the answer from this you have a vector of (max_area, minimum side of area, side not used in area) and sort it. The blocks that you can glue together are next to each other, so you can easily consider all the unions.
edit: now that I think about it, you just need the dimensions sorted and check if the 2 maximum sides match, but the thinking process is the same.
For problem D: Basic observation is that if you have parallelepiped (lol I copyed it from statement :D) of size a * b * c, then the radius of the inner sphere is min(a, b, c) / 2. Also you can glue two parallelepipeds together only and only if they have two common edges of the same length. After that you should use a data structure like
std::map<pair<int,int>, pair<int,int>>. In this DS you keep the maximum possible 3rd edge length for given a and b edge lengths, after filling this DS you can use a simple loop to get the answer. Complexity isThis is what I did. Failed the system tests. Must have missed something. Did it work out for you?
Failed test case 15.
Did you check if any element in the pair which acts as key for the map is less than the glued dimension's measure?
Pretty much exactly what I did, but got TLE on Test case 32 :(
how to calculate max volume for k=1 in D
For a rectangular parallelepiped of dimensions a×b×c, the radius of the inscribed sphere is
min(a, b, c) / 2.How to solve problem E? Any small hints?
The jumping root is regular, consider current step is right, so we jump right until reaching the first left step(now all the steps we have visited is left), then we jump left until reaching the first right(now all the steps we have visited is right), and so on until jump out, the answer has two parts, here consider the left part(distance we go at left side of current step), (curIndex — leftIndex1) + (curIndex — leftIndex2) + ...= totLeftNum*curIndex — (leftIndex1 + leftIndex2 + ...)
To calculate the answer in O(nlog(n)), precalculate several arrays, lcntUp(number of up steps from left), lsumUp(the sum of every up index from left) and rcntDown, rSumDown. for every step there are 4 cases.
Sorry for my poor English.
I used the same approach and I just wanted to add that the answer can also be calculated in O(n).
My code
Is this you? link
Yes, that would be me :)
Well that's interesting!
Consider position i. Let char be 'U' there. The movement will be oscillatory. You will move to first 'D' above i, then to first 'U' below i, then to second 'D' above i, then to second 'U' below i and so on. I advise just running through an example on paper to see this. So, if you know the count of Us below and Ds above, you get to know whether you will exit from top or bottom. Then just calculate the total distance travelled. The case for when str[i] = 'D' is analogous. So each i can be dealt with in O(1). :)
Code
Tried to hack this solution for Problem B with the following test case.
No initialization done whatsoever in the code. Still no hack :(
The variables are global, so initialized to 0
Typed
if (t&(1>>k))instead ofif (t&(1<<i))in problem F, lost 3000 points...WOW , how could that pass the pretests ?
it should completely change the answer
He didn't pass the pretests. He meant that fixing the line helped him get AC verdict.
Solved D but Just fell short of 2 minutes from submitting C.Need to boost my speed.
only two minutes before the end of the round I realized that o(n^2) solution can pass the pretest for problem D
I could have hacked a lot of participants
BTW, problem C is sucks
However my O(n^2) solution submitted and the result is TLE in pretest 7.
Yeah, my O(n^2) solution also failed on pretest 7. Managed to get it to O(N*log N) but it took another 20 minutes to complete it.
To include Hacks like in problem A IMO should be controversial.
Well I don't know but hacks do change the contest for me so in my selfish opinion hacks should test algorithmic incorrectness . Any other views?
yup,i agree with u.
I agree. It is more of a problem of one's familiarity with English language.
Why would you say that? The statement isn't clear or what? It clearly says which letters are considered to be vowels.
so you have read "and" as "not" ?
I think that on the one hand, the current hacking system is not fair. According to who is in your room, you may hack between 0 and n >> 1 solutions. Getting 0 hacking point or 1000 hacking points may be the result of your luck, more than of your hacking skills.
On the other hand, I'm not sure letting everyone hack anyone would be a great idea. Indeed, we may see one day someone winning the contest with one problem solved and 70 hacks.
What is test 68 on D? I wish I hadn't missed it!
I failed system test on D(test case 14).Any boundary case?
Может скрывать ВК и e-mail участников пока контест идет? Мне в личку написал левый человек с просьбой скинуть код по А (не знаю на что он надеялся)
Можно самому скрыть вроде!
Is there a problem with Codeforces servers? I was repeatedly getting 504 gateway timeout error while trying to submit my solutions during the contest. I was submitting my solutions by uploading the code file. Did not try submitting the code directly though.
Finished C just 2 minutes after contest ended ;_;
I badly needed rating rise
Revenge is a dish best served in the same contest. :)
Good job!
Good for you
I wish someday I can get this feeling
And in the same problem too...
BOOOM The deep meaning of THUG LIFE , BRO :)
It would be very interesting if Div. 1 could have joined this contest officially.
waiting for the result of your submission for problem C is harder than waiting for GOT season 7
How to solve C?
How to solve C ?
I use DP to solve it. DP[i][j] = if i ~ j's number can merge then DP[i][j] = sum( i ~ j ) else -1 if( DP[i][k] != DP[k+1][j] ) DP[i][j] = merge(DP[i][k], DP[k+1][j])
time complexity is O(N^3)... little tight
UPD) Source : http://codeforces.me/contest/733/submission/21933533
There's a O(N) solution:
To get the first wanted weight you need to make some combination using the initial values from the first to some where the sum of all the weights in this interval is the value wanted.
You do the same for the other wanted weights. If in this process the sum is different than the one you want when it ends (when your interval reaches the end or when the sum is greater or equal to the one wanted), there's no answer. If this process ends and there's not enough groups there's no answer as well.
Oh, I read it after solve it O(N), :) I tried O(N) solution using stack, and solve it. (source : http://codeforces.me/contest/733/submission/21955664)
pl0892029 your solution looks very interesting....can you explain your print function ?
plzz explain your code
Hmm... I can't explain well, but try it.
Let's begin. testcase is here.
I intend DP's value is it.
focusly, DP[3][5] is derived it's sub-DP value.
why not DP[3][3] + DP[4][5], because V[4] and V[5] is same value 2.
In this context, let's calculate DP[3][4]'s value.
so generally dynamic formula is
print function is similar binary tree's postorder traversal.
while calculate DP, we save it's k value. my variable name is PATH.
and call print. print is trace it using PATH.
I think it's solution is Unintuitive. other's solution is more helpful. :) ... Haha..
In D, for the second sample case, I printed
2
5 1
and got WA. Why? The statement mentions I can print in any order.
It might be an issue with spacing, for example writing "2 \n" instead of "2\n"
I do that all the time. This is the first time I got WA.
Then I changed 5 1 to 1 5 and got pretests passed. Took me 10-15 minutes, because I thought it's some other serious bug, and test case 2 is different from the second sample case.
It costed me C.
simple rule can help you in all your life :
you're always wrong and the statement is always right
I agree with you.
But life's a little difficult when the checker doesn't agree with the statement.
http://codeforces.me/contest/733/submission/21938356 looks like you didn't print 5 1 huh
Which is funny, because it prints 5 1 when I tested it.
You can test it on ideone or your local compiler. You'll see 5 1
Exiting moment for me ! Waiting eagerly to see the final verdict of my submission on D. Because, after a long time I am able to solve D !! If it got AC, it will be my 2nd time to be able to solve D in contest duration !!
Update: My solution for D is Accepted finally !! I am so much happy and excited that I can't express it !!!
Update2: After rating change done, I became Cyan(Specialist) from green(pupil) ! Exitement overflowed !
Congratulations!
This is my room:
I'm not very optimistic on passing the system tests on problem C :((
EDIT: I became a victim of test 13 too :(
Yeah same, it's kinda nerve wracking.
test case 13 is killing everyone !!
Am I the only one here who is dying to know what is test 13? (Didn't take part in the contest, but read it and assumed there it should be something really obscure)
I've seen a lot killed by test 11 too
Good from tester perspective to have tricky test cases just in the beginning so that if some solution fails it will fail immediately and don't waste time on server by passing 90 cases and then failing on 91st test case.
Unlucky 13
[submission:http://codeforces.me/contest/733/submission/21935362] why did this fail ? :/
Ignore
What ?
Ignore
shouldnt answer be 1\n 1
Yes you are right, both answer are correct
yes but radius of inscribe sphere will be 1 which is also for 2 2 2
http://codeforces.me/contest/733/submission/21931658 can u tell where i am wrong. i failed system test on case 14
Codeforces users now : I think they wait something
WOW!! actually the first official participant in the contest is Abdelfatah_Elsisi the president of Egypt :V :V
i think he's a cheater .. he got WA on D after 1 min of solving C
i think they are two or three people solving on the same handle
Give me your full name and we'll see about that.
you can find it by reading my handle
smart
It's
I think all the government are solving on the same handle :V
Thanks fady for your support, I'll make sure to visit Syria soon to meet my fans there.
You welcome man !! You have many fans here of syria :D P.S. it's fadi not fady -_- smart president
.
I add a define only when I need it :)
and you solve problem c in 1 minute too ??
I use predefined 'mp' and 'make_pair' in same code sometimes,am i a schizophrenic now? same with 'pb' and push_back
define mp make_pair — I use it too.
should I be very optimistic ??
For those who failed problem C: I guess 13th test must be something like
i. e. some valid yes-case with extra monsters appended to a, so you also need to check whether sum of a equals sum of b (or do some other validity check). Pretests didn't cover it.
In my room 3 participants failed on test 11, including me
UPDATE: My C failed just because I forgot to reset a varialbe ...
During the contest I was like "Oh, these guys don't check if the current index is still less than or equal to N, let's hack them" (3 successful hacks). And after getting WA #13, I saw that my code checks if the index is less than or equal to M, not N (in array B instead of A) :D
Some scary idea for Halloween costume:
Wake me up when systest ends.
Wake up
Thanks bro. Wake me up when ratings change :)
Wake up! It's happens! )))
Thanks Bro for waking me up.
For problem C you can check this hack test:
4
1 2 3 4
3
1 2 3
Answer should be "NO"
LOL. Thank god I first checked if sum of array a and b are equal. I still can't say it will pass. :/
My solution fails this. :( Thanks by the way. Now I don't need to wait for the system testing.
After seeing this test case I got AC now. Just had to add one line that sum(A)== sum(B)
I am feeling that MikeMirzayanov turned the last 20% of automatic system test to manual system test :\
Submitted solution for problem C at 2:29:59..now just hoping it passes the system tests. :)
Happy Halloween ? Test 13 Again :/
Both C and D failed on test 13.Such a Halloween theme round for me. :D
That feel when in the phrase
Help Zahar choose such a present so that Kostya can carve a sphere of the maximum possible volume and present it to Zahar.you took attention only to wordsmaximum possible volume and present itand decided that goal is to maximaze volume of parallelepiped, not sphere... =(Bro! plz don't wait for the rating change :P
How does this solution pass for problem C? Shouldn't variable sum2 be of type long long as elements in B are ~ 5*10^8 and maximum 500 in number .
Elements in B are 5*10^8. These elements are sums of elements in A that are 10^6.
You didn't get me. number of elements in B are maximum 500 , maximum value of these can be 5*10^8 . maximum value variable sum2 can get is 25*10^9 =2.5 *10^10. which overflows integer range. ( Look at variable sum2 in the code )
Indeed, interesting http://codeforces.me/contest/733/submission/21947301
It doesn't pass without sum2 but it would need an incredibly specific test in order to make the overflowed sum match sum1 in order to make a difference.
I think it passes because he checks for !=
If sumof A != sumof B, then it doesn't really matter that one of them overflows, because if they are indeed equal, they won't overflow.
Такой себе контест, какой смысл делать претесты если все равно решаешь вслепую?!
Как минимум для того, чтобы не прогонять ТЛ-и на систестах
how to solve c ??
Watch first number in array b, say it's 10. Iterate over array a elements until their sum is 10. If their sum is less or more then it's not possible. If it's 10 then you need to find an element in array a among those you checked that will eat all the other elements. It's one of the maximal elements, consider some tests on a paper to understand which one you have to pick. Once you are done with first number in array b, watch the second number and do the same stuff...
That feel when you solve C and D and get a wrong answer at problem B.
Butthurt noobs who didn't solve C downvote this.
Any idea why this fails for F? http://codeforces.me/contest/733/submission/21947192The value of minimum sum matches, but it says "wrong answer lyamzikov shortage" i also checked that it is printing n-1 edges...}Edit: NVM, Got it! I forgot that there could be multiple edges b/w same pair of vertex in graph too
I think "lyamzikov shortage" means that you use more coins than you're given while lowering drivers' dissatisfaction :)
WOW!!
Abdelfatah_Elsisi submit problem D at 17:30 and submit problem C after exact one minute :|
It's called cheating.
:)
Maybe he wrote two programs, checked them and then sent?
really nigga !?
So he wrote C and D in less time than dreamoon_love_AA and uwi? seems logical.
and maybe he is the flash and he accidentally forget to pretend that he is normal ?
احلوف!!!
In fact,he might meet the following condition. In a contest,I wrote the code of problem C first but I failed to debug the code. Then I gave it up and wrote the code of problem D. After I sent the code of D,I continued to debug the code of C and sent the code of C after debugging in little time.
For Problem C :
Why This Answer Considered as invalid for testcase 1?
YES 4 2 L 1 R 2 R 2 R
Yes 4? What is 4?
For Problem C On testcase 1 :
Why this is considered as invalid? Input :
6 1 2 2 2 1 2 2 5 5
My output : YES 4 2 L 1 R 2 R 2 R
You don't have to print the "4".
Ouch, i just realized that. Thanks for answering! It's a funny mistake though
When will be editorial?
Got C and D wrong by two very small and silly mistakes.... :(
Got them ACed just after the contest ended :P
Same here. :)
Can I download the test cases for a problem, because my solution is failing on a test case which very large and is not displayed completely in the browser ?
Why rating change is so delayed ?
Update: I just commented and reloaded the page and saw that rating change is published... !
Rating change done :)
As soon as I completed commenting, rating change is done !!
I heard that 2Pac didn't come back in 2014 because he was waiting for ratings to be updated.
In problem E, why am I getting RTE on CF, while its working fine on ideone?
There are various types of RE. It'd be good if the judge can tell us which RE it is.
what's the procedure of the check against repetitive code？ one of my friend Hu_huhuhuhuhuhu used other's code on problem D(despise him!),but after systest his score was still less than me. but i got -8 on this round(now my rating is less than him), he escaped from decreasing！ it seems if someone's rating will decrease in a round，copy other's code can avoid it. that's rediculous!
Something fishy going on with the judge/checker for D.
For D, what can we do if we are asked to find out the maximum volume? As a * b * c may be as large as 10^27, how can we compare two volumes without BigInt?
p.s. I didn't work out D during the contest because I didn't read the problem carefully and thought it was finding greatest volume. Don't be like me.
the answer can be simple as the min(a, b, c) / 2
You can use log values for comparison
Thanks, maybe, I've tried, but consider this: 999,999,999 ^ 3 and 1,000,000,000 * 999,999,999, 999,999,998. It seems that even using log will return the latter is bigger.
Although this isn't what was required in this problem, but you can simply use double for comparing huge numbers like this.
if((double) a1 * b1 * c1 < (double) a2 * b2 * c2) { // my code }Thanks for your attention.
According to the following code, with given a1, b1, c1 and a2, b2, c2, it gives a1*b1*c1 == a2*b2*c2.
Notice that
a1 * b1 * c1 == a2 * b2 * c2won't cause you any problems even if they overflow because the overflowed values will probably be equaled if the real values of the multiplications are equaled. But to be on the safe side, use doubles.Orz hahaha
;|
any hints about problem E?
Can you determine the which side will you fall off in O(1) with preprocessing? If you can, then can you use this observation tell how many "cycles" you have to go through before falling off?
Somebody please compare these two submissions and tell me wtf is going on!!!! One is failing on test case2, other at test case 36.
21957079 21957040
spoiler : they're EXACTLY the same!!!
For Problem D,
First of all, for a parallelepiped with sides say l,b and h ,the radius of sphere inscribed in it will be r = min(l,b,h)/2 . So here, to maximize the volume, we need to maximize the radius r. That is we need to maximize the minimum side of parallelepiped.
Now, two parallelepipeds should have atleast two sides identical in order to join them. Lets sort the sides for a parallelepiped in increasing order and do this for all parallelepipeds. After sorting, lets say the sides of a parallelepiped are l,b,h such that l<=b<=h . Now the observation is we need to match only the larger sides i.e. 'b' and 'h' of this parallelepiped with larger sides of other parallelepipeds so that the minimum side of the resulting parallelepiped can be maximum. Why? Because , lets assume we match 'l' and 'b' values of two parallelepipeds then for the resulting parallelepiped the minimum side will remain 'l' . The same thing happens when we match 'l' and 'h' values of two parallelepipeds. But when we match 'b' and 'h' then there is a chance that now the 'l' side of resulting parallelepiped will be greater than 'b' or 'h' as a result our minimum side will become 'b' now.
For help refer to my solution, 21956827
Hope this helps :)
And sorry for my bad English!
Ui bai kho qua chiu thoi.
Haha co cl y bai day toi lam 1 dam.
When will be the editorials published??? Nice problemset Hope they publish it ASAP
For problem F, after viewing some other's code. I think I understand it. First, we are actually finding a spanning tree of the graph and are decreasing weights of some of the edges of the tree to get the answer.
Suppose now we happen to know the spanning tree, we can simply invest all of our money into only one edge, whose C is the smallest among edges of the tree, to reduce total 'disatisfaction' as large as possible. Note that we may not be able to invest in any other edge by doing so.
But how can we find the spanning tree — we only know minimal spanning tree algorithm.
Well, let's turn our attention to another point. I mentioned that what you have to do is just to reduce the weight of only ONE edge. So what about enumerate through edges we are going to reduce! Actually, the final spanning tree may be very similar to the minimal spanning tree — intuitively, apart from the edges to reduce, other weights of edges of the spanning tree must be as small as possible. So, suppose we now have the minimal spanning tree T.
And now we want to plug an edge (u, v), which may or may not be in the tree, into T. The only block, if (u, v) is not in the T, is the only path from u to v in T. And if we remove one of the edge of the path from T and plug (u, v) into T, we'll got another spanning tree.
So, you may just remove the edge with the largest weight on path from u to v and plug E into it you will get the answer. But how to find the path from u, v and find the maximal weight along the path? You'll need LCA(Lowest Common Ancester) algorithm, which preprocess the minimal spanning tree.
Sorry for my poor English. But typing solution out really helps me organize my thought.
I was wondering why we just need to reduce the weight of only ONE edge. As you mentioned "what you have to do is just to reduce the weight of only ONE edge".
Thanks.
Because the weight can be negative
Suppose you want to reduce weight of m edges of a spanning tree, let's number them 1, 2...m, you wan to reduce each edge by ui times, and each edge costs you Ci for reducing once. Then, the result you get is tot - u1 - u2 - ... - um, where u1 * C1 + u2 * C2 + ... + um * Cm ≤ S. Suppose now you select an edge with minimal C, and you can at least reduce u1 + u2 + ... + um times, because: C ≤ Ci and u1 * C + u2 * C + ... + um * C ≤ u1 * C1 + u2 * C2 + ... + um * Cm ≤ S. So reducing only one edge is at least as good as reduce many edges.
And intuitively, for a fixed spanning tree, you can find the edge with minimal C, then you can reduce the 'dissatisfaction' of the whole tree by S / C. If you select edges with bigger C, you may not be able to reduce the 'dissatisfaction' that much.
As we don't know whether the edge we are working with is the edge with minimal C, we want the w of remaining edges to be as small as possible, that's why we are replacing edges in MST.
For the problem C733C - Epidemic in Monstropolis Although my code is Accepted, but if use this data will wrong answer
23
3 2 1 3 3 3 1 1 2 1 2 1 1 1 2 2 3 1 2 3 3 3 3
5
6 16 5 5 15
Because my answer is NO and the right answer should be "YES" So is the data have BUG? Hope a reply!Thank you!@Kniaz
The answer my program gives is YES 1 R 1 R 4 R 4 L 3 L 2 R 2 R 2 R 2 R 6 L 5 L 4 L 5 L 7 L 6 L 5 R 5 R 5 R You can try it. And my code
I ran this testcase and my AC solution gave NO. I freaked out until I realize the testcase lacks number K (number of elements in B). You scared me :(
I am so sorry! Just now surely lack a "k", you can try again. For this data my accepted program gives "NO" but I think should be "YES"...
wait for my online judge
Hi! Can you give me a test example where this does not work:
https://gist.github.com/Vitosh/01e3ce215de5ecb70b42cafc2dd2b8d0
Its from http://codeforces.me/contest/733/problem/B and I think it should be working. However it breaks on test 10 and I cannot see it. Thanks!
You are missing out so many things:
why the "&&(long_left>long_right)" conditions? Sometimes there are more right legs and you need to reduce them to achieve max beauty.
maximising the delta of legs do not guarantee maximum beauty, think about it.