The profile page https://www.facebook.com/codingcompetitions/profile is broken, at least for my account. Initially the page loads, and shows "Meta Hacker Cup — 2023: T-Shirt" information, which I missed in 2023 and didn't claim. In about 10 second, the page automatically refreshes itself and shows a blank page "This page isn't available". The profile page has been this way for over a month and I assume the problem is not specific to my account.

The tutorial is very intuitive and easy to follow, as my solutions happen to match the tutorial ones on all the problems. I enjoy the whole set, particularly G and H as they offer challenges but not too hard for div 4. Thanks for the quick tutorial!

O(N) solution for E1. The logic is based on examples and reasoning, despite not a complete and rigorous proof. https://codeforces.me/contest/2003/submission/278303362

The idea is to assign value 0 or 1 to a signature array that can be used to uniquely yield the optimal permutation (similar to the concept in tutorial). There are 2 separate passes. In the first pass, we handle intervals in head and tail and meet in the middle, and maintain counters for number of 0 in prefix and number of 1s in suffix. It is optimal to place 0111...1 in head if pre0 <= suf1 and otherwise place 00...01 in tail. In the second pass, we handle indexes not within any interval. In this phase, it is optimal to have value 1 at the index if pre0 < suf1 and 0 otherwise.

I actually find the time limit is super tight. With the same core idea, it takes me dozens of iterations to make my Java solution be accepted, with lots of optimizations to reduce runtime and a special handling for the scenario of test 76. A time limit of 4 second instead of 3 would be better. The tight memory limit prevent me from using more time-efficient lookup table but is relatively less critical than time limit in my case.

I got that. I mentioned a few other involved overheads or factors, including I/O (Input and Output) and initialization delay. For example, even if n is only 10, the system may take O(300ms) to evaluate the submission regardless, and the overhead may vary a lot across different languages. We already know that the I/O delay matters, sometime much more in one language than the other, which explains all kind of tricks to make the I/O faster, at the cost of low level code with poor readability. The desire to set small/tight time limit, may unnecessarily create unfair hardships for specific set of languages. For example, I encountered problem with such a tight limit that it is impossible to be Accepted in Java, with the exact algorithm and similar code.

O(100000) stands for Order of 100000 accepted submission.

I am not an author. I do noticed system slowness in div 4 contest. I am not sure the exact reason but think larger number of participants and more submissions (due to easier problems) are the main reasons. For example:

• the most recent div 4 contest has about 46k participants and O(100000) accepted submissions;
• the most recent div 2 contest has 36k participants and O(50000) accepted submissions;

So the system has double traffic in div 4 contest than in div 2 contest, which I think is the main reason of the relative slowness.

It is unclear to me by how much reducing time limit like in 1980C from 2 to 1 second would help, as many submissions take less than 1 second already and 2 second is not a big number. Also reducing the time limit to bare minimal as indicated by the optimal solution is not cost free:

• the relative overhead due to I/O or language will be amplified;
• the tolerance for alternative sub-optimal solution become narrowed;
• more discouragement for beginners in div 4 contest.

The real optimization, as in my opinion, is to improve the system capacity and performance, so it can deliver similar or better response time under double traffic, and prepare for increased traffic in the future due to CF become more popular.

I am puzzled at the statement of problem F for an hour and couldn't explain the sample output, until I realized that lower vertex in condition below is by depth instead of vertex id! Somehow I couldn't realize it earlier despite noticed the input is a rooted tree.

• for every bridge, all tree edges in the subtree of the lower vertex of that bridge should also be bridges;
• the number of bridges is as small as possible.

My guess is that trees used in the tests are randomly generated with depth O(logn) instead of O(n). Whoever curious on the exact reason can test their code with a deep tree.

After replacing the allocation of 200000 List (to group queries by node id) with int[][], the runtime drops from TLE to 921 msec. This is a nice learn of the overhead of Java List.

    List<Integer>[] nids = new ArrayList[n+1];
    for (int i = 0; i < t; i++) {
      int v = u[i];
      if (nids[v] == null) {
        nids[v] = new ArrayList<>();
      }
      nids[v].add(i);
    }

My Java solution was barely Accepted with the exact time limit of 1000 msec. The algorithm complexity is fine as far as I can tell. I tried to optimize the code without success and suspect it might be implementation language related. In this case, the time limit of 1 sec appears rather tight to me.

There are tests added by hack, like Test #50, contains 800 sub-tests each with 100x100 input, with a total sum of n x m 8000000, which is 80 times of the upper limit as promised in the problem. Now the whole thing become less interesting due to these invalid hacks.

Now it makes more sense. It appears that the hack used 200 tests of 100x100 matrix, with the sum of n*m being 2000000 which is 10 times of the limit as specified in the problem statement. So it is likely an invalid hack.

It is so surprising to see so many G solutions are hacked. Given that my rather standard DP solution https://codeforces.me/contest/1955/submission/255745682 is accepted just fine, now I wonder whether I have missed something important, like a more advanced approach that usually works better.

(I assume) The tool fetches the submission HTML page and then extracts the embedded test case. As the response page truncates the test input but only show first N characters of each test, I don't see how magically the tool works around it and likely it does not. To get test input with O(1000) numbers, people can throw exception in the code to show a chunk of such numbers and do it in O(20) submissions, which is rather tedious and not feasible for larger input.

The real solution would be for CF to provide a download link for compressed test inputs. Maybe the concern was additional network traffic and server load. It will be a nice feature to have.

If the expected answer is YES but your contest submission was NO, then it is wrong answer. If you wonder why it was NO in the contest submission, check the submitted source code as well, to tell whether you have modified the code afterward to get the expected YES answer now.

Have you downloaded the result you submitted during the contest and verified the results are expected?

Thanks for the contest and problems. I like a few things that are kind of unique in Hacker Cup:

1. I like the relaxed 72/24 hours time limit of the qualification round and original round 1. It allows me to solve all the problems thoroughly without tight time constraint, which is usually the case of problem solving in real projects. One example is problem D, I was able to solve it after thinking about it on and off for 2 days, after two in-correct/slow versions. I really enjoy the journey.
2. Thorough testing is necessary and feasible given the relaxed time constraints, which again mimics real software development.
3. Submitting results requires people to avoid deep recursion code that may lead to stack overflow in local run, which is a good practice to encourage.

Based on AM-GM Inequality, a set of numbers with specific sum will have largest product if all the numbers are equal. Increasing the smallest digit will make these digits be closers to their average. It is not a solid proof but rather an intuitive way to quickly realize it.

(not verified with code but just based on code review): The raw tmp value range is [0,n] and then adjusted to [0,n-1]. When tmp is 0, gap should be 0 instead. To fix, do not adjust tmp, but compute gap with:

  gap = mid * tmp - (tmp == 0 ? 0 : dp[tmp-1]);

I see nothing wrong with F. Time wise, it took me much longer to solve G.

               problem: A  B  C  D  E  F  G  H
  num_minutes_to_solve: 6  2 10  3  5 26 63 28

The constraint does not have to be at the tight lower bound. 51 might serve as a big hint; author might have other legit ideas to solve the problem etc.

Problem C has either too big T or too tight time limit. For example, it could have a limit of T like 10000 instead of 100000. As a result, the problem would be more effective to accept Java solution with the right idea and algorithm. The way it is requires low level IO hacks to squeeze the last IO efficiency to possibly and barely meet the time limit, and as a result the IO code is messy and has poor readability etc, which is NOT the purpose no should be the focus of the problem.

After using a hack to workaround test #4 which always TLE in System Verdict, this submission https://codeforces.me/contest/1867/submission/223000398 is Accepted with runtime 1949 msec on test #6 where the input array has length 100000 and MEX 100000. It is unclear exactly how many IO interactions in test #6 as it depends on how greedily the Judge choose y each time.

Overall, the interactive IOs delays of problem C is too much for the given limit of T and timeout, and the problem is partially to do with the System Test. Problem C should either use a smaller limit like 10000 for T or a bigger timeout so to accept legit Java solutions without losing any generality of the problem.

My best guess is for test like #4 where T = 100000, the system judge does not generate the input data for next test in stdin fast enough after the previous test complete.

I tried to simulate stdin for 100000 tests each with n = 1 on local machine like below. It measured 185 msec. So the fact that test #4 always TLE in system tests suggest some kind of delay introduced by system test for Java submissions.

  static void simulateLargeNumOfTests() {
    long t0 = System.currentTimeMillis();
    {
      // Prepare stdin for 100000 tests each with n = 1 and mex 0.
      // In such case, an immediate -1 will follow after the input of each test.
      int T = 100000;
      StringBuilder sb = new StringBuilder();
      sb.append(T);
      sb.append('\n');
      for (int t = 1; t <= T; t++) {
        sb.append(1);
        sb.append('\n');
        sb.append(1 + RAND.nextInt(1000000000));
        sb.append('\n');
        sb.append(-1);
        sb.append('\n');
      }
      byte[] data = sb.toString().getBytes();
      InputStream fakeIn = new ByteArrayInputStream(data);
      System.setIn(fakeIn);
    }

    {
      MyScanner in = new MyScanner(true);
      int T = in.nextInt();
      OutputStream out = new BufferedOutputStream(System.out);
      for (int t = 1; t <= T; t++) {
        int n = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
          a[i] = in.nextInt();
        }
        solve(a, in, null, out);
      }
    }
    System.out.format("%d msec\n", System.currentTimeMillis() - t0);
    System.exit(0);
  }

Not necessarily related to MLE, but I wonder what's C++ sqrt()'s behavior on negative input because x * x — 4 * y could be negative.

The problem describes the game "Tic-Tac-Toe" and explains player win conditions, all like the "real" game rules. Configurations like below wouldn't be possible in "real" 3-person Tic-Tac-Toe games during which 3 players {X, O, +} would play in turns. Example 5 is more like a contradiction to the problem description in a quiet and non-intrusive (to both problem writer and testers) manner. Hacking test cases added later are more like invalid tests.

XO.  OOO
XXX  OOO
X+O  +.X

For me, the ambiguous part is restriction No 3. I can read the sentence more than a dozen times without really getting it. I imagine if the problem is described more mathematically, it will be easier for readers to get the precise meanings in shorter time.

I managed to get Accepted once with https://codeforces.me/contest/1842/submission/211112289. There are at least 5 tests completed with 1996 ms, under the limit only by 4 ms! The problem will be more friendly to have a time limit of 3 seconds or so instead.

It appears that the time limit of 2 seconds for problem 1842F is too tight for other languages except C++. I have tried all the optimizations I can think of in a Java implementation, but still see TLEs (and bunch of tests more than 1900 ms). Another evidence is, as of now, there are 10 pages of Accepted submissions, all in C++.

The time limit of 1 second is too tight for problem F, at least for Java language.

• Math.atan2(y,x) is convenient to get the angle of (x,y) in polar coordinate yet it is too expensive to be used for n = 300000 test case.
• BigInteger is convenient to represent the square sum precisely yet it is too expensive to be used for n = 300000 test case, so double is used instead.
• Precompute y/x ratio for points in each quadrant is necessary to sort them in angle order (compute each ratio long(n) times lead to TLE).
• The tight limit also forbit other variants of solutions that are essentially the same idea and complexity.

The main risk to have a very tight time limit is it rejects otherwise reasonable solutions that deviates from the tutorial one in some perspective, or code that are otherwise more intuitive and readable, which are important in software development.

Reference: https://codeforces.me/contest/1841/submission/209905657

Found the thread https://codeforces.me/blog/entry/115117 with manual binary search of the id.

John F. Kennedy's historic words: “Ask not what your country can do for you – ask what you can do for your country”

Editorial contains the formal proof. My intuition for the problem using n = 12 as example is below. To place {1,2,3,4,5,6,7,8,9,10,11,12} into 12 spots, among which 6 has positive contribution to the alternating sums. It always makes sense to place {7,8,9,10,11,12} into the positive spots.

    1 2 3 4 5 6
 1: + - + - + -
 2: - + - + - +

As v[1][1] and v[2][6] are both positive and always included, it always makes sense to place {12,11} into these two spots. A path would pass exactly one of v[1][3] or v[2][2], so it makes sense to place (10,9) into these two spots. I end up placing these 5 pairs (10,9)(8,7)(6,5)(4,3)(2,1) the way below with bigger value in second row. The intuition happens to be right.

     1  2  3  4  5  6
1:  12  5  9  3  7  1
2:   6 10  4  8  2 11

I think it should be "Let T_i consists of vertices x such that v_x = i". In other words, T_i consists of all the vertices which shortest distance to 1 is (i-1). It is also true that such x will appear i number of times in the final sequence.

First detect consecutive sequence of cities with non-descending fuel cost per liter. A round trip started at a city not in the sequence would visit all the cities in order from begin to end. A round trip started at a city within the sequence would visit the suffix cities and later all the prefix cities in the sequence. In either cases, because the fuel price is non-descending, it is always optimal to purchase as much fuel as sufficient to reach the end of the sequence limited to the tank capacity of course.

For each such sequence [B,E], we run DP to compute the pre[] and suf[] array where pre[i] is cost to reach i from B and suf[i] is the cost to reach E+1 from city i. Such computation is O(M) where M is the length of the sequence. I will skip more details to compute the pre and suf array.

Once we have all the individual sequences handled, for each city i, its round trip cost includes the whole cost of all other sequences it does not belong to, plus pre[i] + suf[i]. It takes O(N) to compute the value for all the cities as answer. Overall the complexity is O(N).

There are 4 * m points (x, y) that satisfies |x|+|y| = m for m >= 1. The diagram below shows points 4 + 12 = 16 points for m = 1 and 3. The total number of points for m = 1, 3, 5, ..., 2 * k — 1 is 4k^2. For k = 493827161, the value is 975461059765279684 which is greater than 975461057789971042, so the answer should be <= 2k-1 = 987654321.

            .
            o
         o  .  o
      o  .  o  .  o
.  o  .  o  .  o  .  o  .  .
      o  .  o  .  o
         o  .  o
            o
            .

An illustration that 987654320 won't work: if we use m = 0, 2, 4, 6, ..., 987654320, the total number of points is 1 + 4 * (2 + 4 + ... + 987654320) = 1 + 987654320^2 = 975461055814662401 which is one less than the required 975461055814662402 in your example.

I solved F after the contest with a solution that is O(n) 198883707, then noticed that each b_i is limited to either 1 or 2. The 1 or 2 constraint is essentially not required and would only slightly simplify the code.

The tree in the first example input is like below. Each node has two numbers id and value.

     1:1
      |
     2:5
    /   \
  3:2   6:1
  /  \
4:3  5:1

The first query is (4,5), which has following path to root respectively:

  4: 4:3 3:2 2:5 1:1
  5: 5:1 3:2 2:5 1:1
  3*1 + 2*2 + 5*5 + 1*1 = 3 + 4 + 25 + 1 = 33

multiple corresponding value of these nodes we have the answer 33 for the pair (4,5).

If you understand this example and apply the idea generally you will get a "naive" solution. If you could NOT understand this example, I suggest you focus on solving problem A, B, C instead and skip E and above.

Firstly try to implement an "naive" solution that would give right answers without worrying about execution times. One way to verify its correctness is to pass the first several tests.

Then, analyze why the solution takes long time on larger trees, and think about how to optimize it. One natural idea is to memorize the result of visited pairs (x, y) in a map and re-use the results in future queries. Such "natural" idea however would still lead to TLE and require more optimizations.

One such optimization is to skip adding pairs to the cache in the first M (like 1000) steps walking-up the tree. More other ideas were discussed in the thread.

At my first glance, I read the round as Newbie Welcome Round — simple and friendly problems to welcome new people join Codeforces.

A problem F that is usually solved by 1 or 0 people in Div 2 satisfies the desire of unofficial participants from Div 1 but will be ignored by most Div 2 participants during the contest, as if it never existed. Maybe I will have a different view/desire once become more advanced, but currently feel such F will add more stress and intimidation, at least during the contest.

Less than 20 people in Div 2 solved E, less than 10 people in Div 2 solved E with 10+ minutes left.

Maybe the code is close to avoid TLE so you can try a few minor optimizations. For examples:

A. Change

    full = min(seg_tree[2 * ind + 1][0], seg_tree[2 * ind + 2][1]);
    seg_tree[ind][2] += full + seg_tree[2 * ind + 1][2] + seg_tree[2 * ind + 2][2];
    seg_tree[ind][0] = seg_tree[2 * ind + 1][0] + seg_tree[2 * ind + 2][0] - full;
    seg_tree[ind][1] = seg_tree[2 * ind + 1][1] + seg_tree[2 * ind + 2][1] - full;

    to be:
    int[] s1 = seg_tree[2 * ind + 1];
    int[] s2 = seg_tree[2 * ind + 1];
    int[] s = seg_tree[ind];
    full = min(s1[0], s2[1]);
    s[2] += full + s1[2] + s2[2];
    s[0] = s1[0] + s2[0] - full;
    s[1] = s1[1] + s2[1] - full;

B. Simplify query() to return int instead of vector.

C. Use int[4*n][3] instead of:

    vector<vector<int>> seg_tree(4 * n, vector<int>(3, 0));

An Introduction to Fast Fourier Transform video: https://www.youtube.com/watch?v=h7apO7q16V0 and convolution video: https://www.youtube.com/watch?v=KuXjwB4LzSA

For the above problem, firstly identify the coefficients of polynomial P as determined by A. For example: [2,2,4,1,5,5] -> [0,1,2,0,1,2] -> P(x) = x + 2x^2 + x^4 + 2x^5

Then use FFT to calculate P^2(x) in O(nlong(n)) time. In the above example:

[0,1,2,0,1,2] -> [0,0,1,4,4,2,8,8,1,4,4,0,0,0,0,0]
P^2(x) = x^2 + 4x^3 + 4x^4 + 2x^5 + 8x^6 + 8x^7 + x^8 + 4x^9 + 4x^10
subtract 1 for each squares of term with itself: x^2 x^4 x^4 x^8 x^10 x^10
Q = [0,0,0,4,2,2,8,8,0,4,2,0,0,0,0,0]
  = 4x^3 + 2x^4 + 2x^5 + 8x^6 + 8x^7 + 4x^9 + 2x^10
           ^      ^^
          c=4     c=5

Finally add up Q[c] for each c in A, divide by 2 will be the number of qualified triples (a,b,c) in A. In the above case, 3 for (2,2,4) (1,4,5) (1,4,5).

c in the above code appears to be a constant, but in the problem, (a,b,c) are triples in the array A.

I rarely read editorials but instead often spend hours, sometime across a period of multiple days, to ponder about a hard problem and implement experimental code to verify ideas and its efficiency. During such iterations, more and more ideas are explored, covered, verified or dismissed. Intuitions sometime suddenly arise during showers, toilet time or bed time etc. I feel such exploration and iterations are fruitful and enjoyable, despite it cost times.

Another minor reason is editorial if often not presented in a "natural" thinking order but rather a final summary of a sophisticated solution, with lots of intermediate dots to be connected by the reader.

A downside of my approach is despite I solved the problem in the end, there is chance that it is inferior in some perspective but I missed learning other better approach as offered by the editorials. I hope once I am able to solve more and more problems faster, I would have the bandwidth to digest editorials afterward to learn potential new ideas.

Below is an counter-example with all 3 strings. All the 6 merging results exceeds maximal length 12: 11111000 00000000 00101111

  11111000 00000000 -> 1010101010000
  11111000 00101111 -> 10101101010101
  00000000 11111000 -> 0101010101000
  00000000 00101111 -> 0001001010101
  00101111 11111000 -> 0101101101010
  00101111 00000000 -> 0010010101010

Auto comment: topic has been updated by dzhi (previous revision, new revision, compare).

There is usually no motivation to click the link for the scheduled time, as people stay in the same time zone and most periodical contests start at the same time 07:35.

I don't recall seeing the "unusual start time" when I register, but maybe I have missed it, as I do recall seeing such words before.

The countdown until the contest starts does reveal a difference, despite usually I find no need to digest that number the day before.

If I have a suggestion for the CONTESTS page, is to highlight the start time of the coming contest that is periodical but does not start at the usual 07:35.

Your suggestion is valid (and independent/compatible to my suggestion). I have no evidence that you are a joke, but maybe lack of empathy and hence low EQ, which you will learn more in your future life.