We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Counting Special Sub-Cubes

Counting Special Sub-Cubes

Problem
Submissions
Leaderboard
Discussions
Editorial

Given an cube, let (where ) denote the value stored in cell .

A sub-cube (where ) of an cube is considered to be special if the maximum value stored in any cell in the sub-cube is equal to .

For each in the inclusive range , calculate the number of special sub-cubes. Then print each as a single line of space-separated integers (i.e., ).

Input Format

The first line contains an integer, , denoting the number of queries. The subsequent lines describe each query over two lines:

  1. The first line contains an integer, , denoting the side length of the initial cube.
  2. The second line contains space-separated integers describing an array of integers in the form . The integer in some cell is calculated using the formula .

Constraints

  • where

Output Format

For each query, print space-separated integers where the integer denotes the number of special sub-cubes for .

Sample Input

2
2
2 1 1 1 1 1 1 1
2
1 1 1 1 2 1 1 2

Sample Output

7 1
6 1

Explanation

We must perform the following queries:

  1. We have a cube of size and must calculate the number of special sub-cubes for the following values of :

    • : There are sub-cubes of size and seven of them have a maximum value of written inside them. So, for , the answer is .
    • : There is only one sub-cube of size and the maximum number written inside it is . So, for , the answer is .

    We then print the respective values for each as a single line of space-separated integers (i.e., 7 1).

  2. We have a cube of size and must calculate the number of special sub-cubes for the following values of :

    • : There are sub-cubes of size and six of them have a maximum value of written inside them. So, for , the answer is .
    • : There is only one sub-cube of size and the maximum number written inside it is . So, for , the answer is .

    We then print the respective values for each as a single line of space-separated integers (i.e., 6 1).

Author

nikasvanidze

Difficulty

Medium

Max Score

50

Submitted By

793

Need Help?


View discussions
View editorial
View top submissions

rate this challenge

MORE DETAILS

Download problem statement
Download sample test cases
Suggest Edits
  • Contest Calendar
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature