Source

My school hosted a local ICPC format contest yesterday, this problem appeared in it. Since it was for local only, I cannot provide link for submission (sorry!)

Statement

Given a weighted undirected graph $$$G$$$ with $$$n$$$ vertices and $$$m$$$ edges. Edge $$$e_i$$$ is a tuple $$$(u_i, v_i, A_i, B_i)$$$ denotes there is an edge connects $$$u_i$$$ with $$$v_i$$$, with cost $$$A_i$$$ and $$$B_i$$$. Consider path $$$u \rightarrow v$$$ is a sequence of edges $$$E: \{e_1, e_2,... e_k\}$$$, cost of $$$E$$$ is defined as product of (sum of all $$$A_x$$$) and (sum of all $$$B_x$$$) with $$$x$$$ is an edge in $$$E$$$. Calculate shortest path from node $$$1$$$ to all other nodes.

Contraints

• $$$1 \leq n, m \leq 2000$$$
• $$$1 \leq A_i, B_i \leq 2000$$$

There is no additional guarantees

Sample Tests

Input 1

4 4
1 2 2 4
3 4 4 1
4 2 1 1
1 3 3 1

Output 1

8
3
14

Output shortest path from $$$1$$$ to $$$i (2 \leq i \leq n)$$$:

• Shortest path from node $$$1 \rightarrow$$$ node $$$2$$$ is the edge $$$(1,2)$$$, with cost $$$2 \times 4 = 8$$$
• Shortest path from node $$$1 \rightarrow$$$ node $$$3$$$ is the edge $$$(1,3)$$$, with cost $$$3 \times 1 = 3$$$
• Shortest path from node $$$1 \rightarrow$$$ node $$$4$$$ are $$$(1,3),(3,4)$$$ with cost $$$(3+4) \times (1+1) = 14$$$. The other path is $$$(1,2),(2,4)$$$ has cost $$$(2+1) \times (4+1) = 15$$$ is not the shortest path.

Input 2

3 2
1 2 2 5
2 1 3 3

Output 2

9
-1

$$$-1$$$ means there is no path from $$$1$$$ to that node.

I have prepared this problem some time ago but recently I realized beside my Author solution, another solution works but I just couldn't prove it. I need help on proving the correctness of this unexpected solution.

The problem

I have prepared a problem as follow: There is this secret sequence $$$S$$$ consists of $$$N$$$ distinct numbers. Given a matrix $$$G$$$ of size $$$N \times N$$$, where $$$G_{i,j}=$$$'Y' means surely $$$S_i>S_j$$$. Otherwise, $$$G_{i,j}=$$$'?', meaning we have no information about the relation of $$$S_i$$$ and $$$S_j$$$, whether they are larger or smaller. You need to output a sequence $$$P = \{ P_1, P_2, ..., P_n \}$$$, such that $$$S_{P_1} > S_{P_2} > ... > S_{P_n}$$$, or report that it is impossible to determine exactly the order.

Example

\begin{array}{|c|c|c|} \hline G & 1 & 2 & 3 & 4 \cr \hline 1 & ? & ? & ? & ? \cr \hline 2 & ? & ? & Y & Y \cr \hline 3 & Y & ? & ? & Y \cr \hline 4 & Y & ? & ? & ? \cr \hline \end{array} The above input yields the answer $$$P= \{ 2,3,4,1 \}$$$ which corresponds to $$$S_2 > S_3 > S_4 > S_1$$$. This is the only possible answer.

Constraints:

• $$$(1 \leq N \leq 400)$$$
• Time limit: 1s

The intended solution

This problem can be solved by turn it into the All Pairs Shortest Path problem. First, I create a cost matrix $$$C$$$ of size $$$N \times N$$$. $$$C_{i,j} = 0$$$ if $$$G_{i,j}$$$ equals to 'Y', otherwise, $$$C_{i,j} = \infty$$$. Then I run Floyd-Warshall on $$$C$$$, which produces a "complete" matrix $$$C$$$. After that, if $$$S_i$$$ is the largest element then row $$$C_{i}$$$ will have exactly $$$N-1$$$ zeros, second largest will have $$$N-2$$$ zeros, and so forth.

If the above is not possible, then there is no answer for that input.

The unexpected solution

The solution is as follow:

for (int round = 0; round < 2; round++) {
    for (int a = 0; a < n; a++)
    for (int b = 0; b < n; b++)
        if (G[a][b] == 'Y')
            for (int c = 0; c < n; c++) 
                if (G[b][c] == 'Y') 
                    G[a][c] = 'Y';
}

It needs at max 2 rounds to completely fill the $$$G$$$ matrix, after that I only need to counts the number of 'Y' on each row to reconstruct the sequence $$$S$$$. I have ran this solution on multiple tests against the first solution but it seemed to always give correct results.

Comments

• For sequence $$$S=\{S_1 > S_2 > S_3 > ... > S_n\}$$$ and the its reverse sequence, it only needs 1 round.
• The above requires only 1 run maybe because I traverse all tuples in the "correct" order. For other cases, sequence $$$S$$$ is a permutation of the first case and because I go through all possible ordered tuples, there will be a moment that I go into the "correct traverse order" for the current sequence $$$S$$$, but have not finished it. So it needs another round to complete the traversing... Maybe.

I would like to see the proof for this, or how can I approach it, so any idea would be appreciated.

Problem:

Given a $$$2*N$$$ matrix contains of positive integers with value not greater than $$$10^6$$$. Given an integer $$$K$$$.

Chooses $$$K$$$ column(s) from the matrix, call $$$P$$$ is the sum of all of the top integers from chosen columns, call $$$Q$$$ is the sum of all of the bottom integers from the chosen columns.

Your task is to maximizes $$$P/Q$$$ and print $$$P$$$ and $$$Q$$$ out in its reduced fraction form.

Constraint: $$$1 \leq K \leq N \leq 5*10^4$$$

Time limit: 1s

Input:

• First line contains: $$$N$$$, $$$K$$$

• Next $$$N$$$ lines contain two integers, first integer belongs in the top row of the matrix, second integer belongs in the bottom row. $$$i$$$-th line represents $$$i$$$-th column of the matrix.

Output:

• Two space-separated integers $$$P$$$ and $$$Q$$$.

Example

3 2
3 1
1 2
1 1

2 1

Attempts:

It was from our school's training contest that I first saw it. I blindly submitted a greedy sort sol (ratio of $$$top/bot$$$) but got WA. Next I tried to make it TLE, $$$K$$$ iterations with everytime choose a col. that maximizes $$$(currentP + top)/(currentQ + bot)$$$ and it did get a TLE.

But after that I was stumped.

I aksed my coach for the solution code and let the explaination be an excercise but I couldn't figure it out.

Please help me understand the math/intuition behind the idea of the solution.

I apologize that I can't provide submit link.

Solution:

int main() {
    ios :: sync_with_stdio (0);
    cin.tie (0); cout.tie (0);
    int n, k;
    scanf("%d%d", &n, &k);
    vector a(n), b(n);
    for(int i = 0; i < n; ++i) scanf("%d%d", &a[i], &b[i]);
    long long p = -1, q = 1;
    double lo = 0, hi = 1000000;
    for(int i = 0; i < 100; ++i) {
        double mid = (lo+hi)/2;
        vector > val(n);
        for(int i = 0; i < n; ++i) val[i] = make_pair(a[i]-mid*b[i], i);
        sort(val.begin(), val.end());
        double sum = 0;
        for(int i = n-k; i < n; ++i) sum += val[i].first;
        if (sum > -EPS) {
            p = 0, q = 0;
            for(int i = n-k; i < n; ++i) {
                p += a[val[i].second]; q += b[val[i].second];
            }
            lo = mid;
        } else hi = mid;
    }
    cout << p/__gcd(p,q) << " " << q/__gcd(p,q);
}

I have been only using Polygon platform since March. It's a great platform, easy to learn and very convenient. I mainly use it to prep problems that are later included in Mashups, for my friends to practice.

Back then while poking around, there was one thing I notice, by setting the statement's language to English and then just write whichever language that you prefer, by default it will display for most users since most of them use English language. It worked just fine, well, until now.

Today, after finish everything on Polygon's side, I linked them to here and started checking them, none of the statement are available (in English)! I tried doing the same thing with Russian statement, and Other statement but it didn't work. All of my previous Mashups now didn't work as well. All statements are "not available on English language".

Screenshot

I can't choose the statement to be "In PDF" and I think it's because the language I use contains unicode characters so I have no choice going for "In HTML".

On the meanwhile, one workaround is that I can just send them screenshot of the problem statements.

Edit 1: I just discovered something. Under the Contest Materials on the right bottow of the page when viewing contest, if you attach a link as "Statement", it will act like a "Plan B" if there is trouble viewing the statement. Screenshot Before that it prompted me that statement is not available but now it gives me an option to view a link instead.

Thought that this is a good workaround so i wanted to share.

Edit 2: Thanks to the hardworking CF team, most of my statements work again now. Unfortnately there is one statement that looks like this Screenshot I have found the cause It's because I was messing with the Statement Encoding so False alarm