## DMOPC '19 Contest 5 P4 - Cafeteria Confrontation Conundrum

View as PDF

Points: 7 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

It's lunchtime! Lunch time at Veshy's school can often prove to be a tricky thing, since the cafeteria loves to change their prices on a regular basis. As such, Veshy sometimes doesn't have enough money to afford lunch!

Luckily, there exists a pecking order in the cafeteria! Each person in the cafeteria has dollars to spend and can extort kindly ask at most one other person, () for their lunch money. If the person being asked doesn't have enough money to cover the costs, then the person being asked can ask their own respective victim friend for money, and so on. (i.e. if person is extorting person for dollars and person has dollars such that , then person will extort their own victim for dollars, which repeats until the whole chain coughs up enough money.)

Since Veshy sits right at the top of the pecking order, he gets the special privilege of being able to extort any one of the other people in the cafeteria for their money. However, with great privilege comes great laziness, and as such, Veshy wishes to pick the person sitting closest to him who can supply him with enough money to buy lunch.

Veshy isn't quite sure what the cafeteria will set the lunch price to be today, so he's going to ask you queries to figure out who he should extort ask for money. Help Veshy out to avoid being extorted as well!

Note: closest is defined here as the person with the least index that still satisfies the conditions.

#### Constraints

(i.e. the index of a victim will be strictly less than the index of the extorter; a victim-index of means they have no one to bully.)

Each person can only extort at most person.

#### Input Specification

The first line will contain , the number of people in the cafeteria today (other than Veshy), and , the number of queries.

The next line will contain space-separated integers, , representing the amount of money person has.

The third line will have space-separated integers, , representing the victim of person . If is 0, that means that they can't bully anyone.

Finally, the last lines will contain integers each in the form p c, which means that Veshy already possesses dollars to spend, but lunch will cost dollars.

#### Output Specification

For each query , print out the closest person which Veshy can extort such that he will end up with at least as much money as . Note that Veshy may already possess enough money to pay off the cost outright, which means he doesn't need to extort anyone. Veshy may also be unable to pay for lunch no matter who he chooses to extort. In either of these two cases, print out -1.

#### Sample Input 1

5 4
2 1 4 3 1
0 1 1 2 3
3 2
1 5
5 12
100 100

#### Sample Output 1

-1
3
5
-1

#### Explanation of Sample Input 1

For the first query and last query, Veshy already has enough money to pay for lunch by himself. In the second query, Veshy should kindly ask person for their money. Since Veshy already posseses a 1 dollar and person provides 4 dollars, Veshy will be able to buy lunch, which costs dollars. Although there are other ways Veshy could gather 4 dollars, all of the other choices have higher indices than person . In the third query, Veshy can ask person for their money. Since , the last person will ask person for their money as well. It turns out person also doesn't have enough, so this asking-chain continues through persons and , when a cumulative sum of dollars have been accumulated, which is just enough.

#### Sample Input 2

5 1
999 999 999 999 999
0 1 2 3 4
999 10000000

#### Sample Output 2

-1

#### Explanation of Sample Input 2

No matter who Veshy chooses to ask, it is never possible to accumulate enough money to buy lunch.

• commented on March 5, 2020, 5:05 p.m.

What a wonderful little problem! A couple kinds of dynamic programming, binary search -- I think this is a great problem to help teach those topics.

(I do think that the 'data structures' and 'graphs' problem types are inaccurate, though. There are no cycles and I can't see why a graph formulation would be beneficial.)

Thank you!

• commented on March 4, 2020, 5:04 p.m.

Is there a better solution than QN time complexity?

• commented on March 4, 2020, 5:22 p.m. edited

The intended time complexity is , and there are methods to achieve as well .