0
\$\begingroup\$

Link: https://www.hackerrank.com/contests/hackerrank-all-womens-codesprint-2019/challenges/visually-balanced-sections/problem

Problem Description

A rack has \$n\$ horizontal compartments. The leftmost compartment is the \$1^{st}\$ compartment and the rightmost compartment is the \$n^{th}\$ compartment. Each of the compartments of a rack has a colorful item. A section of a rack consists of one or more consecutive compartments.
enter image description here

A section (\$i^{th}\$ compartment to \$j^{th}\$ compartment where, \$i \le j\$) of a rack is visually balanced if the items within the section can be re-arranged in such a way that the color sequence of the items from the \$i^{th}\$ compartment to the \$j^{th}\$ compartment is same as the color sequence of the items from the \$j^{th}\$ compartment to the \$i^{th}\$ compartment.

Few examples of visually balanced sections are:
enter image description here
enter image description here
enter image description here

Note that, in the third example, the items in this section can be re-arranged in such a way that the color sequence of the items from the \$1^{st}\$ compartment of this section to the compartment of this section will be same as the color sequence of the items from the compartment of this section to the \$1^{st}\$ compartment of this section.

Given the colors of each of the \$n\$ items of a rack, your task is to determine the number of visually balanced sections of a rack.

Function Description

Complete the visuallyBalancedSections function in the editor below. It should return an integer denoting the number of visually balanced sections of a rack..

visuallyBalancedSections has the following parameter(s):

colors: an integer array representing the colors of item in each compartment

Input Format

  • The first line contains a single integer \$t\$ denoting the number of scenarios.
  • The first line of each scenario contains a single integer \$n\$ denoting the number of compartments of a rack.
  • Each of the next line \$i\$ of the \$n\$ subsequent lines (where \$1 \le i \le n\$) of a scenario contains an integer \$color\$ denoting the color of the item in the \$i^{th}\$ compartment.

Constraints

  • \$1 \le t \le 100\$
  • \$1 \le n \le 1000\$
  • \$1 \le color \le 50\$

Output Format

  • For each scenario, print an integer denoting the number of visually balanced sections of a rack.

Sample Input 0

1
4
1
2
1
2

Sample Output 0

7

Explanation 0

There is only one scenario where the rack has four compartments.

  • The \$1^{st}\$ compartment has an item of \$= 1\$.
  • The \$2^{nd}\$ compartment has an item of \$= 2\$.
  • The \$3^{rd}\$ compartment has an item of \$= 1\$.
  • The \$4^{th}\$ compartment has an item of \$= 2\$.

The visually balanced sections are:

  1. {\$\{1\}\$} - compartment 1
  2. {\$\{2\}\$} - compartment 2
  3. {\$\{1\}\$} - compartment 3
  4. {\$\{2\}\$} - compartment 4
  5. {\$\{1, 2, 1\}\$} - compartments 1, 2 and 3
  6. {\$\{2, 1, 2\}\$} - compartments 2, 3 and 4
  7. {\$\{1, 2, 1, 2\}\$} - compartments 1, 2, 3 and 4

This current solution times out. I have an idea for a faster solution with memoisation, but I'm still working on it so I decided to submit this for review in the interim.

Current Solution

from collections import defaultdict
from copy import copy

def is_palindrome(counter):
    return len(list(filter(lambda x: x%2, counter.values()))) == (1 if sum(counter.values()) % 2 else 0)

def visuallyBalancedSections(colours):
    counter = defaultdict(lambda: 0)
    total = 0
    for i, val in enumerate(colours):
        counter[val] += 1
        temp_counter = copy(counter)
        for j in range(i+1):
            total += int(is_palindrome(temp_counter))
            temp_counter[colours[j]] -= 1
    return total
\$\endgroup\$
  • \$\begingroup\$ I hadn't read your advice as at when I wrote the code. \$\endgroup\$ – Tobi Alafin Mar 19 at 5:26
  • \$\begingroup\$ In future code, I would probably not alias it, but I had already written the code in this answer by the time you guys made your comment (uploading came much later because formatting the question is stressful). \$\endgroup\$ – Tobi Alafin Mar 19 at 5:30
  • \$\begingroup\$ @Ludisposed __________________ \$\endgroup\$ – Tobi Alafin Mar 19 at 5:32
  • \$\begingroup\$ All that explanation really boils down to "compute the number of (possibly overlapping) substrings that are permutations of palindromes", doesn't it? I think that reproducing the problem statement word-for-word really isn't a good use of your time and effort. \$\endgroup\$ – Toby Speight Mar 19 at 8:27
  • \$\begingroup\$ I thought it would be better to produce the original rather than my interpretation of it, as it is possible I may misunderstand something, and reading the original may give prospective reviewers access to some key insight. But I'll consider your suggestion going forward. \$\endgroup\$ – Tobi Alafin Mar 20 at 7:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.