Разбор Educational Codeforces Round 25

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

Becouse then you firstly attach one to first vertex it might have parents. You need to do it from the other side. Label highest leave n and remove it.

→ Ответить

Yellow.Flash

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

sorry ,by "degree" i meant "in-degree"

→ Ответить

kabirsahni8

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

← Rev. 9 →

Try this:- 10 2

3 1 4 1 The problem here is the algorithm tries to allocate the best position for value 1,2,... and so on.But this greedy algorithm forces you to place a bigger number at the more significant position.

→ Ответить

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

or just

3 1
3 1

→ Ответить

srinu37

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

counter example

4 -> 1

2 -> 3

→ Ответить

Dragon_in_Bed

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

"Lexicographically", which means u don't want label 1 to match the smallest index, but let the smallest index to match the smallest label.

→ Ответить

Shameek

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

i tried to use KAHN algorithm but use set instead of queue...this doesnt work — why?

→ Ответить

kurokochin

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

For problem A, why the accepted output of input '100' is '100', shouldn't it be '10'? (Because first we meet 1 and then terminate of first digit with 0 and then we meet 0, thus the output is 10) sorry for my bad english

→ Ответить

darkkcyan

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

← Rev. 2 →

The problem said that 0 character separates blocks consists only character 1, and the length/size of each block is the digit it represents.

For the input 100, we can rewrite it like this: (1)0()0(). So there are 3 blocks. First block has size 1 and the other 2 have size 0. So the output is 100.

→ Ответить

Alexxx

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

I'm too have written solution with using split as you have, but in Java blocks with zero-length lines skips.

→ Ответить

darkkcyan

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

yes, it is like the difference between .split() and split(' ') in python

→ Ответить

Alexxx

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

We divide line using '0',start,end. Then print count of '1' in every segment.

→ Ответить

fofao_funk

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

In problem F, why the answer for the string kbyjorwqjk is 11 and not 12 (test case 4)?

→ Ответить

Aeon

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

+10

answer can't be greater than |s| + 1

→ Ответить

fofao_funk

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

Why not? What would be the compressed version for this string?

→ Ответить

Aeon

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

1kbyjorwqjk

→ Ответить

fofao_funk

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

Lol, my bad. For some reason I thought the quantity of characters of the period should precede it, not the number of times it is repeated. Thanks a lot for the help.

→ Ответить

CuongCuong

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

WA in test 14 prob D but i can't check what that test is

→ Ответить

ghostkkk

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

Use long long

→ Ответить

CuongCuong

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

thank you so much

→ Ответить

todi_kunal

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

In problem D, If i make a count map for all characters for string t and then consider window length of strlen(t) in string s.

Now in each window, there is map count for all characters and then a variable storing count of number of empty characters -> '?'. Now we match the count array of t with count array of window and see if there is a match considering empty characters with all unmatched characters.

Lastly, if i get a match , I jump from i->i+strlen(t) otherewise i->i+1.

Will this algorithm work..??

→ Ответить

kamishogun

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

It should work. Here's my solution, though I think it's slightly different from yours. I stored all positions of '?,' then iterated through them. For each position keep going through all letters in t while subtracting it from a count map if it is already in string s (not a '?'). If a letter isn't in s, we set the current '?' to that letter and repeat for all other positions. Ignore the variables 'bad' and 'mx.' I forgot to delete them but they are unused. 28608658

→ Ответить

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

+11

in problem E :

I have not understood why doing the same as the editorial but from the other side is wrong yet, I mean why labeling from 1 to N starting from the nodes with in-degree equals to zero is wrong.

I applied the proof in the editorial on that and I didn't find anything wrong, could anyone please tell where is my mistake ?

thanks in advance.

→ Ответить

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

I thin there is a bug in your code, when you are trying to do something with unconnected nodes. In the test you fail judge is waiting for 13, while where is no information given about 13. And you print 15, you should print 13, becouse it is unconnected and can be smaller than 15.

→ Ответить

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

sorry if it seemed like I was defending my solution , I know it's wrong !!

maybe the code has some bugs. However, you can see that this approach is wrong here by the counter examples that were mentioned in the above comments.

what I want to know is why the proof in the editorial can not be applied on my approach, where does it fails!!!!!!

→ Ответить

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

It works, you just fail to implement it

→ Ответить

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

take this counter testcase:

4 2

3 1

2 4

if you apply our approach on this test you will choose 2 first, then 3,then 1,finally 4. which will give you this permutation :

3 1 2 4

but the correct solution is to choose 3 first, then 1, then 2, finally 4. which will give you the correct permutation:

2 3 1 4

if I made a mistake, hope you clarify where it is

→ Ответить

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

4->2->4 is a cycle

→ Ответить

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

i'm crashing my head with walls now

4 is the number of nodes

2 is the num of edges

→ Ответить

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

Ohhh, now i see why it doesn't work... Also look at sneaky test 6...

→ Ответить

Momentum

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

← Rev. 2 →

From the set of nodes of in-degree equals to zero: picking node V, the one with smallest index to be labeled '1' will not always give the lexicographically smallest permutation.

Let's apply the same approach of the editorial: let node V be labeled X (X > 1), this labeling may result that other node U (U < V) get labeled Y (Y < X) which result in lexicographically smaller permutation.

So applying the same approach won't result in a contradiction.

→ Ответить

roll_no_1

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

I'll try to explain the reason as to why it doesn't work in the reverse direction.

In the editorial's solution, the label of one vertex increases (X -> N), whereas the labels of some vertices decrease. In this, there is always some vertex having a lesser index whose label is decreased. So, the new labeling is lexicographically smaller than the previous one.

While applying the same thing in the reverse direction, the label of one of the vertices decreases (X -> 1), whereas the labels of some vertices increase. Here, it might be possible that some vertex for which the label is getting increased might have a smaller index than the current vertex. So, in this case, we might end up having a lexicographically larger labeling.

So, the proof for the reverse case can not be established using a similar reasoning.

→ Ответить

isgulkov

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

← Rev. 4 →

и если |t| делится |t| - plast (plast — последнее значение префикс-функции), тогда длина минимального периода равна $\text{[math]}$

Она же в этом случае равна |t| - p_last, нет? Я, дурак, на голубом глазу это сразу в код перевел, а потом час думал-гадал, буквы на листочке рисовал...

→ Ответить

BledDest

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

Sorry for the incorrect formula in F, it is fixed now.

→ Ответить

Sukeesh

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

Can someone explain reason for MLE in my code?

Code : 28646208

→ Ответить

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

Same problem as here. Your binary search may find incorrectly a big number as answer. So this vector that you create to build the answer will exceed the memory limit.

→ Ответить

scarlet37

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

Can someone help me with my solution for D ? I'm getting WA

Code : 28647476

→ Ответить

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

The problem was overflow inside your check function. If the frequency of some letter is big and you test a big number at the binary search the result of multiplication may exceed by far the int limit.

→ Ответить

Ehsan_sShuvo

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

Could someone please explain problem D more clearly?I didn't get that.Thanks ins advance :)

→ Ответить

kamishogun

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

I tried explaining my solution in a comment above (under Todi_Kunal). If you have any further questions, feel free to ask. 28608658

→ Ответить

nimom

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

Can anyone tell me What is qsum in 825D?

→ Ответить