AtCoder Beginner Contest 245 Announcement

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

← Rev. 2 →

I did node coloring. (white unprocessed, grey in-process, black processed)

A cycle is detected if a grey node is visited before being colored black.

→ Ответить

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

+13

I did remove leafs until there are not more leafs. All remaining vertex lead into circles.

→ Ответить

tiasmondal

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

Me too

→ Ответить

itachi_fam

2 года назад, # |

how to solve c ?

→ Ответить

llc5pg

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

I used multi-source BFS. It could have been done by DP as well.

→ Ответить

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

Maintain the max two numbers the previous position x[] can have. First element can be a[0] or b[0] Then iterate x[], and foreach position check if you can use a[i] or b[i], taking into account which values on the previous position where possible.

You end up with 0, 1 or 2 possible values for the last position. If 0, then ans=No.

→ Ответить

Bungmint

2 года назад, # |

How to solve H?

→ Ответить

Penguin07

2 года назад, # |

I tried FFT on D but failed. Is it precision error? Submission Anyway I got AC with a naive approach. There's no way a problem D in ABC would need FFT.

→ Ответить

2 года назад, # |

Is there a way to extract the index of the min value of an array in a range in O(log(n)) rather that just the value? (with segment tree or otherwise — I am not very comfortable with seg tree yet)

I needed that to solve E.

→ Ответить

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

You can make from each element a pair<value,index>, then sort this. First element in this list is min value, and has its index next to it.

→ Ответить

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

No I mean dynamically. I have to change the value of elems to 'delete' them by assigning to a large val then keep querying for the min in a range.

→ Ответить

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

Not sure how exactly that works.

In E, I maintained a multiset of witdhts of chocklates that fit into some with of a box.

Then iterated the boxes sorted by length, and putting all chocklates that fit into the box by length into above multiset.

Then take one choclate out of the multiset, and put it into the current box. For this, we choose the choclate from the multiset with the biggest with. (which is first if putting negative with into the multiset)

→ Ответить

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

I use Python so I guess multiset wasn't an option for me. I'll have to learn C++ too it seems.

Thanks anyway.

→ Ответить

mohamedeltair

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

← Rev. 3 →

Note that if we sorted boxes and chocolates in ascending order of their widths then their lengths, and started processing boxes one by one in ascending order, we can find that among the first chocolates that have widths $$$\le$$$ the current box it is best to assign the chocolate having the maximum length that can fit into the current box (if exists).

The reason is that all those chocolates will fit into the next boxes in terms of width, so the idea is to choose the one that will increase our chance of succeeding later in terms of length by getting rid of the maximum we can choose.

A multiset with upper/lower bound operations is sufficient here, where we can maintain a pointer for chocolates and when we move to the next box keep incrementing the chocolates pointer while adding the respective chocolate lengths to the multiset until we either reach a length greater than the current box or exceed the $$$n$$$ boundary.

→ Ответить

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

Thank you.

→ Ответить

XGptw

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

the editorial sorts the overall list of boxes and chocolates in descending order of (width, length) but the argument looked similar .

Is there any name for such greedy proof's ?

→ Ответить

hbarp

2 года назад, # |

← Rev. 3 →

Nvm

→ Ответить

2 года назад, # |

Can anyone help me with the question polynomial division for this contest ? The question was fairly easy don't know why I am getting RE as a verdict although there doesn't seem to be any .Here's my code CODE LINK . Thanks in advance.

→ Ответить

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

If A0=0 you divide by 0 I think.

→ Ответить

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

In the question it is given that A0 is not zero.Check the question .

→ Ответить

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

← Rev. 2 →

That's An not A0. A0 is the constant term.

→ Ответить

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

" Here, each coefficient of A(x) and B(x) is an integer whose absolute value is at most 100, and the leading coefficients are not 0. " It's stated the coefficients are not 0 , sorry I didn't get it.

→ Ответить

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

Leading coefficients just mean An and Bm not every coefficient.

→ Ответить

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

← Rev. 2 →

okay, thanks for the clarification, language for the problem should have been better, although it did strike to me that it was written "leading coefficients" instead of "coefficients" anyway thanks for your help.

→ Ответить

hbarp

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

→ Ответить