BNYHOP - Editorial

editorial
, , , ,
6

Excellent problem. Kudos to the author for setting such a problem. But on the other hand, I think the statement was quite convoluting. Please try to make the statements less complex, or give more explanations to examples if the first one can’t be achieved. I asked quite a few questions, and the person responding from the contest team did his best in helping me with the resources he could share, but still it took me quite a lot of time to understand the statement.

Note: This might not be the case for others, but it certainly is for me. And I know for a fact that a handful of us found the statement convoluting.

Thanks for reading this!

12 Likes
7

How can we contact the contest team in between contests?

8

how are (1,4) , (1,5) possible ?

9

also can you please explain how we got these paths?

10

40<50 and There exist a path between 1 to 4 i.e. 1->3->4. Similar case for 1 to 5.

11

I can’t understand the 1(sequence-{i}) part. Can anyone please elaborate this for me?

12

then why not 3->1->2 ? as there is a path and A2 < A3 ??

1 Like
13

In the second test case how is (1,4,3), (1,4), (1,5) a possible path? If (1,4,3) is possible then why no (4,2) since we can reach 4 from 4 and 2 has lower rating than 4? Who wrote the statement first tell me? And who approved this?

14

one-way roads connecting them in such a way that they form an arborescence (a tree with all paths directed from the root), rooted at town 1.

As the roads are one way, and it’s an arborescence, there are no paths between 3 to 2. The edges are 1->3 and 1->2 . So we can’t go 3->1->2 . It’s a one-way road.

Anyway, the statement was confusing, and explanation of the test cases was no help too.

I understood it 1 hour after reading the problem. I was solving a whole different problem earlier.

16

Solution isn’t the time complexity of this solution N_Square ? or I’m missing something ?

17

It says that there are no prerequisites but can someone explain Fenwick Trees (or share a video/blog post) please?

18

try Episode 0 from algorithms live.

19

You can read about it from CP’s Handbook, cp-algorithm or watch algorithms live video on Fenwick Trees.

20

What is point of passing x in euler tour when you are not using it? I am new to euler tour :slight_smile:

21

can u please explain how path 4 → 3 is possible … because there is road from
3 → 4 and not from 4->3

22

there is a comments button at the bottom of the problem , you can ask doubts regarding statements there.

23

then why is 3->2 not possible ? 10<20 and there is a path 3->1->2. why is it not possible?

24

then why is 3->2 not possible ?
10<20 and there is a path 3->1->2. why is it not possible?

25

Path 4 → 3 is not there. But 3 → 4 is there. According to the question, we can jump if there is a path between towns i and j, i.e. a path from town i to town j or from town j to town i.
So, the jump 4–>3 is a possible one.

26

understood. Thanks