10
\$\begingroup\$

The program needs to find all contiguous sublists of numbers where the number of occurrences of every member in the contiguous sublist is divisible by 2.

The first line of input is N (the number of ai, where N ≤ 353535). The second line of input contains the ai, delimited by spaces (where each ai < 109).

Here is an example of input and what the output should be:

# N is the user input, and a is the user input with 
#numbers separated by space and converted to list with .split(" ") but
#we'll look for examles first :
N = 8 
a = [3,5,3,5,9,9,5,3]

The output of this input should be 5 because there are 5 contiguous sublists that meet the conditions:

  • [3,5,9,9,5,3]
  • [3,5,3,5,9,9]
  • [5,9,9,5]
  • [3,5,3,5]
  • [9,9]

Here is my solution:

import time
total = 0
try:
    listlength = int(raw_input("Enter the number of list elements >> "))
    listofnumbers   = raw_input("Enter the list elements , space separated >>").split(" ")
    start = time.clock()
    for i in range(listlength,1,-1):
        for i1 in range(0,listlength + 1 - i):
            numbers = []
            countofnumbers=[]
            currentlist = listofnumbers[i1:listlength-abs(i-listlength+i1)]
            #print "I:",i,",TR nIZ ",tr_niz
            for k in currentlist:
                if k not in numbers:
                    numbers.append(k)
                    countofnumbers.append(currentlist.count(k) if currentlist.count(k)%2==0 else 0)
            if 0 not in countofnumbers:
                if sum(countofnumbers)%2==0:
                    total+=1

    print total
    print "Time: ",time.clock()-start

except ValueError:
    print "Data wrong"

My script solves small test cases really well. However, when there are 350350 numbers, It was working all the night, and it didn't turn up with result. How can I fix my algorithm to finish in a reasonable amount of time? Maybe implement multiprocessing because it's using 100% od my core when running , but doesn't use any of 3 other cores available ? And maybe some enhanced algorithm you suggest :)

\$\endgroup\$
  • 1
    \$\begingroup\$ Looking at his code it is pretty obvious that by subgroup he means "contiguous sublist," which would mean there's a typo in his explanation, and the third subgroup should be [5, 9, 9, 5]. But other than that it seems a well posed question. \$\endgroup\$ – Jaime Mar 30 '16 at 4:48
  • \$\begingroup\$ I agree with Jaime - it can only be contiguous subsequences, and the [5, 9, 5, 9] thing must be a simple transcription mistake. Otherwise the number of result groups would be higher. A valid question (classic TLE) with a really neat problem. \$\endgroup\$ – DarthGizka Mar 30 '16 at 5:10
  • \$\begingroup\$ I'm sorry for this subgroup, i didn't know how to express in english :) now i know, So the order really matters because you must search input for patterns. But output is as i listed only number of contiguous subsequences. My script does the following . Let's say i have input with 8 numbers, it'll first search first 7, then move one and search the other 7. Then it will search by 6, so it has 3 spaces to move, and so on, up to 2, where it has 7 spaces to move in input. That's how i split it into subsequences and check how many of each number is in that subsequence , if it matches the condition-> \$\endgroup\$ – Marko Mackic Mar 30 '16 at 9:38
  • \$\begingroup\$ It adds one to total.. now it all works where there is small number of items in list, just for comparison, for 100 items it takse 0.14 s, and for 1000 items it takes 159 s, let's round up (100 times loneger) I'd expect 140s and then for 350350 items, it would take a very long period to finish.. \$\endgroup\$ – Marko Mackic Mar 30 '16 at 9:55
  • \$\begingroup\$ EDIT TO the above, corrected it to fist search all the list, because i was skipping it :) so let's say it's 8, it will look if the whole list meets the condition, and then it will do 7,6, ... as explained in comment above. I edited the question with new code ,and edited subgroups to contiguous subsequences ... \$\endgroup\$ – Marko Mackic Mar 30 '16 at 10:26
3
\$\begingroup\$

The algorithm can be slimmed by tracking only those numbers for which the number of occurrences in the current window is unbalanced (i.e. odd). Whenever this auxiliary structure is empty, everything is balanced and the current window can be added to the set of solutions. Here's some pseudo code to illustrate the approach:

static void print_balanced_contiguous_subsequences (int[] a)
{
    var unbalanced = new HashSet<int>();

    for (int i = 0, e = a.Length - 1; i < e; ++i)
    {
        unbalanced.Clear();

        for (int j = i; j <= e; ++j)
        {
            if (unbalanced.Contains(a[j]))
                unbalanced.Remove(a[j]);
            else
                unbalanced.Add(a[j]);

            if (unbalanced.Count == 0) // print the newly found sequence
                for (int k = i; k <= j; ++k) 
                    Console.Write("{0}{1}", a[k], k < j ? ' ' : '\n');
        }
    }
}

However, this algorithm is still quadratic in n (20 ms for 1000 elements, 2 seconds for 10000) and the key idea for a proper solution still eludes me...

The original problem description might contain a clue, or some restriction that can be leveraged to design a faster solution. It would be nice if it could be quoted verbatim in the question, or at least linked (even if it is not in English).

\$\endgroup\$
  • 1
    \$\begingroup\$ OK, so the task is in Serbian, and link is here :staritakprog.dms.rs/takmicenja/2013.3.sio/tekstovi.pdf , it's the first one , I will try your solution, thanks ;) \$\endgroup\$ – Marko Mackic Mar 30 '16 at 12:52
  • \$\begingroup\$ @Marko: Interesting! The last two lines of the task description (about Ai <= 53 in 50% of tests?/testcases? and so on) should be translated and added to your question. The description of the task does not seem to specify a time limit. Is there a global/implied time limit mentioned elsewhere in the document? \$\endgroup\$ – DarthGizka Mar 30 '16 at 13:14
  • \$\begingroup\$ Nope :) just my code didn't pass the hardest case, and that's my problem, i ran for a day for only 350350 numbers, but anyways if your solution is efficient as quoted above it is really acceptible :) \$\endgroup\$ – Marko Mackic Mar 30 '16 at 13:18
  • \$\begingroup\$ But anyways what is the point of A(i) being small, when number of elements is high ? :) Like there are 20 test cases, and in the 4th the list of numbers contains 1000 elements, in 5th 15000(something a bit more) and then goes to 350350 elements :) \$\endgroup\$ – Marko Mackic Mar 30 '16 at 13:22
  • 1
    \$\begingroup\$ Yeah , it's working, i'll just post the code in python i wrote, thanks :) \$\endgroup\$ – Marko Mackic Mar 30 '16 at 15:03
1
\$\begingroup\$

So @DarthGizka solved it in efficient manner :) Here is the code in python :

import time
try:
        total = 0

        listofnumbers   = raw_input("Enter the list elements , space separated").split(" ")
        start = time.clock()

        for i in range(0,len(listofnumbers)-1):
            unbalanced = set()
            for k in range(i,len(listofnumbers)):
                if listofnumbers[k] in unbalanced:
                    unbalanced.remove(listofnumbers[k])
                else:
                    unbalanced.add(listofnumbers[k])
                if len(unbalanced) == 0:
                    total+=1

        print total
        print "Time : ",time.clock()-start

except ValueError:
        print "Data not ok"

1000 numbers takes 0.45 seconds to complete if anyone has more improvments let me know :) Thanks a lot to @DarthGizka

\$\endgroup\$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.