OJ task

Last updated on December 5, 2024 pm

Interesting Stones

A girl named Tomori likes to collect stones. There are so many types of stones in our world, that if we assign each type an integer number, it could be as large as $10^7$.

One day Tomori lined up her stones in a row. A stray cat came and said, “Your stones are not interesting.” The cat thinks a row of stones is interesting if and only if:

Every continuous subsequence of the row contains at least one stone of unique type, i.e. no other stone in this subsequence has that same type. (Only need to be unique within the subsequence.) (The entire row is a subsequence of itself.)

(A continuous subsequence of an array 𝑎[0…𝑛−1] is a subsequence 𝑎[𝑖],𝑎[𝑖+1],…,𝑎[𝑗] where 0≤𝑖≤𝑗<𝑛.)

Tomori wants to make friends with the cat. Can you develop a program to help her quickly determine whether her rows of stones are interesting?

Input

The first line contains an integer 𝑇(1≤𝑇≤200), the number of test cases. Then 𝑇 test cases follow.

The first line of each test case contains an integer 𝑛 (1≤𝑛≤10000), the number of stones in Tomori’s row. The second line contains 𝑛 non-negative integers (values < $10^7$) separated with single spaces, the types of stones in Tomori’s row.

Output

For each test case, output a single line of the word “Yes” if the row of stones is interesting, otherwise output “No”. Trailing whitespace or line break will be ignored.

Sample Input

1
2
3
4
5
6
7
8
9
4
5
1 2 3 4 5
5
1 1 1 1 1
5
1 2 3 2 1
5
1 1 2 1 1

Sample Output

1
2
3
4
Yes
No
Yes
No

Example Explained

This row is insteresting. I marked some subsequences (not all of them) in different colors, and the unique item(s) within them are marked red. You can check that for all subsequences, there is at least one unique item within.

Limits

  • Time limit: 2 s for C/C++; 4 s for Java/Python
  • (Stack+Heap) Space limit: 512 MB

Hints

  1. Solve the problem in 𝑂(𝑛log⁡𝑛) time with divide and conquer.

  2. You may get “Time Limit Exceeded” for the last 1 ~ 3 tests (depends on how good your code is). To overcome it, you need pre-processing. Why? Because we need a fast enough method to do unique check and unique finding. Make it as fast as possible. It’s crucial! And pre-processing, by its name, is something that happens before the recursion even starts.

    Considering that it’s hard to realize its necessity, more details are provided here. See the following figure. Is 3 unique within the subsequence between the brackets? Yes, because the previous and next positions where another 3 shows up are both outside the subsequence. This way it only costs 𝑂(1) time to check uniqueness, as long as we build up these “arrows” before the recursion starts. And your scan-and-find-unique procedure can early stop (see the next hint).

    So you need 2 utility arrays, each of the same length as the row. And to build them up, you may want to temporarily use a hashmap. See unordered_map (C++11), map (C++), HashMap (Java), dict (Python).

  3. To handle the worst case, it would be better to start from both ends …? That would be the key to getting the last 10 points.

    These two optimizations, i.e. pre-processing and handling the worst case, are both fighting a single common enemy: unbalanced recursion tree. You all know from class that partitioning at middle + Θ(𝑛) dividing/combining time = Θ(𝑛log⁡𝑛) total time. But what if the partitioning could happen everywhere? The recursion tree could be highly unbalanced, and it wouldn’t finish in Θ(𝑛log⁡𝑛) even if each node still cost Θ(𝑛) time. Draw on a paper and check it yourself.

    That’s why the unique-finding procedure should be fast and able to early stop once it finds a unique element (no need to do the full scan every time). And that starting from both ends is a simple yet effective way to short-circuit the worst case where the partitioning always happens at …?

    Hope this problem illustrates the significant impact that the cost of each recursive call can have on the total running time, particularly in the case of an unbalanced recursion tree.

  4. Try brute-force as last resort. Good outcomes.

  5. If you get wrong answer on the 1st test case, it surely means your algorithm is wrong. Yes, a simple check based on some necessary condition can kill most cases (same points as brute-force), but this problem is not that simple.

No more hints after this final update.

Quick facts about recursion in real world

  1. As recursion is typically used in D&C problems, you should notice that there is such thing as stack space limit in operating systems. Simply put, very deep recursion or very large local variables may cause stack overflow. Even it’s 2024, the OS on your PC probably still has a small default stack limit of 1MB/8MB/…

  2. But as stated on the OJ home page, stack space memory on this platform is counted together with heap space memory into total memory usage, not to be limited separately. You should only get stack overflow (would show as RuntimeError in the last 1 or 3 test cases) if you wrote really bad code. Additionally for Python users, please set a special parameter to allow for deep recursion. See Special notes for Python.

    • But don’t blame every RuntimeError on that. Your RuntimeErrors would mostly be caused by index out of range. Check the input value constraints carefully.

  3. In real world applications outside classroom, deep recursion should be avoided by switching to iterative algorithms. If that’s not possible, you can still get an iterative program by manually simulating the call stack. But that’s another story.

Special notes for Python

  • IMPORTANT: The recursion depth of this problem may exceed the default recursion limit of Python. You should add import sys and sys.setrecursionlimit(10005) to the beginning of your code.

  • Please avoid unnecessary list expanding operations. Python is too slow to afford that. For example,

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    # do this
    util_arr = [0] * maxn  # allocate only once
    for test_case in range(T):
      n = int(input())
      a = list(map(int, input().split()))
      for i in range(n):
        util_arr[i] = ...

    # instead of this
    for test_case in range(T):
      n = int(input())
      a = list(map(int, input().split()))
      util_arr = []  # a new empty list every time!
      for i in range(n):
        # when internal capacity is reached, expensive list expanding operation happens
        util_arr.append(...)

    Python code written in adherence to good programming practices should pass all test cases.

Minimum edge sum

You are given two separate rows of vertices. Let’s label the vertices, always from left to right, as $𝐴_1$ … $𝐴_𝑛$ ​ for the first row and $𝐵_1$ … $𝐵_𝑚$ ​ for the second row. Every vertex is assigned with an integer value, $𝑎_𝑖$ for $𝐴_𝑖$ and $𝑏_𝑗$ ​ for $𝐵_𝑗$ ​ (1≤𝑖≤𝑛 and 1≤𝑗≤𝑚, same for the following).

In this problem you are asked to draw edges to construct a bipartite graph from the given two rows of vertices. By using the term bipartite graph, we mean that every edge you draw should connect a vertex $𝐴_𝑖$ in the first row to a vertex $𝐵_𝑗$ in the second row, and we label this edge as 𝐸𝑖𝑗, whose weight is defined as 𝑒𝑖𝑗=∣$𝑎_𝑖$ − $𝑏_𝑗$∣ (the absolute difference between the two vertices’ values).

While drawing edges, you should follow these rules:

  1. The graph should be bipartite, as stated above;
  2. There should be an edge connecting $𝐴_1$ ​ and $𝐵_1$ ​, i.e. 𝐸11​ exists;
  3. There should be an edge connecting $𝐴_𝑛$ ​ and $𝐵_𝑚$, i.e. 𝐸𝑛𝑚​ exists;
  4. Every vertex should be connected to at least one other vertex (i.e. no “isolated vertices”);
  5. There can be at most one edge 𝐸𝑖𝑗 between any vertex pair (𝐴𝑖,𝐵𝑗) (i.e. no “multiple edges”);
  6. Edges should not cross each other. The following image shows examples of a valid and an invalid graph, with the bold red edges crossing each other.

To be more specific, if you draw an edge 𝐸𝑖𝑗, then you cannot draw any edge 𝐸𝑝𝑞 where (𝑝<𝑖 AND 𝑞>𝑗) OR (𝑝>𝑖 AND 𝑞<𝑗), because the two edges will cross each other.

The edge sum of a graph is defined as the sum of all edges’ weights. Your goal is to find a bipartite graph with the minimum edge sum, while following the rules above.

Input

The first line of the input contains two integers 𝑛 and 𝑚, separated with a single space, the number of vertices in the first and second row, respectively.

The second line contains 𝑛 integers $𝑎_1$ … $𝑎_𝑛$ ​, separated with single spaces, the values of the vertices in the first row.

The third line contains 𝑚 integers $𝑏_1$ … $𝑏_𝑚$ ​, separated with single spaces, the values of the vertices in the second row.

Output

An integer, the minimum edge sum of a valid bipartite graph. Trailing whitespace or line break will be ignored.

Sample Input

1
2
3
4 5
1 5 4 6
6 2 5 7 7

Sample Output

1
9

Sample Explanation

5+1+0+1+1+1=9

Constraints

  • 1≤𝑛,𝑚≤1000
  • Specially for test cases 1~6: 1≤𝑛,𝑚≤10
  • All $𝑎_𝑖$, $𝑏_𝑗$ are within the value range of a 16-bit signed integer, i.e. −32768≤$𝑎_𝑖$, $𝑏_𝑗$≤32767

Limits

  • Time limit: 1.5 s
  • Memory limit: 512 MB

Hints

  1. This is a dynamic programming problem. No requisite knowledge of graph algorithms is needed.
  2. The first step of solving a DP problem is often to define the state function courageously. But do make a clear definition without ambiguity.
  3. Think how the rules result in optimal substructure property along with a simple yet elegant DP recurrence (state transition equation).
  4. Draw on a paper: 1) the bipartite graph and 2) visualization of the DP state transition, to help thinking.
  5. Test cases 1~6 have small 𝑛 and 𝑚, allowing for a brute-force search/enumeration as your last resort.