Given weighted undirected graph, every vertex has its country "C[v]" and money "V[v]". Let's call vertex "v" "responsible" if there exist at least one edge (v, u, cost) where C[v] == C[u]. Also, you can do this operation infinitely many times: Choose edge (v, u, cost), delete it, and add edge (k, u, cost), where C[u] == C[k] and u != k. After this operation make subtraction V[k] -= cost (of course after this operation V[k] must be >= 0). You need to maximize number of responsible vertices

Edited by author 14.08.2024 13:04

My friends solve it with dicnic.
But its time complexity can be up to O(nm^sqrt(n+m)),and its space compexity can be up to O(nm).
I think admin should add the test that all the bank belong to one country.

so this is a NP complete problem ,how can it be solved with 1000 range.. I don't know

A bank can't buy its own debt.

The statement says:
“responsible” banks only, i.e., those that credited _OTHER_ banks in the same country

Could anybody explain, why Bank 3 could not buy debt of Bank 2 to Bank 1 and thus become responsible.
As I think, it contradicts only common sense, but not the statement. But if we use common sense, should we disallow only such kind of loops (where A owes B and B owes A) or any loops (e.g. A owes B, B owes C, C owes A) ?

I am not sure from the problem statement, actually I don't get something. Suppose that we have this test case
5
1 20
1 0
2 0
3 20
3 0
2
1 5 10
3 2 25

Is answer = 2 for this test case?
4 buy debt from 5 to 1 and now 1 have 30 or it still has 20?
If it has 30, then it can buy debt from 2 to 3.

If this is wrong, can tell me what is the solution to this test case, please? Thanks.

Is there any important meaning for :"You may assume that the essential quality of every banker is greed; that is why a banker always agrees to get money today even if he may lose greater money tomorrow because of that."? If there is, can you explain what is it?

Edited by author 12.05.2009 02:39

May be:
As debt can be bought at hole only, we have
max matching between all bankers and all debts.
Is it right?



Edited by author 05.02.2009 15:24

Phrase " “responsible” banks only, i.e., those that credited other banks in the same country. ", means " that bank credited other banks ONLY in the same country." ?

subj

So I mean bank 2 buys dept of Bank 3 and visa versa. Both banks can do that
After that bank 2 will owe 200K to bank 1, bank 3 will owe 200R to bank 1 and bank3 and bank2 will owe 200K to each other. In this case there will be 4 responsible banks
Isn't it so?

Edited by author 01.11.2008 17:15

If initially Bank 1 isn't a creditor of Bank 2 and is a creditor of Bank 3. Bank 2 buys a debt of Bank 3 to Bank 1, Bank 2 is a creditor of Bank 3 now. Is Bank 1 a creditor of Bank 2?

Which 3 banks satisfying the requirements?
Thanks.