banner
kanes

kanes

HomeArchives

MiHoYo Written Test - Java Backend

48
AI Translation
This post is translated from Chinese into English through AI.View Original
AI-generated summary
The text discusses a mathematical proof regarding the "digital convex hull interval" formed by the first \( i \) numbers. It establishes that this interval is a continuous range \([P_{\min}, P_{\max}]\), where \( P_{\min} \) is the minimum and \( P_{\max} \) is the maximum of the first \( i \) numbers. The proof shows that the entire range \([1, i]\) has a digital convex hull equal to \([P_{\min}, P_{\max}]\), and any subintervals will not extend beyond this range. For each \( i \), it is sufficient to maintain the minimum and maximum values of the prefix. If \( P_{\min} > 0 \), the smallest non-negative integer not included in the set is 0. If \( P_{\min} = 0 \), then all integers from 0 to \( P_{\max} \) are covered, and the answer is \( P_{\max} + 1 \). The text also includes a Java implementation with a time complexity of \( O(n) \) for this logic, which reads input values, calculates the prefix minimum and maximum, and determines the output based on the conditions described.

We can prove that for all intervals formed by the first iii numbers, their "numerical convex hull interval" is exactly a continuous interval [Pmin⁡,Pmax⁡][P_{\min},P_{\max}][Pmin​,Pmax​] (where

Pmin⁡=min⁡{a1,…,ai},Pmax⁡=max⁡{a1,…,ai}P_{\min}=\min\{a_1,\ldots,a_i\},\quad P_{\max}=\max\{a_1,\ldots,a_i\}Pmin​=min{a1​,…,ai​},Pmax​=max{a1​,…,ai​}

). This is because the entire interval [1,i][1,i][1,i] as a sub-interval has its numerical convex hull as [Pmin⁡,Pmax⁡][P_{\min},P_{\max}][Pmin​,Pmax​]; while the intervals given by other sub-intervals are all sub-intervals of this interval, and cannot extend beyond the values of the entire continuous interval.

Therefore, for each iii, we only need to maintain the minimum and maximum values in the prefix, thus:

  • If Pmin⁡>0P_{\min}>0Pmin​>0 (that is, 0 does not appear in the prefix), then the entire set does not contain numbers from 000 to Pmin⁡−1P_{\min}-1Pmin​−1, at this time the smallest non-negative integer is 000.
  • Otherwise (that is, Pmin⁡=0P_{\min}=0Pmin​=0), then from the entire interval [0,Pmax⁡][0,P_{\max}][0,Pmax​], it can be seen that all numbers from 000 to Pmax⁡P_{\max}Pmax​ are covered, and the answer is Pmax⁡+1P_{\max}+1Pmax​+1.

Below is the Java implementation, with a time complexity of O(n)O(n)O(n):

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        // Use BufferedReader to read input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line = br.readLine();
        // The first line can only contain one integer n
        int n = Integer.parseInt(line.trim());
        
        // Read the array
        int[] a = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }
        
        // Prefix minimum and prefix maximum
        int prefixMin = Integer.MAX_VALUE;
        int prefixMax = Integer.MIN_VALUE;
        
        // Construct the answer
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            prefixMin = Math.min(prefixMin, a[i]);
            prefixMax = Math.max(prefixMax, a[i]);
            
            // If the prefix does not contain 0, then all intervals of [1,i] do not contain 0, the answer is 0;
            // Otherwise, the answer is the prefix maximum plus 1
            if (prefixMin > 0) {
                sb.append("0");
            } else {
                sb.append(prefixMax + 1);
            }
            if (i < n - 1) {
                sb.append(" ");
            }
        }
        
        System.out.println(sb.toString());
    }
}

Code Explanation#

  1. Input Handling
    Use BufferedReader and StringTokenizer to improve reading efficiency for large data volumes.

  2. Maintaining Prefix Extremes
    Continuously maintain the minimum (prefixMin) and maximum (prefixMax) values of the first iii numbers in the loop.

  3. Judgment and Output

    • When prefixMin > 0, it indicates that there is no 0 in the prefix (thus no non-negative number smaller than 0), the answer is 0.
    • When prefixMin == 0, based on the interval coverage (from the entire sub-interval [0,prefixMax][0, prefixMax][0,prefixMax]), the answer is prefixMax + 1.

This approach only performs constant time operations for each iii, with an overall time complexity of O(n)O(n)O(n), which meets the requirement of n≤2×105n \le 2 \times 10^5n≤2×105.

Problem Description#

Given a binary string of length nnn consisting of 0s and 1s, we need to construct a square table with nnn rows and nnn columns, consisting of 0s and 1s. The first row is the original string sss, the second row is the string sss cyclically shifted to the right by one position, the third row is the string sss cyclically shifted to the right by two positions, and so on.

Find the maximum area of all triangles or rectangles composed of 0s in the table.

Input Description#

Input a binary string of length nnn consisting of 0s and 1s, where 1≤n≤50001 \leq n \leq 50001≤n≤5000.

Output Description#

Output the maximum area of all triangles or rectangles composed of 0s in the table.

Example 1#

Input#

00110

Output#

6

We can prove that due to the special construction of the table, every row is a right cyclic shift of the original binary string, the state of any shape (strictly speaking, its "numerical convex hull", which is the interval composed of all cells corresponding to j−ij-ij−i (mod nnn)) depends only on a certain segment of consecutive zeros in the original string. Through simple analysis, we can prove:

  • If we select a "rectangle" (i.e., a continuous hhh rows and continuous www columns) sub-region, the j−ij-ij−i values corresponding to all its cells form the set

{D−(h−1,D−h+2,…,D+w−1}\{\, D - (h-1),\, D-h+2,\dots,\,D+w-1\,\}{D−(h−1),D−h+2,…,D+w−1}

(where DDD is some offset), which is actually an integer interval of length w+h−1w+h-1w+h−1 (note that there will be overlaps between adjacent rows). It is clear that to make the area fully 0, there must be a segment of zeros in the original string with a length of at least w+h−1w+h-1w+h−1; and in the case of non-all-zero (i.e., w+h−1<nw+h-1<nw+h−1<n), through optimal selection, it can be proven that the maximum rectangle area is

R(L=⌊L+12⌋⋅⌈L+12⌉,R(L)=\lfloor\frac{L+1}{2}\rfloor\cdot\lceil\frac{L+1}{2}\rceil,R(L)=⌊2L+1​⌋⋅⌈2L+1​⌉,

where LLL represents the length of the longest continuous segment of zeros in the original string.

  • Similarly, if we only allow "right-angled triangle" shapes (for example, with the top left corner as the right angle, each subsequent row has one more cell than the previous row, the area is 1+2+⋯+h=h(h+1)21+2+\cdots+h=\frac{h(h+1)}21+2+⋯+h=2h(h+1)​), then if the height of the triangle is hhh, the j−ij-ij−i values it "uses" exactly form an interval of length hhh, thus requiring h≤Lh\le Lh≤L; in this way, the maximum triangle area is

T(L=L(L+1)2.T(L)=\frac{L(L+1)}2.T(L)=2L(L+1)​.

It is easy to verify that when L≥2L\ge2L≥2,

T(L=L(L+1)2>⌊L+12⌋⋅⌈L+12⌉=R(L),T(L)=\frac{L(L+1)}2> \lfloor\frac{L+1}{2}\rfloor\cdot\lceil\frac{L+1}{2}\rceil=R(L),T(L)=2L(L+1)​>⌊2L+1​⌋⋅⌈2L+1​⌉=R(L),

that is, in the case of non-all-zero, the optimal area depends on the "zero triangle" shape. Note: If the original string is all 0s, then all cells in the table are 0, and the maximum area is of course the entire table area n×nn\times nn×n (because n2>n(n+1)2n^2>\frac{n(n+1)}2n2>2n(n+1)​).

In summary, we can first scan the original string (considering it as circular) to find the length of the longest continuous segment of 0s LLL (if there are no 0s, the answer is 0); then determine:

  • If L=nL=nL=n (all-zero string), the answer is n2n^2n2;
  • Otherwise, the answer is L(L+1)2\dfrac{L(L+1)}22L(L+1)​ (which is the maximum area of a "zero triangle").

Below is the Java code implementation, with a time complexity of O(n)O(n)O(n):

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        // Read the input binary string (original string s)
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine().trim();
        int n = s.length();
        
        // Calculate the length L of the longest continuous segment of 0s in the original string (considering it circular)
        int L = 0;
        int curr = 0;
        // Scan once (not considering the connection between the head and tail of the ring)
        for (int i = 0; i < n; i++) {
            if (s.charAt(i) == '0') {
                curr++;
                if (curr > L) {
                    L = curr;
                }
            } else {
                curr = 0;
            }
        }
        // If both ends are '0', try to update L using circular connection
        if (n > 0 && s.charAt(0) == '0' && s.charAt(n - 1) == '0') {
            int prefix = 0, suffix = 0;
            for (int i = 0; i < n && s.charAt(i) == '0'; i++) {
                prefix++;
            }
            for (int i = n - 1; i >= 0 && s.charAt(i) == '0'; i--) {
                suffix++;
            }
            if (prefix + suffix > L) {
                L = prefix + suffix;
            }
            // Note that L can be at most n (length of the original string)
            if (L > n) {
                L = n;
            }
        }
        
        long ans = 0;
        // If there are no 0s in the original string, the answer is 0
        if (L == 0) {
            ans = 0;
        }
        // If the original string is all 0s, then every element in the table is 0, the answer is n*n
        else if (L == n) {
            ans = (long) n * n;
        }
        // Otherwise, the best area comes from the "zero triangle", with an area of L*(L+1)/2
        else {
            ans = (long) L * (L + 1) / 2;
        }
        
        System.out.println(ans);
    }
}

Code Explanation#

  1. Finding the Longest Continuous Segment of 0s (Circular)
    First, scan forward to count the number of continuous 0s; also note that if both the head and tail of the string are 0, they can connect in a circular manner, so additionally calculate the number of 0s at the head and tail, and update the longest continuous count LLL (but LLL can be at most nnn).

  2. Determining the Answer

    • If L=0L=0L=0 (no 0s), the answer is 0.
    • If L=nL=nL=n (all 0s), the entire table is 0, the answer is n×nn \times nn×n;
    • Otherwise, the answer is L(L+1)2\frac{L(L+1)}{2}2L(L+1)​ (this is the maximum area when forming a "zero triangle").

Thus, we have achieved the goal of finding the maximum area of regions composed of 0s (triangles or rectangles) in the table within O(n)O(n)O(n).

Summary#

Since the value of each cell in the table only depends on s[(j−i)modn]s[(j-i) \bmod n]s[(j−i)modn], the entire problem reduces to finding the length of the longest segment of zeros LLL in the original string; and it is proven that in the case of non-all-zero, the area of the "zero right triangle" is

L(L+1)2,\frac{L(L+1)}2,2L(L+1)​,

which is always greater than the area of the rectangle with the same restrictions. Therefore, the final answer is:

  • If sss is all 0s: the answer is n2n^2n2;
  • Otherwise: the answer is L(L+1)2\frac{L(L+1)}{2}2L(L+1)​.

This approach not only reduces the time complexity (only O(n)O(n)O(n)), but also utilizes the special property of "cyclic shifting" when constructing the matrix.

Loading...
Ownership of this post data is guaranteed by blockchain and smart contracts to the creator alone.