Introduction to algorithms with java-Shakutori method

Article summary

This is a series of articles that I have compiled in my study and memo. The sixth bullet. Click here for previous articles.

# article
5 Introduction to algorithms with java-Cumulative sum
4 Introduction to algorithms with java-Search (bit full search)
3 Introduction to algorithms with java-Search (breadth-first search)
2 Introduction to algorithms with java-Search (depth-first search)
1 Introduction to algorithms with java-Search (full search, binary search)

In this article

-* Shakutori method *

I will study about. With cumulative sum? Is it the one used? I often see them introduced as a set.

Shakutori method

Like the cumulative sum, it seems to be a technique for speeding up operations on arrays of numbers.

Reference: [[Cumulative sum, shakutori method] Algorithm illustration that even beginners can understand](https://paiza.hatenablog.com/entry/2015/01/21/%E3%80%90%E7%B4%AF% E7% A9% 8D% E5% 92% 8C% E3% 80% 81% E3% 81% 97% E3% 82% 83% E3% 81% 8F% E3% 81% A8% E3% 82% 8A% E6% B3% 95% E3% 80% 91% E5% 88% 9D% E7% B4% 9A% E8% 80% 85% E3% 81% A7% E3% 82% 82% E8% A7% A3% E3% 82% 8B% E3% 82% A2% E3% 83% AB% E3% 82% B4)

Well ... it's a bit confusing if you look at the link. .. .. I will explain it for my own study.

As an example, consider an array of integers of size n. When divided into the length t of the specified interval from there, what is the maximum value of the sum within that interval? It is a problem to solve a typical problem. It's a problem that can be done with cumulative sums. See also the previous article (https://qiita.com/aja_min/items/3a334fb03749d8f42a25).

As an example, consider the case of size 5 (n = 5) and interval length 2 (t = 2). スクリーンショット 2020-08-02 14.26.30.png

Consider the array as shown. If you divide this by the length of 2 of the section, it will be as follows.

スクリーンショット 2020-08-02 14.28.27.png

From the conclusion, 4 + 10 = 14 of the sum when choosing the 4th and 5th is the highest value, but how much is the amount of calculation so far?

  1. Which section to select
  2. Calculation of sum within the interval

Let's think about it separately.

First of all, 1. How to divide the section, but it's easy. In the above example, the sum is taken four times. If you drop it in the formula, it will be n-t + 1 time. This time 5-2 + 1 = 4 times.

Next is 2. The calculation of the sum within that interval, but we are processing it twice to access each element of the array.

In general, it is (n --t + 1) * t times. Note that if t depends on n, the amount of calculation will be about O (n ^ 2). In this case, if n is taken as 10 ^ 5, it will take a tremendous amount of time. At that time, the Shakutori method was introduced.

Well, it's a relatively simple story ... Remember the sum so that you don't have to add from 1 each time. about it. See the figure below.

スクリーンショット 2020-08-02 14.49.09.png

Do you understand somehow? Remembering the sum, you don't have to add all the elements t times at a time. The complexity is n-t + 1 times because we no longer need to access each element of the array. I think it can be expressed as O (n).

Let's go to the example.

example

Example: AtCoder --abc032-c "column"

Click here to display problem sentences and input examples
* Please refer to the problem link as much as possible

(Section start) 【Problem statement】 There is a non-negative integer sequence S = s1, s2, ..., sN of length N and an integer K. Your job is to find the length of the longest contiguous subsequence of S that meets the following conditions: The length of the subsequence must be one or more columns.

-The product of the values of all the elements contained in the subsequence is K or less.

If there is no subsequence that meets the conditions, output 0.

【input】 Input is given from standard input in the following format.

N K
s1 
s2
:
sN

-In the first line, the integer N (1 ≤ N ≤ 105) representing the length of the sequence and the integer K (0 ≤ K ≤ 10 ^ 9) in the problem statement are given separated by spaces. -The value of each element in the sequence is given to the N rows from the second row. Of these, si (0 ≤ si ≤ 10 ^ 9) is written on the i (1 ≤ i ≤ N) line.

【output】 Output should be standard output in the following format. In the first row, output the length of the longest contiguous subsequence in which the product of the values of all the contained elements is K or less. If there is no subsequence that meets the conditions, output 0. Don't forget the newline at the end.

(End of section)


This is the problem. It's a little applied. It's basically a shaky method, but this time the length hasn't been decided. We will implement it according to the following policy.

--Save the product in the same way as the Shakutori method. --As long as the conditions are met, proceed to the right end. --When the conditions are no longer met, proceed to the left end. ――When the left end comes to the far right, the search ends. The longest value at that time is output.

Below is an example answer.

Main.java


import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt(); //Length of non-negative integer sequence
		long k = sc.nextLong(); //Maximum product

		long[] s = new long[n]; //Non-negative integer sequence

		for (int i = 0; i < n; i++) {
			s[i] = sc.nextLong();
			if (s[i] == 0l) {
				System.out.println(n);
				return;
			}
		}

		long seki = 1; //Variable storing the product
		int ans = 0; //Maximum length
		int ans_max = -1; //Save the answer
		int left = 0; //Left end
		int right = 0; //Right end

		for (left = 0; left < n; left++) {

			//Fix the left edge and move the right edge as far as you can go to multiply
			while (right < n && seki * s[right] <= k) {
				seki *= s[right++];
			}

			//Storage of maximum ans
			ans = right - left;
			if (ans_max < ans) {
				ans_max = ans;
			}

			//Move the left edge. left==Be careful when it becomes right.
			if (left == right) {
				right++;
			} else {
				seki /= s[left];
			}

		}

		System.out.println(ans_max);
	}
}

Yes. I referred to various sources, but it was quite difficult. .. The example where left catches up with right was especially difficult. This also seems to require practice. .. .. Let's practice well. I will read the source over and over again.

see you!

Recommended Posts

Introduction to algorithms with java-Shakutori method
Introduction to algorithms with java --Search (depth-first search)
Introduction to algorithms with java --Search (breadth-first search)
Introduction to algorithms with java --Search (bit full search)
Introduction to algorithms with java-Search (Full search, Binary search)
Introduction to algorithms in java-cumulative sum
Introduction to Design Patterns (Factory Method)
[Java] How to compare with equals method
Introduction to Ruby basic grammar with yakiniku
Introduction to Ruby 2
Introduction to SWING
Method to search
Introduction to web3j
Introduction to Micronaut 1 ~ Introduction ~
[Java] Introduction to Java
Introduction to migration
Introduction to java
Introduction to Doma
Introduction to Robot Battle with Robocode (Environment Construction)
Override protected method with anonymous class to stub
Introduction to Robot Battle with Robocode (Beginner Development)
How to avoid exceptions with Java's equals method
[Introduction to Spring Boot] Authentication function with Spring Security
Introduction to JAR files
[Introduction to Docker x ECS] ECS deployment with docker compose up
Introduction to Ratpack (8)-Session
Introduction to algorithms in java-lexicographic order / combination omnivorous (part1)
Introduction to RSpec 1. Test, RSpec
Introduction to bit operation
Introduction to Ratpack (6) --Promise
Introduction to PlayFramework 2.7 ① Overview
Introduction to Android Layout
Introduction to design patterns (introduction)
Introduction to Practical Programming
Introduction to javadoc command
Get started with "Introduction to Practical Rust Programming" (Day 3)
Introduction to jar command
Introduction to Ratpack (2)-Architecture
[Rails] devise introduction method
Introduction to lambda expression
Introduction to java command
Introduction to RSpec 2. RSpec setup
Introduction to Keycloak development
Introduction to RSpec 4. Create test data with Factory Bot
16 Corresponds to method invocation
Introduction to javac command
I tried to make an introduction to PHP + MySQL with Docker
I was addicted to setting default_url_options with Rails devise introduction
How to test a private method with RSpec for yourself
Introduction to Design Patterns (Builder)
Java to play with Function
Introduction to RSpec 5. Controller specs
Introduction to RSpec 6. System specifications
Introduction to Android application development
Introduction to RSpec 3. Model specs
Introduction to Metabase ~ Environment Construction ~
Introduction to Ratpack (7) --Guice & Spring
(Dot installation) Introduction to Java8_Impression
Introduction to Design Patterns (Composite)
Integer check method with ruby
Introduction to Micronaut 2 ~ Unit test ~