Codeforces Round #484 (Div. 2)

6 лет назад, # |

-35

Wish high ratings to all.

→ Ответить

legendjohn9999

6 лет назад, # |

+130

I hope this round won't be like that

→ Ответить

DanAlex

6 лет назад, # ^ |

Guess I'm a faithful guy...

→ Ответить

eisen_shinzou

6 лет назад, # ^ |

Hacking is such a ridiculous thing, maybe good for some guys but unfair... But not always bad, the stress and excitement is cool, agree?

→ Ответить

prodipdatta7

6 лет назад, # |

-11

better starting time for Bangladeshi contestant....

→ Ответить

the_badcoder

6 лет назад, # |

Can't open problem C and D. Showing Error !!

→ Ответить

SonDinh

6 лет назад, # |

-12

Комментарий удален по причине нарушения правил Codeforces

→ Ответить

6 лет назад, # |

+66

How to solve F?

→ Ответить

KhaledKEE

6 лет назад, # ^ |

← Rev. 4 →

+26

If we look at the dfs tree of the graph:

If we got any backward edge (an edge connecting a node to one of its ancestors) then the answer must be one of the nodes between the two endpoints. If there is not such edge then answer is -1.
If we got another backward edge then we need to find the intersection (or remove nodes from solution which are ancestor of the other node or are not ancestor of the current node). For example, 1 -> 2 -> 3 -> 4 is a cycle, and 2 -> 3 -> 5 is another cycle. Both 4 -> 1 and 5 -> 2 are backward edges.

If we got a cross edge (edge connecting a node to another that is neither its ancestor or descendant) then if the other node is in cycle and topmost node of the cycle is a parent of the current node, we need to erase the nodes that are neither parent to the current node nor descendant of the other node. For example, 7->4 is a cross edge.

Submission as a reference: 38382900

→ Ответить

Jakube

6 лет назад, # ^ |

Hi there, I am struggling hard with this problem. So I studied your code quite a bit, and found a mistake in it. Try the following test case:

Solution should be 4, but your program answers -1.

The last edge 1->6 in this test case is a cross edge. So you have to delete all vertices on the cycle 1->2->3->4->1 that are anchestors of 6, but not of 1. Finding the lowest anchestor of 1 on the cycle works (it is 1 itself). But finding the lowest anchestor of 6 doesn't work, since you argument with the height h of 6, which has nothing to do with the ancestors.

→ Ответить

saihemanth9019

6 лет назад, # |

How to solve problem D?

→ Ответить

6 лет назад, # ^ |

You can brute force for all posible k using sets in O(nlogn).

→ Ответить

ChickenInKitchen

6 лет назад, # ^ |

what is the test 5 ?

→ Ответить

Vicennial

6 лет назад, # ^ |

I used co-ordinate compression. I got WA TC #5 when I was printing K in terms of the compressed value instead of the real value.

→ Ответить

baobab

6 лет назад, # ^ |

← Rev. 3 →

I got WA on test 5 for a different reason.

My answer: 57209037

Judge: 45567032

My algo iterated a values as candidates for k. When a is sorted by size, these values are consecutive in the input:

57209037 (found best solution at this value)

45567031 (found worse solution at this value)

Obviously, the best solution can also be found at 45567031+1.

→ Ответить

Wolverine_07

3 года назад, # ^ |

← Rev. 2 →

-10

Can you please tell me what's wrong in my code 107085887. I am getting WA on test 36 !!

UPD — Solved It :))

→ Ответить

baobab

6 лет назад, # ^ |

If anyone needs complete test 5 input, I've put it here: https://pastebin.com/vHuv6LE4

→ Ответить

saihemanth9019

6 лет назад, # ^ |

What is stored in the sets? Also... Brute force requires to iterate through the whole array right?

→ Ответить

karin0

6 лет назад, # ^ |

← Rev. 3 →

We can store lengths of locations and when they are reached, with a array or bst like std::set or std::map. To do this we can sort the sequence and enumerate k from 1 to n, using disjoint sets.

→ Ответить

Phanix

6 лет назад, # ^ |

Can you elaborate please?

→ Ответить

karin0

6 лет назад, # ^ |

based on this we can simply use an array instead of std::set, thus we can do this step in O(n).

→ Ответить

6 лет назад, # ^ |

And of course k can only be equal to a[i] + 1

→ Ответить

sdssudhu

6 лет назад, # ^ |

I got the k=ai+1 part during the contest but can you tell me about how to brute force ??

→ Ответить

6 лет назад, # ^ |

← Rev. 4 →

I have one set to store segments of elements less than k and one multiset to store lengths of all segments in first set. Then i add all a[i] from the smallest to the biggest, where current k = a[i] + 1. When you add one there're three scenarios: it forms a new segment, it unites with one segment, it merges two segments together. I think it's clear how to do updates and how to keep multiset of length.

→ Ответить

sdssudhu

6 лет назад, # ^ |

Oh thanks I get it.

→ Ответить

6 лет назад, # ^ |

Alternately, start with the segment [1...n], and add a[i] from largest to smallest. This way, it's guaranteed that the only operation happening is breaking up an existing segment, which makes implementation easier.

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

So when at some step segment set size is begger than it's sizes at all previous steps and when all elements in multiset are equal I update the answer with a[i] + 1.

→ Ответить

6 лет назад, # ^ |

I thought of this, forgot to implement it because the samples didn't need it, and managed to implement it with about 10 seconds to spare in the contest.

...Needless to say, I wasn't able to submit in time :(

Ah Codeforces, thou art a cruel mistress...

→ Ответить

0101-1001

6 лет назад, # ^ |

+26

Maintain a dsu of active indices and process the indices with increasing order of values. At each step, let cur_k be value + 1. Check if neighboring indices are active and accordingly merge them. Also maintain the count of total active indices for a given size of set. Update the answer if the current size is equal to total active indices.

→ Ответить

6 лет назад, # |

+61

the solution to problem c was available at https://www.geeksforgeeks.org/maximum-edge-removal-tree-make-even-forest/

→ Ответить

dheeraj_1997

6 лет назад, # ^ |

+12

I took 30mins to solve it. Authors need to be more cautious before preparing a problem. :(

→ Ответить

__noob__

6 лет назад, # ^ |

striver_79 try to solve problems rather than searching for problems

→ Ответить

6 лет назад, # ^ |

haha, if I was to search for the problem, I would have got all the pretests passed in 5 minutes. I tried for an hour, but when I did fail for it, then I was searching for the DFS part when I came across it. Learn to observe before saying something. :)

→ Ответить

__noob__

6 лет назад, # ^ |

← Rev. 2 →

Looking for the dfs part and then came across that nice explanation btw what are you looking in DFS. "WHAT TO OBSERVE". I also type DFS in google but I didn't came across that question maybe your browser is a legendary one.

→ Ответить

6 лет назад, # ^ |

I do not owe an explanation to you that is for sure buddy. And stop blaming someone for pointing out a link which seems similar. :) I guess you learn everything without googling. You got so much of inner talent :)

→ Ответить

__noob__

6 лет назад, # ^ |

But learning is not googling in between the contest. In between try to apply your own mind.

→ Ответить

papa-ka-para

6 лет назад, # ^ |

grab popcorn :P

→ Ответить

subhamastoo

6 лет назад, # ^ |

*grabs

→ Ответить

dummkopf

6 лет назад, # |

← Rev. 2 →

Problem E can be solved by the fact that this rectangle can be mirrored adjacently on the coordinate plane.

No, I didn't solve it.

I've done a similar problem in Google Foobar. If I had been given 40 mins I could've solved it. :(

→ Ответить

madmax

6 лет назад, # |

← Rev. 2 →

What is the 6th pretest in C?

→ Ответить

azaxnoot

6 лет назад, # |

+38

Problem C is available at Hacker Rank: Your text to link here... . Check this out..

→ Ответить

alwerty

6 лет назад, # |

+11

I read "connected components with equal size" instead of "even size" in C. Yikes

→ Ответить

Morphy

6 лет назад, # |

+23

Feedback:

C: nice

D: A bit ambiguous, I needed two clarifications to understand it.

E: The mirroring trick is very standard. I think I've seen a very similar (maybe the same) problem in uva.

→ Ответить

hell_hacker

6 лет назад, # ^ |

C was a direct copy from geeks for geeks

→ Ответить

NewNick

6 лет назад, # ^ |

Mirror trick? Can you say sth? I solve it using Chinese remainder theorem.

→ Ответить

Redux

6 лет назад, # ^ |

Do you know if there's a name for the mirroring trick? I've seen a solution that used it in the past, but I wasn't able to understand it then. I'd like to find more information about it and learn it now.

→ Ответить

Alireza

6 лет назад, # ^ |

just consider each side of the table as a mirror and copy the table based on its picture in the mirror. So anytime the ball hit the side it enters the new table and continues its direction.

→ Ответить

6 лет назад, # ^ |

← Rev. 3 →

I don't understand what algorithm follows this. You calculate the intersetcion point of rectangle and a straight line. If you hit the origin or a corner, you are done. If you hit the wall, you reflect the whole rectangle and keep going.

You repeat the above 10^9 and tle.

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

+20

The point of the reflection isn't to simulate the process: that can be done without the reflection at all. The point of the reflection is:

You can now travel in a straight line
You get generalized coordinates for the corners: for example, using the labeling in Morphy' picture in the other comment, point A will have coordinates (2mk, 2nl) for integers k, l.

You can get similar generalized coordinates for the other 3 corners, and then it's simply checking whether integers k and l exist such that the point given by them lies on the line you have, in the direction you want.

→ Ответить

NAbdulla

6 лет назад, # ^ |

Can you please provide a resource link to learn it? Thanks in advance.

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

I'm sorry, but I don't have an online resource for this sort of thing.

Given the context, I'm pretty sure that there'll be a few problems of this type discussed on AOPS, so look there maybe?

To be honest, this is my first time seeing the reflection being used in a coding problem. I've only used it in maths problems before, but it seems like a nice Olympiad problem trick, so AOPS seems like the place to look.

I'll look around a bit and see if I can find something more concrete.

→ Ответить

NAbdulla

6 лет назад, # ^ |

Thanks, again. :)

→ Ответить

AnishG

6 лет назад, # ^ |

This link might be helpful for the proof and solution of diophantine equations.

→ Ответить

Morphy

6 лет назад, # ^ |

+78

→ Ответить

-_-_-

6 лет назад, # ^ |

← Rev. 2 →

There is a thread in below link which explains the similar case

Source: https://math.stackexchange.com/a/2295371

→ Ответить

Alireza

6 лет назад, # ^ |

I agree with you and saw a couple of problems like E. (e.g. in Google foobar) I'm wondering why did I read it at the end of contest! :-/

→ Ответить

6 лет назад, # |

I used tree dp to solve C but now i find out that there's some simple solution -_-

→ Ответить

lessmeaning

6 лет назад, # ^ |

dp solution is pretty simple too

→ Ответить

Bobrosoft

6 лет назад, # |

-29

Очень расстроила задача F. В ней всего в одном месте неявно указано, что граф ориентированный («дороги односторонние»), после чего никаких упоминаний или рисунков со стрелочками или любых других намеков на ориентированность нет. И тесты из условия тоже очень легко воспринять за неориентированные, причем код для неориентированного случая их проходит. :(

→ Ответить

KAN

6 лет назад, # ^ |

+63

Дороги в Брагинске односторонние
будут продолжать ездить по односторонним дорогам
количество перекрестков и односторонних дорог
начало и конец i-той односторонней дороги

→ Ответить

Bobrosoft

6 лет назад, # ^ |

+15

Перечитал. Действительно, все так, не знаю, как я все это просмотрел. Приношу искренние извинения составителям.

→ Ответить

P_Nyagolov

6 лет назад, # |

+24

So are you sure what you want us to find in D is what D's statement says?

Thus, in the sequence of n days we can find consecutive nonempty segments when the shark traveled the distance less than k in each of the days: each such segment corresponds to one location.

Shit in bold's true but it it's not true that each location has a corresponding nonempty set.

Now getting back to what the problem asks for:

Find such integer k , that the number of locations is as large as possible.

And at the same time, what you want us to do is find the k which maximizes the number of nonempty sets, not the number of locations.

Even after the announcement, which was too late anyway, nobody bothered to actually update the statement.

→ Ответить

Redux

6 лет назад, # ^ |

This is because if a shark travels 2 days in a row, he will still be at a new location on the day in between, correct?

→ Ответить

dheeraj_1997

6 лет назад, # ^ |

After reading the problem statement I thought the answer to this test case 8 1 2 7 3 4 8 5 6 should be 0 as it satisfies all the conditions asked i.e 1) the shark was in each location the same number of days, 2) the number of locations is maximum possible satisfying the first condition, 3) k is smallest possible satisfying the first and second conditions

→ Ответить

Azurey

6 лет назад, # ^ |

← Rev. 2 →

I have the same confusion regarding this problem (but not anymore). Let me help clarify this. Assume the answer is k, one location is counted as non-empty consecutive segment which every number in it is strictly lower than k.

For first sample case, if the answer is 7, the number of location is 3, that is {1,2}, {3,4}, {5, 6} and valid because each segment size is two. If you choose 0 as the answer, the number of location is zero. So there's a better answer than 0.

→ Ответить

Isfandiyor

6 лет назад, # |

+23

Happy Ramadan holiday to all. I wish happiness and health to everyone.

→ Ответить

12iq

6 лет назад, # |

+25

Было бы здорово, если б люди, знающие задачи, не сабмитили код во время раунда. А то всякие с 300icq интеллекта засылают верное по F на 4ой минуте, после чего создается стойкое ощущение, что можно пихнуть хрень и кода должно быть мало.

→ Ответить

300iq

6 лет назад, # ^ |

+36

Задачи раунда я до начала не знал, если ты об этом

Ну и я хотел написать раунд полностью (а зарядка ноута, как оказалось, не хотела), и не видел смысла писать решение и так известной мне задачи

→ Ответить

12iq

6 лет назад, # ^ |

-26

Ты за 4 минуты 3-4 экрана набираешь? Мое почтение!

→ Ответить

GreenGrape

6 лет назад, # ^ |

← Rev. 2 →

+16

Тебе же написали, что это известная задача

Вроде несложно догадаться, что ее просто скопипастить можно

→ Ответить

6 лет назад, # |

← Rev. 4 →

This statement didn't exist at the beginning of the contest. My solution was hacked because of it. and there was no clarification about it!!!!!!! AGrigorii [ ]()

→ Ответить

ajecc

6 лет назад, # ^ |

it did exist

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

+16

The If statement didn't

→ Ответить

Emsawy

6 лет назад, # ^ |

← Rev. 2 →

+17

ajecc No, it didn't exist.

→ Ответить

6 лет назад, # ^ |

MikeMirzayanov

→ Ответить

KAN

6 лет назад, # ^ |

+26

Actually we missed initially that the note was incorrect for n = 2. The mistake was fixed a few minutes before the round, as soon as MikeMirzayanov spotted it, and the update was pushed from Polygon to CF. It takes some time, but for me the statement opened a minute before the contest already contained the fix, so I decided that everything was ok and I did't have to make an announcement. It turned out that for some people the old, cached statement opened without the fix. Luckily almost everyone understood what we meant correctly.

→ Ответить

6 лет назад, # ^ |

-13

Till I submitted my solution ,the fix didn't exist. I wrote my solution based on what I read in the statement. It wasn't my mistake.

→ Ответить

6 лет назад, # ^ |

You can`t re-test only A problem without test with size = 2? I think it would be fair

→ Ответить

6 лет назад, # ^ |

-22

So this is over and my rate decreased beacause of a mistake which is not mine.

→ Ответить

notking

6 лет назад, # ^ |

Stop crying over dumb shit. Mistakes happen and this contest is not the end of the world.Also its just -20 which can be recovered very easily.

→ Ответить

6 лет назад, # ^ |

As for me, this worsened my result by 45, but I totally agree that this is just a rating, but it's not very pleasant either

→ Ответить

swami777

6 лет назад, # |

-9

A question copied directly from geeksforgeeks, wtf ???? Contest should be unrated.Its a big disgrace.

→ Ответить

6 лет назад, # ^ |

+14

The practice shows that it won't be unrated. There was a case when absolutely the same problem appeared twice even on codeforces itself but the round was rated.

→ Ответить

hell_hacker

6 лет назад, # ^ |

If I am not wrong it was in an educational round, in which the ideas can be common. And it did not affect many div 2 coders. I might be saying this since I performed bad in the contest. But still C was just google and first link and it shouldn't be the case.

→ Ответить

6 лет назад, # ^ |

I think there were plenty of "just google and first link" cases too. But still I think we should let coordinators decide whether it's fair or not.

→ Ответить

https://www.geeksforgeeks.org/maximum-edge-removal-tree-make-even-forest/

6 лет назад, # ^ |

← Rev. 2 →

I have seen many times(I guess at least 3) where exactly same problem was in other contest, but mostly all of such contests were rated.

→ Ответить

rsFalse

6 лет назад, # |

Was not able to open all problem statements in one window :( Bug

→ Ответить

f2lk6wf90d

6 лет назад, # |

Does this solve F? https://www.quora.com/Given-a-strongly-connected-component-can-you-determine-in-linear-time-if-the-removal-of-a-single-node-turns-the-SCC-into-a-directed-acyclic-graph

→ Ответить

-emli-

6 лет назад, # |

How to solve C?

→ Ответить

rahul_iit

6 лет назад, # ^ |

→ Ответить

Mr_Emrul

6 лет назад, # |

+17

o.O

→ Ответить

6 лет назад, # ^ |

+14

I think only his last solution got hacked, and all previous solutions were marked as hacked.

→ Ответить

tantam75

6 лет назад, # ^ |

did he cheated using clone account?

→ Ответить

Hd7

6 лет назад, # |

What topic should i learn to solve C div2?

→ Ответить

hackerwizard

6 лет назад, # ^ |

You should know basic graph theory(specially dfs)

→ Ответить

Alireza

6 лет назад, # ^ |

for problem C, just learn how to Google the statement!

→ Ответить

rsFalse

6 лет назад, # ^ |

...and bfs too. I solved with bfs

→ Ответить

Hd7

5 лет назад, # ^ |

Today, I solved it,,

→ Ответить

prodipdatta7

6 лет назад, # |

← Rev. 2 →

Almost same as today's Problem C Is there any difference conceptually ???? May be it is not what the contestant expect from the problem setter..

→ Ответить

calier

6 лет назад, # ^ |

← Rev. 2 →

+16

In the yesterday contest, solution for C was also in Wikipedia.

→ Ответить

6 лет назад, # |

Капец в А там же написано было, что не может 1 и последнее место быть соседним, а потом только же добавилась приписка, что n != 2?? Так же не честно... Если я не прав, напишите.. странно.. разве я мог не увидеть..

→ Ответить

moskalenco_a

6 лет назад, # ^ |

← Rev. 2 →

n = 3, 101, вот тут 2 единицы соседними не являются

n = 2, 11 а вот тут являются потому что n = 2(ваш КЭП)

Т.е условие говорит что первое и последнее место являются соседними только в одном случае — когда n равно 2.

→ Ответить

6 лет назад, # ^ |

Изначально, насколько я помню условия что первый элемент и последний не соседи было написано так, а потом добавили что это не так при n == 2

→ Ответить

Ralsei

6 лет назад, # ^ |

Не знаю, зачем ты это объяснил, это очевидно. Проблема в том, что пояснения про случай n = 2 не было в начальном условии, а когда оно добавилось, не было кляра. Конечно, глупая описка, но кого-то могло ввести в ступор.

→ Ответить

dohchuk

6 лет назад, # |

чё-то изи

→ Ответить

JABAIY

6 лет назад, # ^ |

← Rev. 2 →

сейчас бы падать, на как ты говоришь "изи" контесте. А так контест очень даже не плох

→ Ответить

rr459595

6 лет назад, # |

+24

How to solve C if it would have been a graph with cycles ?

→ Ответить

6 лет назад, # ^ |

-18

tree hasn`t got cycles

→ Ответить

rr459595

6 лет назад, # ^ |

← Rev. 2 →

I know that. I am just asking how would one go about solving the problem if it would have been a graph with cycles as the approach used for solving the tree one will not work here.

→ Ответить

6 лет назад, # ^ |

-11

Sorry, I did not understand correctly what you mean

→ Ответить

Shutterbug

6 лет назад, # ^ |

← Rev. 5 →

-8

I may be wrong but in case of undirected connected graph we have to consider only those edges which if removed results in more than one connected component otherwise clearly if removal of an edge does not divide the graph then answer depends on n is even or odd. Now for the previous one you can have a look at bridge in a graph --> https://www.geeksforgeeks.org/bridge-in-a-graph/ Removing such edges and doing the same what we did in actual C question should do the thing.

But Edges might be of order which does not satisfy the constraints if n is 1e5.

By doing the same thing (which i wrote above) i mean that edge should be removed only if it divides two parts in even number (each).

→ Ответить

rr459595

6 лет назад, # ^ |

The approach seems fine but I think finding out Bridges and removing would give "minimum" number of edges required for deletion and not "maximum".

→ Ответить

Shutterbug

6 лет назад, # ^ |

-8

No removing bridges does not govern whether we get minimum or maximum edges. When i say that you remove edge only if it disconnects the graph and both sides nodes should be even. So automatically all the edges which satisfy this property will get counted and that's what we did it in given C we count all those edges which divides the nodes into two even halves. Please correct if i m wrong !!

→ Ответить

prodipdatta7

6 лет назад, # ^ |

in case of a connected graph ???

→ Ответить

Em00n

6 лет назад, # |

← Rev. 2 →

+204

About the choice of wording in condition 1 of A

→ Ответить

JayZhan

6 лет назад, # ^ |

+11

I like this really much!! XD

→ Ответить

papa-ka-para

6 лет назад, # ^ |

+11

You are worthy of being a problem-settter on codeforces.

→ Ответить

Udit_Maniyar

6 лет назад, # |

In Question B why doesn't 3*nlogn pass the test cases. I tried using maps in c++ but it is showing time limit exceeded in test 45 . Can someone point out mistake in my code : Link

→ Ответить

vbobrov

6 лет назад, # ^ |

while(used[cnt2]==1)
cnt2--;

This part doesn't looks like O(1) or O(log n). I think, it's O(n) at worst case (because of "cnt2 = cnt1;" six lines higher).

→ Ответить

Udit_Maniyar

6 лет назад, # ^ |

Oh got it. Thanks for helping

→ Ответить

6 лет назад, # |

+15

Yay, I became master, but sadly only because of div2 rounds.

→ Ответить

6 лет назад, # ^ |

What is the difference? Master is master. If you don't want to participate in div 2, then wait for div1...

→ Ответить

..vince

6 лет назад, # ^ |

well actually its opposite, there are some purples that skip div 1, because they don't want to be beaten up by reds and yellows and join div 2 to compete with blues instead.

→ Ответить

6 лет назад, # ^ |

They can be beaten up by blues then.

→ Ответить

6 лет назад, # ^ |

I don't understand why everybody is complaining and thinks that it would be easier to get to 2100. The only true thing is that there will be more opportunities to get there. It doesn't mean it would be easier. If you don't deserve 2100 you won't get it, one way or another.

For example I already managed to lose a lot of points in div 2 contest on Monday. And today I was 122. If there were no violet coders, I would have been 25'th which would have given me much more rating.

→ Ответить

sogreatcf

6 лет назад, # ^ |

← Rev. 2 →

-31

Lol You don't understand? Before this shit revolution, to get Master(old) you need to most likely solve 3 probs in Div 1 which is equivalent to all div 2 problems. Now get just good ranks which in most case is possible with just 4 div 2 problems. As you can see in this round, 370 officially solved 4th hardest, you think thats good enough for someone Master?

"I don't understand why everybody is complaining and thinks that it would be easier to get to 2100" Because it actually is faggot. If you don't understand, then compare how many users have got there maximum rating in past div 2 only rounds.

→ Ответить

6 лет назад, # ^ |

"to get Div 1 you need to most likely solve 3 probs in Div 1" — makes sense. Sorry about my previous post.

→ Ответить

vbobrov

6 лет назад, # ^ |

You've became at least, not like me :D (9 points)

Congradulations!

→ Ответить

Kerim.K

6 лет назад, # ^ |

← Rev. 2 →

At least you have a chance to participate to next Div2 round, not like me :D (passed to master with 11 points).

Congratulations!

→ Ответить

jvmusin

6 лет назад, # |

+14

It looks very strange that O(nlogn) solution for D works without any used memory: 38374872.

→ Ответить

f2lk6wf90d

6 лет назад, # |

← Rev. 2 →

Problem C is a duplicate problem: https://www.geeksforgeeks.org/maximum-edge-removal-tree-make-even-forest/
Problem F is a duplicate problem: https://sio2.mimuw.edu.pl/c/pa-2015-1/p/kon/, https://www.quora.com/Given-a-strongly-connected-component-can-you-determine-in-linear-time-if-the-removal-of-a-single-node-turns-the-SCC-into-a-directed-acyclic-graph

→ Ответить

yassin_

6 лет назад, # ^ |

That claim about F is totally ridiculous

→ Ответить

f2lk6wf90d

6 лет назад, # ^ |

Sure. https://sio2.mimuw.edu.pl/c/pa-2015-1/s/89776/source/ 38363244

→ Ответить

KhaledKEE

6 лет назад, # ^ |

+20

The Quora answer is wrong and comments don't seem to give any hint to actual solution.

As for the Polish problem, the translation shows that it is a harder version of Problem F. However, it isn't possible for problem setters to verify that their problems don't exist even on non-English sites.

→ Ответить

Claris

6 лет назад, # ^ |

← Rev. 2 →

Yes, it's the 4th time that I came across this problem.

→ Ответить