UWCOI21D - Efficient Delivery - Editorial

My Ternary search solution gives the same output as the Setter’s solution code and your AC submission on 1000s of randomized test cases yet it’s giving WA on submission for some of the testcases :frowning_face:

My submission:
https://www.codechef.com/viewsolution/40675081

My solution works on public test cases as well as last test case of every subtask… why does it not pass any other case?

Please can anyone explain me that?

My Solution Link: https://www.codechef.com/viewsolution/40679426

#include <iostream>
using namespace std;

int findCost(int x1, int y1, int x2, int y2, int highwayOn);

int main()
{
    int n, m, k;

    cin >> n >> m >> k;

    int x1[k], y1[k], x2[k], y2[k];
    int rowCost[m] = {0};

    for (int i = 0; i < k; i++)
    {
        cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
        int small = y1[i] < y2[i] ? y1[i] : y2[i];
        int large = y1[i] > y2[i] ? y1[i] : y2[i];
        int cost = abs(x1[i] - x2[i]);
        for (; small <= large; small++)
        {
            rowCost[small - 1] += cost;
        }
    }

    int highwayOn = 0;

    for (int i = 0; i < m; i++)
        if (rowCost[i] > rowCost[highwayOn])
            highwayOn = i;

    int totalCost = 0;
    // cout<<"highway on: "<<highwayOn<<endl;

    for (int i = 0; i < k; i++)
    {
        // cout<<"cost of: "<<i<<"  "<<findCost(x1[i], y1[i], x2[i], y2[i], highwayOn+1)<<endl;
        totalCost += findCost(x1[i], y1[i], x2[i], y2[i], highwayOn+1);
    }
    
    cout<<totalCost<<endl;

    return 0;
}

int findCost(int x1, int y1, int x2, int y2, int highwayOn)
{
    int costOnHighway = 0;
    int costOffHighway = 0;
    int yDist, xDist;

    // cost on highway:
    yDist = abs(y1 - highwayOn) + abs(y2 - highwayOn);
    xDist = abs(x1 - x2);
    costOnHighway = xDist + yDist * 2;
    // cost off highway:
    yDist = abs(y1 - y2);
    xDist = abs(x1 - x2);
    costOffHighway = (xDist + yDist) * 2;

    return costOnHighway < costOffHighway ? costOnHighway : costOffHighway;
}

Using counter example, it can be proved ternary search doesn’t work.

Ternary search submission(AC)

CodeChef: Practical coding for everyone

Test Case

100 100 4
1 1 3 1
1 10 2 10
1 20 2 20
1 30 2 30

Output

10

Correct output

8

My Submission

CodeChef: Practical coding for everyone

1 Like

Try this testcase, correct output is 8… your code’s 10.

100 100 4
1 1 3 1
1 10 2 10
1 20 2 20
1 30 2 30

Can you pls explain the part how you brought down the complexity in your code

Is it possible to create this difference array without segment tree? The normal difference array creating method doesnt work for state A and C, since the updates differ by 4.

Whats state A,C? normal difference array creating method would be having 2 loops from y1 and y2 and it would take at worse O(n) time for EACH segment. Thats why we gotta use range update

Ya thats what I meant. For same updates like {9, 9, 9}, I used normal update (add X to L and sub x from R+1) in O(1) but had no idea how to update for variable updates like {1, 5}.

Thanks for providing an edge case, it’s true that ternary search doesn’t work because the distribution of the total time taken by speeding up y=m from m=1 to 100 in your test case isn’t convex. It’s something like
8 10 10 10 .... 10 9 10 ...... 10 9 10 .... where m=1 is the minima.
Although the reason I was facing WA was because I had set low constraints in my random test case generator script and I didn’t notice that I had initialized the result with INT_MAX instead of LLONG_MAX :sweat_smile: Changing that gave me AC so it seems that the test cases are weak.

2 Likes

please tell me the test cases in which my code is giving the wrong answer
my solution: CodeChef: Practical coding for everyone