2
\$\begingroup\$

I'm doing this problem:

After getting her PhD, Christie has become a celebrity at her university, and her Facebook profile is full of friend requests. Being the nice girl she is, Christie has accepted all the requests.

Now Kuldeep is jealous of all the attention she is getting from other guys, so he asks her to delete some of the guys from her friend list.

To avoid a 'scene', Christie decides to remove some friends from her friend list, since she knows the popularity of each of the friend she has, she uses the following algorithm to delete a friend.

Algorithm Delete(Friend):
    DeleteFriend=false
    for i = 1 to Friend.length-1
         if (Friend[i].popularity < Friend[i+1].popularity)
            delete i th friend
            DeleteFriend=true
            break
    if(DeleteFriend == false)
        delete the last friend

Input: First line contains T number of test cases. First line of each test case contains N, the number of friends Christie currently has and K ,the number of friends Christie decides to delete. Next lines contains popularity of her friends separated by space.

Output: For each test case print N-K numbers which represent popularity of Christie friend's after deleting K friends.

Constraints:

1 <= T <= 1000
1 <= N <= 100000
0 <= K < N
0 <= popularity_of_friend <= 100

NOTE: Order of friends after deleting exactly K friends should be maintained as given in input.

Sample Input

3
3 1
3 100 1
5 2
19 12 3 4 17
5 3
23 45 11 77 18

Sample Output

100 1
19 12 17
77 18

Time Limit 1 sec(s) (Time limit is for each input file.)

Memory Limit 256 MB

Source Limit 1024 KB

Initially I would read and add the numbers to the list, then follow that algorithm. I figured doing what that algorithm does except as I add it in would be much faster (which it was):

import java.util.*;

class TestClass {
    public static void main(String args[] ) throws Exception {
        Scanner scanner = null;
        try{
            scanner = new Scanner(System.in);
        }catch(Exception e){
            return;
        }
        int T = Integer.parseInt(scanner.next());

        //remove as i add to list
        for(int i = 0; i < T; i++){
            int friendsStart = Integer.parseInt(scanner.next());
            int friendsDelete = Integer.parseInt(scanner.next());
            ArrayList<Integer> inputList = new ArrayList<Integer>();
            int currentPos = 0;
            for(int j = 0; j < friendsStart ; j++){
                p.add(Integer.parseInt(scanner.next()));
                if(fD > 0 && currentPos > 0 && inputList.get(currentPos) > inputList.get(currentPos-1)){
                    inputList.remove(currentPos-1);
                    friendsDelete--;
                    currentPos--;
                }else{
                    currentPos++;
                }
            }

            //remove remainder required to remove
            while(friendsDelete > 0 && c < inputList.size()){
                if(currentPos > 0 && inputList.get(currentPos) > inputList.get(currentPos -1)){
                    inputList.remove(currentPos-1);
                    friendsDelete--;
                    currentPos--;
                }else{
                    currentPos++;
                }
            }

            //print
            for(int j = 0; j < inputList.size(); j++){
                System.out.print(inputList.get(j) + " ");
            }
            System.out.println();
        }
    }
}

However, when I submit, it does some bigger test cases (not sure what the cases are), but it ends up being too slow. I wanted some hints as to how I can make this faster than it already is. I don't want a direct answer.

\$\endgroup\$
  • 2
    \$\begingroup\$ Some of the variable names are not verbose enough IMO \$\endgroup\$ – Ryan Aug 8 '14 at 16:05
  • \$\begingroup\$ @Ryan Yah, I just kind of hacked it up for the site. Let me change it up so its a bit more readable. \$\endgroup\$ – But I'm Not A Wrapper Class Aug 8 '14 at 16:06
  • \$\begingroup\$ I cannot believe that your algorithm is too slow. I think that its speed is bounded by I/O... \$\endgroup\$ – Emanuele Paolini Aug 8 '14 at 17:26
  • 2
    \$\begingroup\$ Preallocate your list using new ArrayList<Integer>(friendsStart) to avoid copying memory every time it has to double the capacity to make room for more elements. Also, is p the old name for inputList? \$\endgroup\$ – David Harkness Aug 8 '14 at 18:58
  • 1
    \$\begingroup\$ Please don't edit the original code as it invalidates existing answers. \$\endgroup\$ – David Harkness Aug 8 '14 at 19:38
1
\$\begingroup\$

Hint: The problem statement asks you to remove friends from the end of the list as necessary. Think carefully about this.

You don't actually have to remove the remaining friends to delete. Instead, just don't print them. Change your while and for to the following code.

Spoiler tags and code blocks don't interact nicely, so the solution code is base 64 encoded.

Zm9yIChpbnQgaiA9IDAsIGptYXggPSBpbnB1dExpc3Quc2l6ZSgpIC0gZnJpZW5kc0RlbGV0ZTsgaiA8IGptYXg7IGorKykgew0KICAgICBTeXN0ZW0ub3V0LnByaW50KGlucHV0TGlzdC5nZXQoaikgKyAiICIpOw0KfQ==

I believe @EmanuelePaolini is correct in that you're likely getting TLE because of I/O. You're using Scanner, which is way too slow. Try a different input method.

You can try switching to BufferedReader. String.split() is still slow, so you can combine it with StringTokenizer. Here's a sample on ideone.

Encoded:

c3RhdGljIEJ1ZmZlcmVkUmVhZGVyIGJyID0gbmV3IEJ1ZmZlcmVkUmVhZGVyKG5ldyBJbnB1dFN0cmVhbVJlYWRlcihTeXN0ZW0uaW4pKTsNCnN0YXRpYyBTdHJpbmdUb2tlbml6ZXIgc3QgPSBuZXcgU3RyaW5nVG9rZW5pemVyKCIiKTsNCnN0YXRpYyBpbnQgbmV4dEludCgpIHRocm93cyBJT0V4Y2VwdGlvbiB7DQoJd2hpbGUgKCFzdC5oYXNNb3JlVG9rZW5zKCkpDQoJCXN0ID0gbmV3IFN0cmluZ1Rva2VuaXplcihici5yZWFkTGluZSgpKTsNCglyZXR1cm4gSW50ZWdlci5wYXJzZUludChzdC5uZXh0VG9rZW4oKSk7DQp9
\$\endgroup\$
  • \$\begingroup\$ The BufferedReader and StringTokenizer made it way faster. However, it only helped pass one more test case. Still is too slow for other test cases. \$\endgroup\$ – But I'm Not A Wrapper Class Aug 8 '14 at 19:09
1
\$\begingroup\$

You've missed several variable renamings which keeps your code from compiling, and those names were truly atrocious! p, c, fD? Create more descriptive names as an opportunity to practice your touch-typing skills. :) It doesn't help that the names in the original problem description weren't much better:

  • Friend (singular): Holds a list of friends (plural)
  • DeleteFriend (verb phrase): Indicates that a friend was deleted during the iteration (adjective)

Anyway, your new names are better, but here are some alternatives:

  • friends: List of friends
  • friendCount: Number of friends in original list
  • deleteCount: Number of friends left to delete

As for the algorithm, you're on the right track by deleting friends as you read them, but you can take it a step further by deleting more than one when possible. For example, when you delete the previous friend, it may allow you to delete the next previous friend as well. The benefit of this is that you're always deleting from the end of the list which minimizes the amount of memory being copied for each friend deleted.

And as I stated in my comment, preallocate the full length of the list to avoid more memory copies. The array starts with ten elements by default (last time I checked), and doubles in size every time it runs out of space. That requires ten copies to handle ten thousand friends. It's not a large number, but the amount of memory being copied adds up quick.

ArrayList<Integer> friends = new ArrayList<Integer>(friendCount);

Of course, if you alter the algorithm to always delete from the end, you can skip ArrayList altogether and use a simple array of ints and avoid the overhead of Integer objects. So how can we do that?

As long as there are friends left to delete, remove as many friends as possible from the end of the list while reading. The list should always be in the "no friends can be deleted" state: every friend is at least as popular as the next friend.

The empty list obviously starts in that state, and adding the first friend maintains it. From them on when adding the next friend, keep deleting the previous friend until we find one that is at least as popular.

while deleteCount > 0:
    current = readNext()
    while previous < current && deleteCount > 0:
        delete previous
        --deleteCount
    add current

Once you've deleted the desired number of friends, print the processed list of friends and the remaining friends in the line (no need to parse and add them to the list first). If you run out of friends to read before then, remove the last deleteCount friends in the list.

Finally, you may need to employ some micro-optimizations as the others have pointed out: using buffered input, using a different tokenizer, or even scanning the input yourself given that it has such tight constraints.

\$\endgroup\$
  • \$\begingroup\$ The naming convention (and changes following) were addressed in the comments section. \$\endgroup\$ – But I'm Not A Wrapper Class Aug 8 '14 at 19:39
0
\$\begingroup\$

Your algorithm should be quick enough. To get some more efficiency you could avoid using the list to store the values. I think you just need to keep track of last value not yet discarded which you can print at once. To know how many friends should be deleted by the end of the list you can just stop the program as long as you have printed the correct number of values.

\$\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.