czy jestem za głupi by programować? Opcje

[porzeczki]

Włączyłem pierwszy lepszy test na codility.com i głowa boli. Czy to dla was bułka z masłem? przez dwie godziny nie udało mi się napisać algorytmu na papierze, nie mówiąc o php. Coś takiego ma rozwiązać kandydat na JuniorPHP?

https://codility.com/programmers/challenges/titanium2016/

A bracket sequence is considered to be a valid bracket expression if any of the following conditions is true:

it is empty;
it has the form "(U)" where U is a valid bracket sequence;
it has the form "VW" where V and W are valid bracket sequences.
For example, the sequence "(())()" is a valid bracket expression, but "((())(()" is not.

You are given a sequence of brackets S and you are allowed to rotate some of them. Bracket rotation means picking a single bracket and changing it into its opposite form (i.e. an opening bracket can be changed into a closing bracket and vice versa). The goal is to find the longest slice (contiguous substring) of S that forms a valid bracket sequence using at most K bracket rotations.

Write a function:

class Solution { public int solution(String S, int K); }

that, given a string S consisting of N brackets and an integer K, returns the length of the maximum slice of S that can be transformed into a valid bracket sequence by performing at most K bracket rotations.

For example, given S = ")()()(" and K = 3, you can rotate the first and last brackets to get "(()())", which is a valid bracket sequence, so the function should return 6 (notice that you need to perform only two rotations in this instance, though).

Given S = ")))(((" and K = 2, you can rotate the second and fifth brackets to get ")()()(", which has a substring "()()" that is a valid bracket sequence, so the function should return 4.

Given S = ")))(((" and K = 0, you can't rotate any brackets, and since there is no valid bracket sequence with a positive length in string S, the function should return 0.

Assume that:

string S contains only brackets: '(' or ')';
N is an integer within the range [1..30,000];
K is an integer within the range [0..N].
Complexity:

expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N) (not counting the storage required for input arguments).

Ten post edytował porzeczki 10.11.2016, 18:10:57

[SmokAnalog]

Na pierwszy rzut oka to zadanie jest bardzo trudne, ale musi być łatwe rozwiązanie, skoro oczekują O(n). Najtrudniejsze jest to, że trzeba znaleźć długość sekwencji, ale nie jest powiedziane, że musi być to sekwencja od początku S.

Nie lubię takich zadań, bo mnie przytłaczają (IMG:style_emoticons/default/biggrin.gif)