CF Jury Meeting (Assigned in CPI Silver class)

Problems and Contests
#1

I tried the problem Jury Meeting here: https://codeforces.com/problemset/problem/853/B.
I find the editorial extremely confusing, especially since there’s no code attached to it.

I don’t follow the text explanation of the O(m^2 + n) prefix and suffix array solution. Here’s what I’ve understood so far; please help me fill in the gaps.

In the sample test case, I’ve sorted the To and From flights by day. Note that the format of the flights is \{day, city, cost\}.

Flights leaving from home, coming TO the capital:

1 1 5000
2 2 6000
3 2 5500

I think the prefix contains as few flights as possible while including the cheapest flights for each city. Is that correct?

1 1 5000 (cheapest FROM flight for city 1)
2 2 6000
3 2 5500 (cheapest FROM flight for city 2)

I don’t understand what d represents. I think it’s the earliest flight of city n in the prefix? Since all jury members meet for k consecutive days, the earliest flight in the suffix must be at least d + k + 1.

  • Under that assumption, d=2.

Flights FROM the capital, heading back home:

8 2 6500
9 1 7000
15 2 9000

I think the suffix contains as many flights as possible so that every flight’s day is more than d + k. Is that correct?

  • Under my previous definition of d, each day in the suffix must be at least 2 + 5 + 1 = 8.
8 2 6500 (cheapest FROM flight for city 2)
9 1 7000 (cheapest FROM flight for city 1)
15 2 9000

Please explain the parts that I am missing. If we were to brute force every pair of flights in these two lists, the prefix and suffix should have maximal accommodation? How is this true in my interpretation?

I still don’t get what d is. The cheapest TO flight for city a may not be compatible with the cheapest FROM flight for city a, right? Please describe, systematically, how exactly we check the prefix and suffix lists for a solution.

I don’t understand the m\log m + n solution at all – there’s too much text without any code.

Can you please provide the official working solution to his problem? Otherwise, please provide your working solution using the editorial’s implementation.
I am new to Codeforces; how do I check for user solutions to a particular problem? Particularly, how do I find the official solution that was coded by the person who wrote the editorial?

Thank you.

#2

C++ solution (following the editorial):

#include <bits/stdc++.h> // see /general/running-code-locally
using namespace std;

using ll = long long;

using vi = vector<int>;
#define pb push_back
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()

using pi = pair<int,int>;
#define f first
#define s second
#define mp make_pair

void setIO(string name = "") {
	cin.tie(0)->sync_with_stdio(0); // see /general/fast-io
	if (sz(name)) {
		freopen((name+".in").c_str(), "r", stdin); // see /general/io
		freopen((name+".out").c_str(), "w", stdout);
	}
}

struct flight {
    int day, from, to, cost;
};
bool operator<(flight a, flight b) {
    return a.day < b.day;
}

int n, m, k;
vector<flight> flights;
ll enterCost[100001];
multiset<ll> exitCost[100001];

int main() {
	setIO();
	
    cin >> n >> m >> k;
    for (int i = 1; i <= n; i++) {
        enterCost[i] = 1e13;
        exitCost[i].insert(1e13);
    }
    for (int i = 0; i < m; i++) {
        int d, f, t, c; cin >> d >> f >> t >> c;
        flights.pb({d,f,t,c});
    }
    sort(all(flights));

    ll bestCost = 1e18;
    ll curCost = 0;
    // initially all exit flights are usable
    for (int i = 0; i < m; i++) {
        if (flights[i].from == 0) {
            exitCost[flights[i].to].insert(flights[i].cost);
        }
    }
    for (int i = 1; i <= n; i++) {
        curCost += enterCost[i];
        curCost += *exitCost[i].begin();
    }

    // these pointers are inclusive
    int lptr = -1, rptr = 0;
    while (lptr + 1 < m) {
        lptr++;
        // add flight lptr
        if (enterCost[flights[lptr].from] > flights[lptr].cost) {
            curCost -= enterCost[flights[lptr].from];
            enterCost[flights[lptr].from] = flights[lptr].cost;
            curCost += enterCost[flights[lptr].from];
        }

        // move rptr until the time between lptr and rptr is > k
        while (rptr < m && flights[rptr].day - flights[lptr].day <= k) {
            if (flights[rptr].to != 0) {
                // this is a return flight that we can no longer use
                curCost -= *exitCost[flights[rptr].to].begin();
                exitCost[flights[rptr].to].erase(exitCost[flights[rptr].to].find(flights[rptr].cost));
                curCost += *exitCost[flights[rptr].to].begin();
            }
            rptr++;
        }

        bestCost = min(bestCost, curCost);
    }

    if (bestCost >= 1e13) {
        // max cost is n*max_c*2
        cout << -1 << endl;
    } else {
        cout << bestCost << endl;
    }
}

I think the prefix contains as few flights as possible while including the cheapest flights for each city. Is that correct?

The prefix is just all the flights that you can use to get to the capital.

I don’t understand what d represents.

From the editorial:

Sort all flights by the day of departure. Now go through flights to the capital (forward flights) and one by one assume it is the last forward flight in answer (let’s say it is scheduled on day d ).

d represents the day that the last forward flight leaves.

I think the suffix contains as many flights as possible so that every flight’s day is more than d + k. Is that correct?

The suffix is all the flights you can use to leave the capital. If the last arriving flight at the capital arrives at day d, then the first departing flight leaving the capital must be at day \ge d+k+1.

Please explain the parts that I am missing.

Perhaps another way to think about the O(nm^2) solution is:

Let’s say that I specify that the last arrival flight will land in city 0 on day \le d. This means that the first departure flight will leave on day \ge d+k+1. What’s the minimum cost to schedule all the flights? (You should be able to answer this in O(nm) or O(n+m).)

To solve the entire problem in O(nm^2) or O((n+m)m), just iterate through all arrival flights and pretend that the currently flight you’re iterating over is the last arrival flight.

Finally, you can optimize the time complexity by using two pointers and maintaining the minimum cost to get to/from each city.

1 Like
#3

Thank you so much for your detailed response, Nathan! I truly appreciate it. After printing out parts of your code and rereading the editorial to match its text with your code, I believe I have a firmer grasp of the solution.

Here is the code I am using for line numbers: https://ide.thecodingwizard.me/#-MWX3hnLK8wqDyovbMhm.

  • What is the purpose of enterCost? What does “adding” flight lptr mean in lines 97 to 102? It seems to store some kind of minimum for each city using flights that enter the capital.
    Assuming curCost is a running sum of all enterCosts as we keep minimizing enterCost with the flight’s cost, can we do this:
enterCost[flights[lptr].from] = min(enterCost[flights[lptr].from], flights[lptr].cost);
int curCost = 0;
F0R(i, n) curCost += enterCost[i];

I think fixing curCost while updating enterCost is better since we only update a particular city. I don’t get how you do this in your code.

  • We use both enterCost and exitCost to store the minimum cost of each city while adding/removing to and from flights. We also only care about the minimum cost for each city in exitCost. Why do we have a multiset for exitCost but simply a running minimum array for enterCost? Can we optimize exitCost to be an ll array?

  • The editorial said that we need to output -1 is when there isn’t an exit flight for a city that matches the (cheapest) enter flight for that city. So while playing around with your code, I tried inserting a condition in lines 116-119. Otherwise, I just output bestCost. Why doesn’t this work?

    if (bestCost >= 1e13) {
        // max cost is n*max_c*2
        cout << -1 << endl;
    } else {
        cout << bestCost << endl;
    }
  • I don’t understand when bestCost >= 1e13. The maximum cost would indeed be 2n flights times maxC = 1e6. Since curCost is initialized to 1e13, I’m assuming we’re checking if curCost stays constant throughout? When would this happen?
    Also, where do we take care of these cases in your code?
  1. There isn’t an exit flight for a city even though there is an enter flight for the city? (multiset exitCost is empty).
  2. There isn’t an enter flight for a city even thought there is an exit flight for the city? (enterCost remains 1e13).
    I think we need to print -1 in both those scenarios.

Makes sense; I thought the prefix and suffix were constant. However, it seems we have a running prefix and conforming suffix using two pointers. The prefix is [0, lptr] and the suffix is [rptr, m).

I don’t understand why in the outer while loop (line 95), we check every single lptr from 0 to m instead of only the arriving flights. Doesn’t if(enterCost[flights[lptr].from] > flights[lptr].cost) only work if flights[lptr] goes from city x to city 0?

Also, say lptr was an arriving flight but not the minimum cost for that city. We’d inadvertently move rptr which makes us miss a potential solution.

2 6 5
1 1 0 5000  ENTRY
2 2 0 5500 ENTRY
3 2 0 600 ENTRY
8 0 2 6500  EXIT
9 0 1 7000  EXIT
15 0 2 9000 EXIT

In that test case, say lptr corresponds to the flight on day 3. The actual entry flights would be on days 1 and 2. We would still have to move rptr and delete the flight on day 8 from the multiset. Actually, entry flights 1, 2 for entry and exit flights 8, 9 are valid! Would this make us lose potential pairs (lptr, rptr) that work?

If I slightly understand the ‘enterCost’ logic (lines 97 to 102), we’re finding the sum of minimum costs per city in the prefix [0, d] using lptr. We can do the same with the suffix [d+k+1, m) using rptr. Every time we encounter a new cheapest flight for a city, we subtract the old cost from curCost and add rptr’s new cost to curCost. For n cities and m suffix flights, this is O(n+m). I think the O(nm) solution would be to loop through the suffix for each city instead of doing it with just a single sweep.

#4

Hi, can you please respond to my previous post?

#5

What is the purpose of enterCost?

\texttt{enterCost[i]} is the minimum cost for someone to go from city i to city 0 with a flight that’s before the current cutoff day d we’re considering.

What does “adding” flight lptr mean in lines 97 to 102?

We’re adding \texttt{flights[lptr]} to the list of inbound flights to city 0 that we can use.

can we do this

er yes but isn’t that too slow? because your for loop would take O(n) time

I think fixing curCost while updating enterCost is better since we only update a particular city. I don’t get how you do this in your code.

? I don’t follow what you mean by “fixing curCost.” I maintain curCost in my code by subtracting the previous cost to enter and adding the new cost to enter.

Why do we have a multiset for exitCost but simply a running minimum array for enterCost?

Because we’re adding flights for enterCost but removing flights for exitCost. I think it’s easier to implement running minimum with removals with a multiset, but it’s certainly possible in constant time as well, but luckily that’s not necessary for this problem.

I tried inserting a condition in lines 116-119. Otherwise, I just output bestCost. Why doesn’t this work?

Because you’ll eventually remove all exit flights (just walk through the code on the sample input) and output -1, even if you found a working configuration earlier in your code.

Since curCost is initialized to 1e13, I’m assuming we’re checking if curCost stays constant throughout? When would this happen?

  1. There isn’t an exit flight for a city even though there is an enter flight for the city? (multiset exitCost is empty).

(oops there’s probably a smarter way to check for -1, I was really lazy) If you look at my code, after I read in the input, I initialize all flight costs to 10^{13}.

I don’t understand why in the outer while loop (line 95), we check every single lptr from 0 to m instead of only the arriving flights.

Oops I think you’re right – it should work if you ignore the flights that aren’t arriving (haven’t tested though).

Also, say lptr was an arriving flight but not the minimum cost for that city. We’d inadvertently move rptr which makes us miss a potential solution.

In that case we would have already handled the potential solution earlier (prior to moving lptr).

1 Like
#6

I’d just like to bring my two cents to the discussion with my code here:

#include <iostream>
#include <vector>
#include <set>
#include <unordered_map>
#include <algorithm>
#include <climits>

using std::cout;
using std::endl;
using std::vector;

struct Flight {
    int day;
    int from;
    int to;
    int cost;
};

/**
 * https://codeforces.com/problemset/problem/853/B
 * 2 6 5
 * 1 1 0 5000
 * 3 2 0 5500
 * 2 2 0 6000
 * 15 0 2 9000
 * 9 0 1 7000
 * 8 0 2 6500 should outupt 24500
 */
int main() {
    int city_num;
    int flight_num;
    int meeting_len;
    std::cin >> city_num >> flight_num >> meeting_len;
    vector<Flight> flights(flight_num);
    int days;
    for (int f = 0; f < flight_num; f++) {
        std::cin >> flights[f].day >> flights[f].from >> flights[f].to >> flights[f].cost;
        days = std::max(days, flights[f].day);
    }

    // vector kills the memory lmao
    std::unordered_map<int, vector<std::pair<int, int>>> arrival_log;
    std::unordered_map<int, vector<std::pair<int, int>>> dep_log;
    vector<std::multiset<int>> dep_costs(city_num);
    for (const Flight& f : flights) {
        if (f.from == 0) {
            if (f.day > meeting_len) {
                dep_costs[f.to - 1].insert(f.cost);  // make the resulting cities 0-indexed
            }
            dep_log[f.day].push_back({f.to - 1, f.cost});
        } else if (f.to == 0) {
            arrival_log[f.day].push_back({f.from - 1, f.cost});
        }
    }
    
    long long rn_cost = 0;
    long long min_cost = LLONG_MAX;
    for (const std::multiset<int>& dc : dep_costs) {
        rn_cost += *dc.begin();
        if (dc.empty()) {  // there won't be any valid departures, let's call it off
            cout << -1 << endl;
            return 0;
        }
    }
    vector<int> arrival_costs(city_num, INT_MAX);
    int invalid_arrivals = city_num;
    
    for (int m_start = 1; m_start <= days - meeting_len; m_start++) {
        // as we move the meeting forward, some departure flights become invalid
        for (auto const& [home, cost] : dep_log[m_start + meeting_len]) {
            rn_cost -= *dep_costs[home].begin();
            dep_costs[home].erase(dep_costs[home].find(cost));
            if (dep_costs[home].empty()) {
                goto end;
            }
            rn_cost += *dep_costs[home].begin();
        }

        // but oh cool, some new arrival flights become valid
        for (auto const& [home, cost] : arrival_log[m_start]) {
            if (arrival_costs[home] == INT_MAX) {
                invalid_arrivals--;
            } else {
                rn_cost -= arrival_costs[home];
            }
            arrival_costs[home] = std::min(arrival_costs[home], cost);
            rn_cost += arrival_costs[home];
        }

        if (invalid_arrivals == 0) {
            min_cost = std::min(min_cost, rn_cost);
        }
    }
    end:;
    cout << (min_cost == LLONG_MAX ? -1 : min_cost) << endl;
}

I think it follows the same philosophy as the editorial, so maybe this will enhance your understanding of the solution.

2 Likes
#7

Thank you once again, Nathan. I’ve clarified most of my doubts except the -1 edge case scenarios.

Thanks also for your code, Kevin. It helped me enhance my understanding of the editorial. I went through your code and understood the structure, particularly how you used a vector for arrival_costs and some multisets for dep_costs (similar to Nathan’s approach). I’ll be asking questions on Nathan’s code, but please note that I appreciate your help as well.

Ah, please correct me if I’m wrong. If we don’t put 1e13 in the exitCosts, say we have an arrival flight on the last day. Then we’d move rptr to m and delete every exit flight (since there’s no 1e13). So we’d say the multiset is empty even if we found some pairing that worked.

I think the bestCost >= INF is clever, since it cares for both these cases at once. I still don’t understand when exactly that condition is true, though.

  1. There isn’t an exit flight for a city even though there is an enter flight for the city? What happens to the multisets exitCost?

  2. There isn’t an enter flight for a city even thought there is an exit flight for the city? So enterCost would stay 1e13.

In the latter, curCost would remain 1e13 since it’s the sum of enterCosts. However, in the former, what happens if we delete 1e13 from exitCost?

It seems 1e13 is a purposeful number. It seems above max_c (is that why we wouldn’t delete it from exitCost?) and above n * max_c * 2 (so bestCost >= 1e13 is a definitive condition). You also initialized bestCost as 1e18, though. Does it matter whether the “checking number” is \le 1e18/m or would any number \ge n * max_c * 2 work?

#8

Ah, please correct me if I’m wrong. If we don’t put 1e13 in the exitCosts, say we have an arrival flight on the last day.

Oops, you’re right; with 1e13 in exitCosts I don’t think the multiset will ever be empty.

There isn’t an exit flight for a city even though there is an enter flight for the city? What happens to the multisets exitCost?

I think the exitCost for that city is just 10^{13} in this case

There isn’t an enter flight for a city even thought there is an exit flight for the city? So enterCost would stay 1e13.

Yep!

However, in the former, what happens if we delete 1e13 from exitCost?

I don’t think we’ll ever delete 1e13 from exitCost?

Does it matter whether the “checking number” is \le 1e18/m≤1e18/m or would any number \ge≥ n * max_c * 2 work?

Any sufficiently large number would work. I just chose 1e13 randomly :stuck_out_tongue:

#9

Thank you so much for your help, Nathan! I understand the entire problem, including the iteration through all possible arrival prefixes. I see why we keep modifying a multiset for all the departure flights and find the minimum total cost for each arrival prefix. It also makes sense when we would output -1, since with a sufficiently large number, either enterCost or exitCost would remain 10^{13}. Thanks for providing your solution and clarifying my doubts about this problem.

1 Like