Monday, April 27, 2015

SRM 657

I guess I just solved the div1 easy. Tried the div1 medium, modulos, modulos , modulos. But I finished the div1 easy editorial, you can find it at http://apps.topcoder.com/wiki/display/tc/SRM+657. Or here, because really, why not:

The problem consists of 6 variables: E, EM, M, MH, H, they are the number of problems you can use in problem sets. Each problem set needs an Easy, A Medium and a Hard problem to be used. E,M and H problems MUST be used as easy, medium or hard, respectively. There are EM problems that can be either easy or medium and MH problems that can be either Medium or Hard. What is the maximum number of problem sets you can make without repeating any problem? Oh, and each variable is a integer as long as 10^18.

Two decisions are involved in this problem:

• Of the EM problems that can be easy or medium, how many will be assigned as medium? Let that number be a
• Of the MH problems that can be medium or hard, how many will be assigned as medium? Let that number be b

When a and b are known, we can calculate the number of problems of each difficulty we have available:

• E + ("EM" - a)  easy problems.
• M + a + b medium problems.
• H + ("MH" - b)  hard problems.

To have a problem set we need one of each kind of problems, so the maximum problem sets is min(E + "EM" - a, M + a + b, H + "MH" - b).

Imagine we wanted to see if it is possible to have x problems in total:

• If E + "EM" < x, no matter what value of a we pick, the number of easy problems would be too small.
• If E + "EM" >= x, then there are normally enough easy problems unless a becomes too large. We can find the maximum allowed value of a: M_a = x - E + "EM". Also a cannot be larger than "EM"
• Similarly, H + "MH" must be at least x and M_b = x - H - "MH" is the maximum allowed value for b.
• We just need M + a + b to be at least x, imagine we take the maximum allowed values: if M + M_a + M_b >= x then we can know x is a valid number of problem sets

Now note that if a value of x is allowed, then so will all smaller values and if a value of x is not allowed , no value larger than x will be allowed. So we can use Binary Search to find the maximum allowed value for x, this is the maximum possible number of problem sets.


long allowedX(long E, long EM, long M, long MH, long H, long x)
{
if (E + EM < x) {
return false;
}
long aa = std::min(EM, E + EM - x); //maximum a
if (H + MH < x) {
return false;
}
long bb = std::min(MH, H + MH - x); //maximum b
return (M + aa + bb >= x);

}

long maxSets(long E, long EM, long M, long MH, long H)
{
// We have to maximize:
// min(E + EM - a, M + a + b, H + MH - b)
// where 0 <= a <= EM , 0 <= b <= MH
long lo = 0; // we know 0 is allowed
long hi = M + MH + 1; // we know this will never be allowed
while (lo + 1 < hi) {
long x = (lo + hi) / 2;
if (allowedX(E,EM,M,MH,H, x)) {
lo = x;
} else {
hi = x;
}
}
return lo;
}


That was the solution in the editorial, but I prefer my lambda solution:

long maxSets(long E, long EM, long M, long MH, long H)
{
// We have to maximize:
// min(E + EM - a, M + a + b, H + MH - b)
// where 0 <= a <= EM , 0 <= b <= MH
return BinarySearch<long>( 0LL, H + MH + 1,  [&](long x) {
if (E + EM < x) {
return false;
}
long aa = std::min(EM, E + EM - x); //maximum a
if (H + MH < x) {
return false;
}
long bb = std::min(MH, H + MH - x); //maximum b
return (M + aa + bb >= x);
});
}


It uses this Binary Search library function because it is funny to use functions as arguments.

// Library code
// takes lo, hi, P() such that:
// P(lo) is true
// P(hi) is false
// If P(x) is true and (x > y) then P(y) is true
// If P(x) is false and (x < y) then P(y) is false
// returns the maximum x such that P(x) is true
template<class D> D BinarySearch(D lo, D hi, std::function<bool(D)> P) {
while (lo + 1 < hi) {
D ha = lo + (hi - lo) / 2;
if (P(ha)) {
lo = ha;
} else {
hi = ha;
}
}
return lo;
}



Friday, April 17, 2015

Codejam round 1A, problem B : Hair Cut

Okay, I participated in round 1A and utterly failed. A ton of factors got involved that made me waste time.

• I thought of the solution for problem A, but when I started to code it I figured out I didn't actually set up my codejam test environment. I had a ton of setup to do to make my (worthless) solution multithreading support to work AND for it to work in gcc 4.8.2 with c++11 support.
• I got really confused by problem A, apparently eating 1.5 (or any other fraction) mushrooms per second is valid... but I don't think that was really well explained... Also what's up with "constant ratio" when the ratio is definitely not constant? It becomes 0 at some times? Huh? And how about giving you an input example before describing what the input is?
• I tried to solve B, my first solution was too slow, then I tried to find cycles in the simulation and it worked but I kept failing the small solution. There was a small bug - After doing the cycle stuff I forgot to return 1-indexed results... Overall what happened in problem B is I completely missed there's a very simple (but with caveats) solution until the last 2 minutes of the match, it was too late.
• C small is just bruteforce and convex hull. Thanks to allowing colinear points (artificial difficulty at its finest :/) I actually had to do a ton of fixes to my convex hull algorithm which I haven't really used in years. My code was pretty awful and there were a couple of bugs in that old code that I had to fix.

Anyway, since B-small / B-large are the only problems I solved that are actually interesting. Here is an explanation for problem B large:

The time

I think the most important thing is to notice the problem is much easier when we know the time t  at which customer N will be served. Imagine we knew this time in advance. Then we would only need a single loop to find all the barbers that finish serving a customer at time t. Each barber i is a cycle, every M_i the barber serves a new customer. So barbers with M_i such that: (t mod M_i = 0) will serve a new customer at time t.

You might be thinking that the solution is the barber that serves a new customer at time t and has the smallest index. This is not entirely true. Multiple customers may be served at time t, and N is not necessarily the first customer to be served at that time. How can we approach this?

Imagine a function b(t) that told you how many customers are served with starting time less than or equal than t. Then b(t-1) will be the amount of customers that were served right until time t. And b(t) - b(t-1) is the amount of customers that start getting served exactly at time t. Now N - b(t-1) - 1 customers will be served at time t before N. Which means that we are looking for the barber with the (N - b(t-1))-th smallest index among those barbers with (t % M_i = 0).

The last piece of the puzzle is how to find t. It all comes down to b(t), with this function we can do a binary search for the smallest t such that b(t) >= N, this is the time you want.

// Library code
// takes lo, hi, P() such that:
// P(lo) is true
// P(hi) is false
// If P(x) is true and (x > y) then P(y) is true
// If P(x) is false and (x < y) then P(y) is false
// returns the minimum x such that P(x) is true
template<class D> D BinarySearch(D lo, D hi, std::function<bool(D)> P) {
while (lo + 1 < hi) {
D ha = lo + (hi - lo) / 2;
if (P(ha)) {
hi = ha;
} else {
lo = ha;
}
}
return hi;
}

struct solver
{
int N, B;
vector<int> M;

int solve()
{

auto begunByTime = [&](long t) -> long {
if (t < 0) {
return 0;
}
long begun = 0;
for (int i = 0; i < B; i++) {
// how many times did it start?
begun += t / M[i] + 1;
}
return begun;
};

// Is the start time for at least N users <= t ?
auto enoughBegun = [&](long t) -> bool {
return (begunByTime(t) >= N);
};

long t = BinarySearch<long>(-1, 10000000000000LL, enoughBegun);
long old = begunByTime(t-1);
long rem = N - old;

//cout << "time = "<<t<<endl;
// find smallest index of a server that starts at time t:
for (int i = 0; i < B; i++) {
if (t % M[i] == 0) {
if (rem == 1) {
return i + 1;
} else {
rem--;
}
}
}
assert(false);
return -1;

}
void init() { }
cin >> B >> N;
//N = 1000000000;
//B = 1000;
M.resize(B);
for (int & x : M) {
cin >> x;
//x = 1 + rand() % 100000;
}

}

Edit: Fixed bugs, oh and also b(t) is just the sum of a bunch of divisions. For each barber, you can find the number of times the barber has started serving customers before or during t by just doing a division, because for every M_i seconds, the barber tries a new user.

Saturday, April 11, 2015

Google Codejam 2015 Qualification Round : Part 4: C small

Part 1: Problem D in Emily

Part 2: Problem A in unnamed language

Part 3: Problem B in Julia

C small

Problem statement

Unlike the other Small problems I didn't really think of a solution of this right away. I had to take a day to do it.

The trick to the problem is that we can find in O(n) the product of the x first left-most numbers (for all x). And the same for the right-most numbers. So imagine if we had a substring [a,b]. If left[a-1] is equal to i and right[b+1] is k then all that we need to learn is if the substring is equal to j. If we can answer that question in O(n^2), we have the whole problem solved. And we totally can answer that question! We just need to start with an a, then b = a and calculate the product for b = a, then it is easy to calculate the product when b = a + 1, just multiply one more number. And so and so for b = a + 2, etc.

The only extra complication is doing the multiplication with i, j, k and the signs... Well, really there are 8 distinct numbers, and we can easily index them and make a table, multiplying this index with this other index yields this other index...

So I tried free pascal. I used to code in Pascal, and I hated it. Now I don't really remember much. So I guess it counts? I had to relearn Pascal a bit. But I reached a solution... which failed. And then it failed again and again... I really thought the problem was in that big hardcoded matrix, and spent hours trying to think of a mistake there. Turns out that free Pascal's Strings are limited to 255 characters (What the hell, free pascal?). You have to use AnsiString for limitless strings.

program C;

function solution(s : AnsiString): String;
const
CONST_I = 2;
CONST_J = 4;
CONST_K = 6;
var
i, j, n, left, curr : Integer;
right : Array[0..100000] of Integer;
t : Array[0..7,0..7] of Integer = (
(0,1,2,3,4,5,6,7),
(1,0,3,2,5,4,7,6),
(2,3,1,0,6,7,5,4),
(3,2,0,1,7,6,4,5),
(4,5,7,6,1,0,2,3),
(5,4,6,7,0,1,3,2),
(6,7,4,5,3,2,1,0),
(7,6,5,4,2,3,0,1)
);
inputInts: Array[0..99999] of Integer;

function ch2index(ch: Char): Integer;
begin
ch2index := CONST_K;
if ch = 'i' then ch2index := CONST_I;
if ch = 'j' then ch2index := CONST_J;
end;

begin

n := Length(s);
solution := 'NO';
for i:=1 to n do begin
inputInts[i - 1] := ch2index(s[i]);
end;
right[n] := 0;
for i := n - 1 downto 0 do begin
right[i] := t[inputInts[i]][right[i+1]];
end;
left := 0;
for i := 0 to n-1 do begin
curr := 0;
for j := i to n-1 do begin
curr := t[curr][inputInts[j]];
if (left = CONST_I) and (curr = CONST_J) and (right[j+1] = CONST_K) then begin
solution := 'YES';
end;
end;
left := t[left][inputInts[i]];
end;
end;

var
X, L : Integer;
w : AnsiString;
ww : AnsiString;
T : Integer;
i,j : Integer;
begin
for i := 1 to T do begin
ww := '';
for j := 1 to X do begin
ww := ww + w;
end;
//writeln(ww);
writeln('Case #',i,': ', solution(ww) );
end
end.

The end

I qualified! This was a lot more fun and far more stressful than usual.

Google Codejam 2015 Qualification Round : Part 3: B small in Julia

After the disaster solving A-large, it became clear that I needed to do more than 2 problems to get an advancing score. But also both B and C seemed likely to be impossible in the languages I wanted. But I still didn't want to use my normal languages. I mean at least B-small seemed quite obvious. A typical problem we can solve with memoization. If we set the state to be equal to an array of 9 elements containing the number of eaters that have 1, 2, ... 9 pancakes. We need to notice that it never makes sense to create a plate that has more pancakes than the original plate from which we took the pancakes. Otherwise each minute just shifts the array...

Anyway, I decided to look for a new language to learn. But something a bit more usable than the other two. I tried Julia. It actually felt like cheating, because it turns out this is a pretty good language. There's a couple of things I don't like, like the 1-indexing. But it was overall a nice experience. Similar to python but with some differences. And apparently benchmarks say it is a bit faster. You can also make it less dynamically typed if needed. Anyway:

function solve(P)
mem = Dict()

function f(seq)
return mem[seq]
end
#println(seq)
res = 1000000000
if count(x -> (x != 0), seq) == 0
# all zeros, base case
res = 0
else
# let one minute go:
a = [ seq[i] for i = [2:9] ]
push!(a, 0)
res = 1 + f(a)

# move something:
for i = [2:9]
if seq[i] > 0
for j = [1:i-1]
#if j != div(i , 2)
#    continue
#end
for k = [1 : i - j - 1]
if seq[k] > 0
b = [x for x = seq]
b[k] -= 1
b[k + j] += 1
b[i] -= 1
b[i - j] += 1
res = min(res, 1 + f(b) )
end
end
# move to empty plate
if i - j < i
b = [x for x = seq]
b[j] += 1
b[i - j] += 1
b[i] -= 1
res = min(res, 1 + f(b) )
end
end
end
end
end
mem[seq] = res
#print (seq)
#print (" = ")
#println(res)
return res
end

seq = [ count(x -> x==i, P) for i = [1:9] ]

return f(seq)
end

for i = [1: s]
q = split(readline(STDIN), " " )
P = map( x -> int(x) , q)
@printf "Case #%d: %d\n" i solve(P)
end


Coding this was easy except for googling how to do things. The logic I learned when learning python really helped.

My compiler

The other language I initially intended to use in codejam was an old compiler thing I coded in 2013. It was a school assignment that took me a couple of days to implement. It's just a C clone that doesn't even have arrays. But hey, at least it has integers. And can actually read. Although it can only read one integer, and write one integer. It doesn't have division either. But it compiles to 64 bits asm code which can be compiled to binary, so speed isn't a big issue.

Problem A - The one with shyness - Standing Ovation

I had to pick a good problem for this. But all seemed unsuitable. My first idea for problem A - Standing OvationWas to just bruteforce for the number of additional members. There's no reason to bring audience members who are shy, so their shyness should be 0. The maximum result is equal to Smax. For each candidate number of additional members, we can just simulate the process and check if everyone claps. So we can do this in an O(S_(max) N) loop quite easily.

For the large version, and also to solve using a language that has no arrays. We can use an on-line algorithm. We initially have x audience members with 0 shyness. We know those will be clapping. So we should worry about the rest. We encounter that there are s_1 audience members with shyness 1. If 1 > x, we need to invite one more audience member: 1 - x. In fact, we can repeat this, now we know there are max(1,x) + s_1 audience members that are clapping. We find that there are s_2 members with shyness 2. And so and so.

The problem was that I needed to have a way to turn the neat input file into something my language can read. Then turn the language's output into something that looks like "Case #1: xxx". DISASTER, I actually learned that my asm code only does syscalls for reading bytes and then converts to integer and is not quite the same as a scanf or cin>>x... In fact, the whole thing really fails at reading files. Even ignored the format issues. I had to learn how to automatize having a terminal send keystrokes to my program for it to work. Apparently this is usually a thing that people need as there is a family of programs called expect that do this. Fortunately, after learning how to use expect I found that python has a pexpect module. This allowed me to create this nifty glue python program:

import pexpect
import sys

# call the solver program, return the result
def call_solver(smax, shy):
try:
child = pexpect.spawn ('./A')
child.sendline('%d' % smax)
child.expect( '.*' )
for ch in shy:
child.sendline ('%s' % ch)
child.expect( '.*' )
child.expect(pexpect.EOF)
return int(child.before.split('\r\n')[-2])
except:
print "ERROR"
return -1

T = int(raw_input() )
for i in range(1, T+1):
s = raw_input()
(smax, shy) = s.split(' ')
smax = int(smax)
print "Case #%d: %d" % (i, call_solver(smax, shy) )
sys.stdout.flush()


So now I am free to make my program using my language...

program Codejam2015A
{
int n, a, s, i, cost;

i = 1;
cost = 0;
//initial clappers (shyness = 0)
while (i <= n) {
if (a >= 1) {
if (i > s) {
// must invite i - s
cost = cost + (i - s);
s = i;
}
}
s += a;
i = i + 1;
}
print cost;

}


Anyway, you can find the complete source code in the codejam score boards...

I submitted A-small, had a failure because it was slower than I thought, I tried to check if there was something wrong. It seems expect is slow in sending things.

I should have known that the reason it was slow would only get worse in A-Large, in fact, when I tried A.large, it turned out that it could barely solve one case per minute, even tho the program was, the glue stuff using expect was very slow, specially when there are 100000 line enters to send to the fake terminal... Failed A-large because of a time out.

Google Codejam 2015 Qualification Round : Part 1: D small in Emily

It's another google codejam qualification round and honestly, these rounds are getting old. We are supposed to spend a whole day solving problems, between the too easy Small inputs and the impossible Large inputs. And what for? Once you get enough points for the cut-off it's not worth it. Unless you planned to be connected at 19:00 and try to solve the problems as fast as possible, then your rank might actually mean something...

One time I had position 29 at a qualification round. Impressive! Except it's all fake. I didn't even qualify to the third round that year.

I actually might have some rants to make about the formats used in our competitions. Did you know that google found winning programming competitions is correlated with bad work performance? It's SCIENCE. (Supposedly). Although us fans of these contests might like to think there is some sort of mistake in this result of Google's data mining. We cannot just really say it's not true, without doing any actual analysis of the data used and how the conclusion was made.

Anyway, so I want to qualify to round 1, but I was bored of qualifications rounds. So I decided to make them interesting by doing something different to my routine of using c++ and trying to get a perfect score. Instead, I wanted to make special language choices. Use only languages that I designed myself or that I didn't actually learn before the day of the round.

Emily

Once I decided to use special languages. I knew that one of the languages to use today was Emily. It's a relatively new languages, so that's a bonus. Also because o> f luck I've been seeing many previews of its development and finding them interesting. Honestly tho I kind of made this decision without thinking a lot...

The day of the round I noticed I should start learning this language. I figured out a couple of issues. Emily doesn't seem to have a way to read input. Fortunately, it does have the ability to write things. Unfortunately, only strings that you cannot process or floats. For some reason, Emily in its 0.1 version only has floating point numbers. That was going to be a bit of a problem.

My initial plan was to only use Emily and the language I will mention next; and hope to advance using only them. *After* getting an advancing score, I could actually try to use other languages just for fun. When I opened the problems, this seemed difficult. All problems seemed to need arrays, or actual string manipulation or 2D arrays, which are worse to do in Emily. Eventually I noticed Problem D.

Problem D: Ominus Omino - (The one with n-ominos)

statement

When I read this problem, it seemed that the small input can be solved with a bunch of conditionals. And the results are just one of two strings. Conditionals are good news because at least they can be implemented in Emily. And we can print fixed strings. I would only need to use my text editor's regexes to turn input files into code that calls my Emily solution.

To solve this problem (The small version) you can just try all variations of R and C, and just try by yourself, is it possible to pick an n-omino that stops the other player from winning?

This is how my notebook looked after this:

The rest was just implementing everything on Emily. It was HARD. So many conditions. The interesting thing about Emily is everything is an unary function. And I mean EVERYTHING. This includes objects and numbers. Unfortunately, I couldn't think of a good way to think advantage of this in this problem.

\version 0.1

# Hi, I am using a language called Emily, it is in version 0.1 :/
# https://bitbucket.org/runhello/emily/wiki/Home

ALWAYSAWAY = "GABRIEL"
CANMAKELOSE  = "RICHARD"

min = ^a ^b (
(a < b) ? a : b
)
max = ^a ^b (
(a > b) ? a : b
)

case4 = ^R ^C (
( (max R C) == 4 && ( (min R C) >= 3 ) ) ? ALWAYSAWAY : CANMAKELOSE
)

case3 = ^R ^C (
a = max R C
b = min R C

maxIs4 = ( (b == 3) ? ALWAYSAWAY : CANMAKELOSE )
maxIs3 = ( ((b == 3) || (b == 2) ) ? ALWAYSAWAY : CANMAKELOSE )

(a == 4) ? maxIs4 : (  (a == 3) ? maxIs3 : CANMAKELOSE )

)

even = ^X (
( (X == 0) || (X == 2) || (X == 4) )
)

case2 = ^R ^C (
( (even R) || (even C) ) ? ALWAYSAWAY : CANMAKELOSE
)

# woops, here was my mistake
case1 = ^R ^C (
ALWAYSAWAY
)

mode = ^X(
( X==1? case1: X==2? case2: X==3? case3: X==4? case4: null )
]

solution = ^X ^R ^C (
( mode(X) ) R C
)

# Examples
println: solution 2 2 2
println: solution 2 1 3
println: solution 4 4 1
println: solution 3 2 3



I couldn't help but get carried away with the functional programming here. Case4 is a function that solves the case for tetraominoes, Case3 for tetraominoes, etc. mode is a function that picks which function to use according to X. I wanted this to just be an array, but apparently that's currently a bit difficult to do.

TCO 2015 Round 1A

I guess I advanced? Unless there is an implementation bug in my algorithms, which is quite possible. I know they are theoretically correct.

While solving the first two problems I kept having the feeling I was doing things the overcomplicated way.

250 points: The one with digits

You are given 1 <= L < R <= 100000, find a pair L <= a < b <= R such that a and b have as many digits in common (ignore repeated digits).

So for a 250 in an "easy" round, this is not like the div2 easies. Can't just try all pairs (a,b). In fact, the solution I used is quite complex (not hard, complex) and sounds like a division 2 hard thing?

The numbers will have at most 5 digits. So each number L <= i <= R will have at most 2^5 = 32 subsets of digits. The idea is to try them all and check if any number in the past had that subset of digits. Hey, it works.

// extract digits from x, call f(d) for each digit d we find.
void forEachDigit(int x, std::function<void(int)> f)
{
while (x > 0) {
f(x % 10);
x /= 10;
}
}

int maxsim(int L, int R)
{
vector<bool> exists(1024, false);
int best = 0;
for (int i = L; i <= R; i++) {
// create a bit mask of the digits in i:
forEachDigit(i, [&](int d) {
});
// for each subset of i's digits:
// did we see this subset before?
// if so, consider for maximum
}
}
}
return best;
}



I did a wrong thing in my first submission, instead of marking exists[smask] = true for each subset I was marking exists[mask] = true for just the set...

500: The one with simulation

There is a graph in which all vertices have exactly one out-edge. You initially place tokens, at most one per vertex. In each step of the game, the tokens move to the vertex pointed by their out-edge. If at any time there are two tokens in the same vertex, you lose. Count the number of ways to place tokens without losing. The steps are repeated K<= 100000000 times.

So once two tokens end up in the same vertex, they will never separate again. So for example we can try simulating with a graph that has a token each. At the end of the simulation, some vertices will have multiple tokens. The trick is to notice that each of these tokens represent an initial vertex. If there are 4 tokens in a single vertex, it means there are 4 vertices that must all contain at most one token in total initially. So for each of the vertices at the end of the game, multiply (Number of tokens in vertex + 1).

The problem is that K can be pretty large. I used something similar to matrix exponentiation to simulate. But I think maybe it is possible to prove that you don't need to do too many simulations?

const int MOD = 1000000007;

// merge two simulation vectors
vector<long> merge(const vector<long> &A, const vector<long> &B)
{
int N = A.size();
vector<long> R(N);

for (int i = 0; i < N; i++) {
R[i] = 0;
for (int j = 0; j < N; j++) {
if ( (1LL << j) & B[i] ) {
R[i] |= A[j];
}
}
}

return R;
}

int wayscnt(vector<int> a, int K)
{
int N = a.size();
// The "identity" vector each token in its initial vertex
vector<long> I(N);
for (int i = 0; i < N; i++) {
I[i] = (1LL << i);
}
// B represents what happens after a single step:
vector<long> B(N);
for (int i = 0; i < N; i++) {
B[i] = 0;
for (int j = 0; j < N; j++) {
if (a[j] - 1 == i) {
B[i] |= (1LL << j);
}
}
}
// P[0] is what happens after one step
// P[1] is what happens after two steps
// P[2] is what happens after four steps
//...
// P[i] is what happens after 2^i steps
const int MAX = 30;
vector<vector<long>> P(MAX, vector<long>(N) );
P[0] = B;
for (int i = 1; i < MAX; i++) {
P[i] = merge(P[i-1], P[i-1]);
}
// with that in mind, we can find what happens after any number of steps
vector<long> x = I;
for (int j = 0; j < MAX; j++) {
if ( (1<<j) & K ) {
x = merge(x, P[j]);
}
}

long res = 1;
for (long y: x) {
res = (res * (__builtin_popcountll(y) + 1 ) ) % MOD;
}

return (int)(res % MOD);
}


1000: The one with bipartite matching

Find the minimum total weight of edges to remove from a bipartite graph so that there is no perfect bipartite matching. o_O.

According to this: ItayGonshorovitzThesis.pdf, if we reduce the bipartite matching problem with flow and try to find the minimum cost to reduce the flow, that is NP-hard. Although with such a low constraint for n`, maybe non-polynomial IS intended. I think that paper has interesting reductions for the problem so maybe it helps?