Linked List

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 5.0s
Java 8 10.0s
Java 9 10.0s
Memory limit: 10M
Java 8 12M
Java 9 12M

Author:
Problem types

1992 is a different time. It's before the time that the entire Windows division at Microsoft could only afford to get one computer with a staggering 96 MB of RAM to test Windows 95 on. The average computer back then had less than 4 MB of RAM. It's less than what modern Java requires to start up!

To secure your release back to the modern age, you came across me. I would gladly let you back to the future if only you do me one little favour. I need to implement a linked list that can store N elements, up to 1\,000\,000, each storing integers ranging from -8 \times 10^{12} to 8 \times 10^{12}. But wait, I am not very rich! I can only afford 10 MB of RAM (remember it's 1992) to run the program.

Your linked list must support these operations:

  • < select the previous element (rewinding).
  • > select the next element (advancing).
  • = changes the current element to a value (updating).
  • + creates a new element with value, shifting the current element back (inserting). The pointer will point at the inserted element.
  • - removes the current element, shifts pointer to the next element (deleting).
  • ! prints the value of the current element (printing).

Note that your linked list starts empty, and it is possible to delete the last element in the list. In both cases, the pointer goes beyond the end of the list. In no case will the past-the-end "element" be updated, deleted, or queried, nor will there be attempts to advance past the past-the-end "element", or rewind past the first element.

Input Specification

The first line contains the integer M, the number of operations to perform, up to 10\,000\,000.

The next M lines will contain one of the operation labels, <, >, =, +, -, or !. If the operation takes a value, in case of = or +, then the label is followed by a space followed by an integer.

Output Specification

For every ! operation, print the value at the linked list pointer.

Subtasks

There are four subtasks:

  1. N \le 1\,000, M \le 10\,000, 10\% of points
  2. N \le 10\,000, M \le 100\,000, 20\% of points
  3. N \le 100\,000, M \le 1\,000\,000, 30\% of points
  4. N \le 1\,000\,000, M \le 10\,000\,000, 40\% of points

Sample Input

10
+ 100
+ 200
>
!
<
!
-
!
= 300
!

Sample Output

100
200
100
300

Explanation

  1. Insert 100 to list: [100], pointer at 0.
  2. Insert 200 to list: [200, 100], pointer at 0.
  3. Advance pointer: pointer at 1.
  4. Print: prints 100 which is at index 1 of list [200, 100].
  5. Rewind pointer: pointer at 0.
  6. Print: prints 200 which is at index 0 of list [200, 100].
  7. Delete element: [100], pointer still at 0.
  8. Print: prints 100 which is at index 0 of list [100].
  9. Update to 300: [300], pointer at 0.
  10. Print: prints 300 which is at index 0 of list [300].

Warning

It might be unwise to use languages that use a lot of memory, and even more unwise to use languages that won't start in the memory limit. Your mileage may vary. Problem is guaranteed to be solvable in any language that allows direct memory access, such as C, or C++.


Comments


  • 0
    lolzballs  commented on April 5, 2015, 10:43 a.m.

    Any tips on how to reduce running time? My program uses linear search to find free blocks of memory, but it fails on the last 3 batch cases.


    • 0
      quantum  commented on April 5, 2015, 1:46 p.m.

      You said it, there's your problem. A linked list should not have linear time operations. Please refrain from posting too much details though, it might give away too much info.


  • 0
    lolzballs  commented on April 4, 2015, 8:35 p.m. edited

    What happens when the final element in the list gets deleted? Does the current pointer go to the new final element or does it stay at the same location?

    EDIT: It stays at the same location


  • 0
    jackyliao123  commented on March 24, 2015, 9:27 a.m.

    creating a long array size of 1000000 causes MLE


    • 0
      quantum  commented on March 26, 2015, 5:32 p.m.

      Increased time and memory limit for Java only so it can pass.


      • 0
        jackyliao123  commented on April 5, 2015, 10:52 a.m.

        There is no option to submit in Java.


        • 0
          quantum  commented on April 5, 2015, 1:23 p.m. edited

          Oh dear someone broke Java.

          Update: Fixed.


        • -2
          bobhob314  commented on April 5, 2015, 12:22 p.m. edit 2

          FatalEagle, on a post DIRECTLY below yours: "The problem statement specifically stated that Java won't work."

          Edit: Good point lolzballs.


          • 0
            lolzballs  commented on April 5, 2015, 12:29 p.m.

            I think that he is confused by what quantum said,

            "Increased time and memory limit for Java only so it can pass."


    • -2
      FatalEagle  commented on March 24, 2015, 9:35 a.m.

      The problem statement specifically stated that Java won't work.


  • 0
    kobortor  commented on March 18, 2015, 5:37 p.m. edit 2

    http://imgur.com/giU0ECo

    I can't submit in anything other than Java. It's only for this question.


    • 0
      quantum  commented on March 18, 2015, 5:42 p.m.

      Judge herculaneum was broken for some reason.


  • 0
    lolzballs  commented on March 18, 2015, 10:43 a.m.

    I'm slightly confused by "In no case will there ... be attempts to advance past the past-the-end "element", or rewind past the first element."

    Does this mean that once the current pointer is at the last element, there will be no attempts to use '>'? Or does it mean that it can, but after it gets there, it won't use '>' again


    • 0
      quantum  commented on March 18, 2015, 10:55 a.m.

      You can advance beyond the last element, but no > will be used when it is beyond the last element. This is necessary because the linked list starts empty, and points to the pseudo-element.


      • 0
        lolzballs  commented on March 24, 2015, 5:08 p.m.

        Can you < past the first element?

        Like if there is elements 1, 2 and the current pointer is on 1, can you < to the "element" before it and prepend something there?


        • 0
          kobortor  commented on March 24, 2015, 7:52 p.m.

          In no case will the past-the-end "element" be updated, deleted, or queried, nor will there be attempts to advance past the past-the-end "element", or rewind past the first element.

          So no.


  • 0
    kobortor  commented on Feb. 23, 2015, 2:40 p.m.

    What is N supposed to be?


    • 0
      quantum  commented on Feb. 23, 2015, 3:30 p.m.

      N is the number of elements to store.