Dear Codeforces community,

We're excited to invite you to TOKI Regular Open Contest (TROC) #2!

Key details:

• Rated
• Contest link: https://tlx.toki.id/contests/troc-2
• Time: 25 August 2018, 19:05 UTC+7
• Style: ICPC-style, 8-minute penalty per wrong submission
• Writers: wiwitrifai, Luqman, radit
• Duration: 2 hours
• Problems: 6
• Allowed languages: C, C++11, Pascal, Java, Python 3

The first several rounds of TROCs will be used to generate the initial ratings for the contestants. Everyone can join (combined divisions), and the problemset is expected to be easier than usual.

Please register to the contest, and we hope you will enjoy TROC #2!

UPD: Contest is over! Top 5:

1. jonathanirvings
2. dragoon
3. prabowo
4. rais.fathin38
5. AMnu

Editorial is available at https://docs.google.com/document/d/196SfM9y36uGuRhPkTG5aqFZY2YX26alwAB-LV0cMj7o/.

You can upsolve the problems at https://training.ia-toki.org/problemsets/118/problems.

Thanks for participating!

Dear Codeforces community,

We're excited to invite you to TOKI (Indonesian informatics olympiad committee) 's first rated contest on our TLX platform:

TOKI Regular Open Contest #1!

Key details:

• Rated (our first rated contest!)
• Contest link: https://tlx.toki.id/contests/troc-1
• Time: 28 July 2018, 19:05 UTC+7
• Style: ICPC-style, 8-minute penalty per wrong submission
• Writers: ayaze, athin, rais.fathin38, FwP, Yoshiyuki
• Duration: 2 hours
• Problems: 6
• Allowed languages: C, C++11, Pascal, Java, Python 3

The first several rounds of TROCs will be used to generate the initial ratings for the contestants. Everyone can join (combined divisions), and the problemset is expected to be easier than usual.

Please register to the contest, and we hope you will enjoy TROC #1!

UPD:

Contest is over! Thanks for your participation.

Top 5:

• AMnu
• dragoon
• sokokaleb
• chaotic_iak
• jonathanirvings

Ratings have been updated! See the global ranklist: https://tlx.toki.id/ranking.

You can upsolve the problemset here: https://training.ia-toki.org/problemsets/117/problems.

See you in the next TROC!

TCO17 Algorithm Round 2B will start at 12 noon EDT, Saturday, July 8, 2017.

Let's discuss the problems after contest here.

Hi all,

Is there any way to buy the Looking for a Challenge book? I know there have been PDF scans circulating in the Internet but I really want to buy an original physical copy of the book. The website has been saying "We plan to print more!" for years but I've never been able to reserve a copy as advertised.

Thanks!

Hello,

Indonesia is hosting this year's APIO 2015. The contest will take place on this weekend, May 9 2015.

We also provide a mirror contest, called Open APIO 2015, after the official contest day for everyone to participate. It will be a 5-hour virtual contest that you can start any time between Sunday, 10 May 2015, 20:00 (UTC+7) and Monday, 11 May 2015, 20:00 (UTC+7). We really encourage you to try the problems, just for fun!

Here are the details:

• Register here: https://competition.ia-toki.org/contests/18/view. Registration closes 1 hour before Open APIO 2015 ends. If you don't have account on TLX (our contest system), you will be prompted to register on TLX.
• No medals/certificates will be awarded.

The rules for Open APIO 2015 are similar to the official one:

• There will be 3 IOI-style problems.
• You can only submit at most 30 submissions for a problem.
• You will get full feedback for each submission.
• For each problem, there are several subtasks:
  • For each subtask, there are points assigned to it.
  • Each subtask contains several test cases.
  • You get the points from that subtask if the program passes all the test cases in that subtask.
• The score of a submission is the sum of all the points that you get from completing subtasks.
• The final score for a problem is the maximum of all the submission scores for that problem.

And here are the grading environment specifications:

• OS: Ubuntu 14.04.1 LTS
• Kernel: Linux 3.13.0-36-generic #63-Ubuntu SMP Wed Sep 3 21:30:07 UTC 2014 x86_64
• CPU: Intel Xeon E5-2666 v3 2.90GHz
• Compilers:
  • gcc (Ubuntu 4.8.2-19ubuntu1) 4.8.2 (flags: -O2 -lm)
  • g++ (Ubuntu 4.8.2-19ubuntu1) 4.8.2 (flags: -std=c++11 -O2 -lm)
  • fpc 2.6.2-8 [2014/01/22] for x86_64 (flags: -O2 -XS -Sg)
• You must print a newline ('\n') after each line in your output.

You can also discuss the problems on this thread, but please do so after Open APIO 2015 ends.

Thanks,

APIO 2015 organizers

Hi all,

Last week, we conducted TLX Open Contest Beta Round #1 Now, want to invite you to take part in TLX Open Contest Round #2. The details are similar to the previous contest. To reiterate:

• Saturday, May 2, 20.00 UTC+7 — 23.00 UTC+7 (3 hours) click here for other timezones.
• Registration opens here. If you don't have account, you will be prompted to register (there is an SSO login system).
• Contest registration closes 5 minutes before contest ends.
• IOI-style, 3 problems. There will be subtasks. For this testing round, we will be using past Indonesian national olympiad problems.
• Available languages are C, C++11, and Pascal.
• Full scoreboard will be available.
• Full feedback for each submission.
• You may submit clarifications on the first hour of the contest.
• There is a 20 submissions limit per problem per contestant.
• Note: all times shown on TLX are in UTC+7 (Jakarta time).

Thanks!

UPD

Thanks for participating. Congratulations to the following users who solved all problems:

• dreamoon_love_AA
• dnk
• FatalEagle
• kien_coi_1997

The problems have been added to TLX Practice Contest for upsolving. (Note that this is a temporary solution -- we are planning to have a problems archive functionality.)

You may discuss the problems here.

Hi all,

This year, Indonesia is hosting Asia-Pacific Informatics Olympiad 2015. For this competition, we will use our brand new contest system called TLX. We have been using TLX intensively for Indonesian training camps and so far we have been very satisfied and no major problems were encountered.

Now, we would like to conduct a real-time test for international usage. So, we invite you to take part in TLX Open Contest Round #1. Here are the details:

• Saturday, April 25 20.00 UTC+7 — 23.00 UTC+7 (3 hours) timeanddate.
• You have to register to TLX (there is an SSO login system), and then register to the contest.
• Contest registration closes 5 minutes before contest ends.
• IOI-style, 3 problems. There will be subtasks. For this testing round, we will be using past Indonesian olympiad problems.
• Available languages are C, C++11, and Pascal.
• Full scoreboard will be available.
• Full feedback for each submission.
• You may submit clarifications on the first hour of the contest.
• There is a 20 submissions limit per problem per contestant.
• Note: all times shown on TLX are in UTC+7 (Jakarta time).

For APIO 2015 contestants, you may want to participate in this contest as a warm-up for the real contest. For all students, you may want to participate in this contest as a warm-up for IOI 2015.

There is already a practice contest round for TLX contest system that you can use before the real contest round.

Thanks!

UPDATE

Thanks for participating! We're sorry for typos in problem statements -- we made some errors when importing the old problems from their PDFs to the systems.

The problems have been added to the practice contest. Feel free to upsolve!

Also, we would like to hear your comments on the contest system. Please do give some feedback on this thread!

Thanks,

• APIO 2015 organizers & TLX developers

Hello!

I have been writing a new test cases generator framework for IOI-style problems for several months. It should be quite stable now, so I would like to share it to you.

First of all, let me tell the source of inspiration of this new framework.

testlib

(https://code.google.com/p/testlib/)

I discovered MikeMirzayanov's testlib library when I prepared Codeforces Round #192 (a.k.a. Trollforces round). It is a nice library (thank you Mike!). I wanted to use it for generating test cases for our national training camps, but it seems that it is not quite suitable for IOI-style problems which have subtasks etc. So, I created a wrapper on top of it.

tokilib

(https://github.com/fushar/tokilib)

It is a wrapper on top of testlib. I actually wrote about it in a blog post. It essentially will call testlib's generation many times for generating multiple test cases, and testlib's validation many times for supporting subtasks.

It has been very useful and quite easy to use. We have been using it for ~ 1 year for our training camps and real national OI. It really helped the problem setters to collaborate on writing test cases for the whole problemset. Their feedbacks are always positive.

tcframe 0.3.0 (NEW)

(https://github.com/ia-toki/tcframe, https://tcframe.readthedocs.org/en/latest/)

Using the previous two solutions, we still need to write two files: a generator, and a validator. Can we somehow just merge them and only write a single file?

After brainstorming and designing for several months, I came up with a solution that I think is quite clean and neat! I completely rewrote it from scratc. It now does not depend on testlib anymore. I gave it a new name: tcframe.

Let's consider a very simple A + B problem:

Description

You are given two integers A and B. Compute A + B!

Input Format

The first line contains two space-separated integers A and B.

Output Format

A single line contains the answer.

Sample Input

7 42

Sample Output

49

Subtask 1

• 1 <= A, B <= 1000

Subtask 2

• 1 <= A, B <= 1000000

This is a sample generator program using tcframe framework that generates test cases for the above problem.

#include "tcframe/tcframe.hpp"
using namespace tcframe;

class Problem : public BaseProblem {
protected:
    int A;
    int B;

    int result;

    void Config() {
        setSlug("aplusb");
    }

    void InputFormat() {
        LINE(A, B);
    }

    void OutputFormat() {
        LINE(result);
    }

    void Subtask1() {
        CONS(1 <= A && A <= 1000);
        CONS(1 <= B && B <= 1000);
    }

    void Subtask2() {
        CONS(1 <= A && A <= 1000000);
        CONS(1 <= B && B <= 1000000);
    }
};

class Generator : public BaseGenerator<Problem> {
protected:
    void Config() {
        setBaseDir("tc");
        setSolution("./solution");
    }

    void SampleTestCases() {
        SAMPLE_CASE({
            "7 42"
        }, {1, 2});
    }

    void TestGroup1() {
        assignToSubtasks({1, 2});

        CASE(A = 1, B = 1);
        CASE(A = 5, B = 7);
        CASE(A = 10, B = 100);
        CASE(A = 1000, B = 1000);
    }

    void TestGroup2() {
        assignToSubtasks({2});

        CASE(A = 1001, B = 1001);
        CASE(A = 2000, B = 1500);
        CASE(A = 41728, B = 771823);
        CASE(A = 1000000, B = 1000000);
    }
};

int main() {
    Generator gen;
    return gen.generate();
}

One cool feature of this framework is that the problem specification class is really similar to the problem statement! I have brainstormed several possibilities for the syntax, and I think this is the best so far.

When run, the above program will produce the following output:

Generating test cases...

[ SAMPLE TEST CASES ]
  aplusb_sample_1: OK

[ TEST GROUP 1 ]
  aplusb_1_1: OK
  aplusb_1_2: OK
  aplusb_1_3: OK
  aplusb_1_4: OK

[ TEST GROUP 2 ]
  aplusb_2_1: OK
  aplusb_2_2: OK
  aplusb_2_3: OK
  aplusb_2_4: OK

And all generated test case pairs will be available in tc directory.

Now suppose that we made some mistakes in the generator class: instead of CASE(A = 1000, B = 1000), we accidentally wrote CASE(A = 1000, B = 10000). When the program is run, it will output a nice error message:

Generating test cases...

[ SAMPLE TEST CASES ]
  aplusb_sample_1: OK

[ TEST GROUP 1 ]
  aplusb_1_1: OK
  aplusb_1_2: OK
  aplusb_1_3: OK
  aplusb_1_4: FAILED
    Description: A = 1000, B = 10000
    Reasons:
    * Does not satisfy subtask 1, on constraints:
      - 1 <= B && B <= 1000

[ TEST GROUP 2 ]
  aplusb_2_1: OK
  aplusb_2_2: OK
  aplusb_2_3: OK
  aplusb_2_4: OK

That's it. You can find more complex examples on the documentation.

Anyway, please do try it yourself for creating test cases for your problems! I really need feedbacks from you, whether as bug reports or feature suggestions. Note that this still not a 1.0 version yet, so some syntaxes may change in the future.

I released this framework as open source, under MIT license. You can use it for whatever you want.

If you have any questions or feedback, please post a comment on this thread

Thanks! I hope this framework will be useful for you :)

Hello!

It is the first time for Indonesia to open our IOI selection contest to (selected) international participants. We call it TOKI Open 2014. TOKI stands for Tim Olimpiade Komputer Indonesia, or Indonesian Computing Olympiad Team in English. We received very good responses in term of number of participants and the enthusiasm, despite the limited amount of time for preparation and publication.

Objectives of us opening this contest include, but not limited to:

• Foster friendship between Indonesia and other IOI participating countries.
• Test Indonesia's scientific committee capability in setting IOI-level problems.
• Test Indonesia's technical committee capability in hosting IOI-level contests.

Here are the problemset, results, and test data. We hope you find the problems interesting!

There were in total 124 contestants registered: 40 going to this year IOI, 50 not determined yet whether going or not to this year IOI, 18 no longer eligible for IOI, 16 perhaps going to later IOI. And among those, 1 champion achieved perfect score (600), congrats to contestant registered as Mohammad Ishraq Huda from Australia. Congratulations!

We hope to conduct TOKI Open again next year, with broader audience. If you have any inquiries, please contact scientific@toki.or.id.

Feel free to discuss anything!

Hi all,

I created a framework for generating test cases for competitive programming problems: https://github.com/fushar/tokilib. It extends MikeMirzayanov's testlib so that the test cases can be used for systems other than Polygon.

We have been using it for IOI training camps in Indonesia and so far we are very satisfied, so we want to share it to you. Any feedback will be appreciated :)

So! We hope you enjoyed the round. Internally, we called this round Trollforces, because as you knew, most solutions should be unexpected :)

Some fun fact: there are ~ 30 pictures in this round, totaling ~ 144 KB.

Here is the editorial, written with mixed point of views of all writers (hence "I" may refer to any of us).

330A - Cakeminator by dolphinigle

Long solution:

• Once an evil strawberry, always an evil strawberry (since they can’t be eaten).
• Thus, if a row cannot be eaten before any eat is performed, it can never be eaten.
• Same with column.
• Thus, you can know which columns and which rows you can eat.
• Just try to eat them all and calculate how many cells you actually eat.

Short solution:

• A row or a column cannot be eaten if it has at least one strawberry.
• A cell cannot be eaten if both its row and its column cannot be eaten -- otherwise you can eat the row/column and eat it!

If there are r' rows that cannot be eaten, and c' columns that cannot be eaten, then there are r' * c' cells that cannot be eaten -- a cell such that both its row and columns cannot be eaten.

Since all other cells can be eaten, answer is R * C — r' * c'.

330B - Road Construction by jonathanirvings

• Since m < n/2, there exists at least one node that is not incident to any edge.
• The constraints can be satisfied if and only if the graph is a star graph: http://en.wikipedia.org/wiki/Star_(graph_theory). We can just create a star graph centered with the node and connect it to all other nodes.

330C - Purification / 329A - Purification by dolphinigle

• Obviously the minimum possible answer is n (why?). But is it always possible to purify all the cells with n spells?
• If there exist a row consisting of entirely "E" cells and a column consisting of entirely "E" cells, then the answer is -1. This is since the cell with that row and that column cannot be purifed.
• Otherwise, without loss of generality let's suppose there is no row consisting entirely of "E". Then, for each row, find any "." cell. Purify it. The case with no column consisting entirely of "E" is similar.

330D - Biridian Forest / 329B - Biridian Forest by dolphinigle

The only non ad hoc problem in the round! ...sort of. Despite the very long problem statement, the solution is really simple.

• We should take any shortest path from S to E (yes, any!). We will see why this is optimal at the end.
• If a breeder can reach E faster than or equal to us, then he will battle us. This is since he can simply walk to E and waits for us there.
• Otherwise, they can never battle us by contradiction. Assume they battled us, but they cannot reach cell E from their location faster or equal to us. If the battle us in cell X, then cell X is part of the shortest path from S to E that you are travelling. Since he is able to battle us there, he must be able to arrive at cell X <= us. But then, that means he can walk from X to E and reach E before or equal to us! Contradiction.
• This is optimal, since any breeder that we battle in this solution must also be battled in any other solution (the other breeders should immediately go to E and wait).
• You can use Breadth-First Search once from exit cell to obtain the shortest paths from each breeder to it.

Thoughts

I tried to make this clearer by separating the paragraphs by topic. Did it work well?

Btw, mikemon is pronounced "mi-ke-mon", not "mike"-mon -- similar to how Pokemon is pronounced "po-ke-mon" not "poke"-mon >:).

330E - Graph Reconstruction / 329C - Graph Reconstruction by fushar

First, I would like to apologize the missing node 3 in the picture of the first example. It was a mistake :(

Intended, deterministic solution:

• If n <= 7, brute force all possible subsets of the edges (at most 2^(7 * (7 — 1) / 2)), and check if they satisfy the constraint.
• Otherwise, a solution always exists. Here is how to construct one.
• Partition the nodes into connected components. Note that each component will be either a cycle or a chain. List the nodes of each component in order of the cycle/chain. For example, for the first example, the partition would be { <1, 2, 3>, <4, 5, 6, 8, 7> }. For each component, we do not care whether it is a cycle or a chain.
• For each component, reorder the nodes such that all nodes in the odd positions are in the front. For example, component ABCDEFGHI is reordered into ACEGIBDFH. (Each letter represent a node.)
• Pick any component with the largest number of nodes. If the number of nodes in it is even, swap the first two nodes. For example, ABCDEFGH -> ACEGBDFH -> CAEGBDFH.
• For each other component, insert the nodes alternately between the largest component. For example, if the other components are acebd and 1324, insert them as follows: CAEGBDFH -> C a A c E e G b B d DFH -> C 1 a 3 A 2 c 4 EeGbBdDFH.
• Connect adjacent nodes so that the number of edges is m, connecting the last with the first nodes if necessary.

The deterministic solution is very tricky. Therefore, I made the pretest quite strong. Some tricky cases:

• 4-cycle and 1-chain (covered in the example)
• 3-cycle and 3-cycle
• 4-cycle and 3-cycle (very tricky! many submissions failed on this case)

Actually, we can do brute force when n <= 6, but this requires a special handling: when the largest component has 4 nodes, we should swap the first node with the third node (not the second). This is to handle the 4-cycle-and-3-cycle case.

Troll solution, nondeterministic:

Do the following many times:

x = [1, 2, 3, ..., n]
random_shuffle(x)
for i = 1 to m:
    if the edge (x[i], x[(i+1)%n]) is in input:
        // fail this iteration, repeat the entire procedure

if didn’t fail:
    // we obtain a solution!
    for i = 1 to m:
        print x[i], x[(i+1)%n]

If didn’t obtain solution:
    print -1

So, the question is, for large n what is the probability that a permutation is not "bad"? This can be computed (or at least approximated) similar to computing derangement probability -- I obtained a result above 0.1, which means in 100 iterations it should succeed if there was a solution. ...There is a solution if n > 7, so it should work.

329D - The Evil Temple and the Moving Rocks by dolphinigle

Post your solution in the comment! Here's mine for the last case! (approximately 120,000 sounds). You can get the number of sounds your solution produces when submitting it to the server.

1 copy of
v<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<.<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v>v^

24 copies of
v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.v.
v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^

24 copies of
v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^v^
.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^.^

1 copy of
>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^>^
....................................................................................................

1 1

I wonder if there’s a solution with ~150,000 sounds or more... the (theoretical) upper bound is 100^3 / something, so it may be feasible...?

329E - Evil by dolphinigle

The solution to this problem is actually quite simple: 4122927

This problem asks us to prove something very long (the proof below is of 80+ lines).

Assume that the number of cities is at least 4. The case where it's less than 4 is trivial.

First, we will assume that no two cities will have same X or Y coordinates. To get this assumption, we can juxtapose every city very slightly that it will not change the answer.

The keys are : A) "Manhattan Distance", B) the tour starts and ends at the same city. Suppose we know a tour. The total distance traveled will be |X1 — X2| + |Y1 — Y2| + |X3 — X2| + |Y3 — Y2| ...

Let's separate the X and Y coordinates for simplicity. Note that each city will contribute twice to this value, for example X2 was in |X1 — X2| and |X3 — X2| in the example above. Manhattan distance implies that each of these values will either be multiplied by +1 or -1, depending on the other coordinate being compared in the absolute term. Furthermore, the number of values that are multiplied by +1 must equal the number of values that are multiplied by -1 (since in each absolute term, one is multiplied by +1 and the other by -1). This directly implies an upper bound on the maximum length of the tour.

If we list all the X coordinates of the cities, and we put each of them twice in this list, and sort them, the maximum will be gained if we multiply the last half by +1 and the first half by -1, and finally summing them up. Note that all of these reasoning applies to the Y coordinate, and summing both maximum of X and Y, we receive an upper bound on the length of the tour.

If we can find a tour with this length, our job is done. In some case, it's possible. Let's investigate!

First, if we have the medians of the X and the Ys as in the list above, we can separated the field like below :

 A  | B
    |
---------
    |
 C  | D

The lines corresponds to the median for both X and Y.

At most one city will lie on each of the median lines (recall our assumption that X and Ys are distinct).

Let's call each A B C and D as boxes. Below, we will refer box A as simply A (applies to B, C, and D too)

To obtain the value above, from a city in B we must go to a city in C. Same reasoning yields : B->C, C->B, A->D, D->A. Here, pairs of cities become apparrent, A and D are paired as well as B and C.

First, if either A+D is empty or B+C is empty, then we can obtain the upper bound above. We simply alternates between the two remaining pair. So let's assume that A+D is not empty and B+C is not empty.

First, let's investigate the relationship between B and C (A and B will also exhibits this relationship).

Theorem 1:

|B — C| <= 1.

Why:

First, if there are no cities in the medians or there is a single city in the center of the median :

A median divides the region into two areas with the same number of cities, so we have:

a) A+B = C+D
b) A+C = B+D

substituting A from a to b yields :

(C+D-B)+C = B+D
2C = 2B
B = C

And the theorem follows.

Next, suppose there are two cities in the median, one for each median line :

Let's suppose the median is one above and one on the right. All other cases will be similar. By definition of median...

a) (A + B + 1) = (C + D)
b) (A + C) = (B + D + 1)

Substituing a into b yields

(C + D - B - 1 + C) = (B + D + 1)
2C = 2B + 2
C = B + 1

which also implies A = D

Applying the same technique to other cases will give:

C = B and A = D+1
C = B-1 and A = D
C = B and A = D-1

And the theorem follows.

Note also that the one with the extra 1 city will be the one that is not adjacent to any median city (adjacent being the city lies in the boundary of the box)

OK, so in the following observations, we will assume the upper bound (that is, the sorted list of both X and Ys have their first half multiplied by -1 while the rest by +1), and trying to find a solution that's as close as possible to this upper bound.

The following will be another case analysis.

Theorem 2:

If there are two cities in the medians (that is, one in each median line), then the upper bound can be achieved.

Why:

We use pair of boxes to denote either A and D or B and C. From the second part of the proof for theorem 1, there will be a pair of boxes that contain different number of cities. Let's pick this pair, and start at the one with the most boxes. We keep alternating with its pair until we end up back in our starting box. Then, we simply move to either of the median city. From there we move to the other pair of box, the farthest one of the two. Alternate between the two, go to the other median city, and return to the starting city. It's easy to see that this will be optimal and have the upper bound as its value.

Now, let's see if there are no cities in the medians. First of all, this implies that the number of cities is even. Second, this implies that our upper bound which has the X and Y lists as -1 -1 -1 ... -1 1 ... 1 1 1 will not work (since this implies we have to continuously alternate between the two pairs of boxes, however, we can't switch between the pair of boxes). So, at least a modification would be required. The smallest possible modification is obtained by swapping the medians, that is, it becomes : -1 -1 -1 ... -1 -1 1 -1 1 1 ... 1 1 1. This is sufficient. Why? So, there are two cities that changes since the number of cities is even. Furthermore, these two cities will be the closest to the median line (let's assume these coordinates are X, that is, they're the closest to the vertical median line) and lies at two different boxes. Then, we proceed as follows. We start at one of these two cities. Alternate and end at the other side. If the other city is at that box, we make it so that we end at that city, and in this case, we can move to a city in the other box pair while respecting the list of X coordinates (we can do so since this city is the closest to the median line). Otherwise, the city will be in the other pair of boxes. We simply move there and it can be shown that we still respect the list of X coordinates. Alternate and at the end, go back to the starting city. All of these can be shown to still respect the list above.

This is optimal since this is the next largest possible upper bound if upper bound cannot be achieved.

Now, if there is a single city in the center of both medians, then the upper bound cannot be achieved. To see this, the upper bound can only be achieved if from a city in a box we move to another city in its box pair or to the center city. However, since both pair of boxes contains a city, we will need to move at least twice between them. Since there's only one center city, this is not possible.

Observe that this case implies an odd number of cities. Hence, we can't simply swap the median since it swaps the x coordinates of the same median city. Instead, we do this :

-1 -1 ... -1 -1 1 1 -1 1 ... 1 1

or

-1 -1 ... -1 1 -1 -1 1 1 ... 1 1

That is, we swap to either one of the neighboring city. With the same reasoning as above, we can show that we respect this list of X coordinates.

To achieve O(N) expected performance, note that the only operations we need are : grouping elements into boxes and median finding. Both can be done in expected O(N) time (expected since although there is a worst-case O(N) selection algorithm, it's ugly).

Thoughts:

Actually I intended to reword this into a three-paragraph weird story, but that seems a little too evil >:), so it was left out.