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\$
5
  • 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\$ Commented Mar 30, 2016 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\$ Commented Mar 30, 2016 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\$ Commented Mar 30, 2016 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\$ Commented Mar 30, 2016 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\$ Commented Mar 30, 2016 at 10:26

2 Answers 2

Reset to default
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\$
8
  • 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\$ Commented Mar 30, 2016 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\$ Commented Mar 30, 2016 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\$ Commented Mar 30, 2016 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\$ Commented Mar 30, 2016 at 13:22
  • 1
    \$\begingroup\$ Yeah , it's working, i'll just post the code in python i wrote, thanks :) \$\endgroup\$ Commented Mar 30, 2016 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\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.