chaicko / algorithmictoolbox Goto Github PK

Need to complete the basic data structures assignment.

Reorganize directory structure as follows:

• algorithmic_toolbox
  • introduction_problems
  • max_pairwise
  • greedy
  • divide_and_conquer
  • dynprog
• data_structures
  • basic
  • prio_queues_disjoint_sets
  • hash_tables
• algorithms_on_graphs
• algorithms_on_strings
• advanced_algorithms

Problem Introduction

In this problem you will simulate a program that processes a list of jobs in parallel.

Problem Description

Task

You have a program which is parallelized and uses n independent threads to process the given list of m jobs. Threads take jobs in the order they are given in the input. If there is a free thread, it immediately takes the next job from the list. If a thread has started processing a job, it doesn’t interrupt or stop until it finishes processing the job. If several threads try to take jobs from the list simultaneously, the thread with smaller index takes the job. For each job you know exactly how long will it take any thread to process this job, and this time is the same for all the threads. You need to determine for each job which thread will process it and when will it start processing.

Input Format

The first line of the input contains integers n and m.
The second line contains m integers t[i] — the times in seconds it takes any thread to process i-th job.
The times are given in the same order as they are in the list from which threads take jobs.
Threads are indexed starting from 0.

Constraints

1 ≤ n ≤ 10^5; 1 ≤ m ≤ 10^5; 0 ≤ t[i] ≤ 10^9.

Output Format

Output exactly m lines. i-th line (0-based index is used) should contain two space-separated integers — the 0-based index of the thread which will process the i-th job and the time in seconds when it will start processing that job.

Time Limits

C: 1 sec, C++: 1 sec, Java: 4 sec, Python: 6 sec. C#: 1.5 sec, Haskell: 2 sec, JavaScript: 6 sec, Ruby: 6 sec, Scala: 6 sec.

Memory Limit

512Mb.

Need to complete the Three following problems:

• Convert array into heap
• Parallel processing
• Merging tables

Problem Introduction

In this problem you will implement a hash table using the chaining scheme.

Problem Description

Task.

In this task your goal is to implement a hash table with lists chaining. You are already given the number of buckets m and the hash function. It is a polynomial hash function

h(s) = SUM{ S[i] * x^i mod p } mod m

where S[i] is the ASCII code of the i-th symbol of S, p = 1 000 000 007 and x = 263. Your program should support the following kinds of queries:

• add string insert string into the table. If there is already such string in the hash table, then just ignore the query.
• del string remove string from the table. If there is no such string in the hash table, then just ignore the query.
• find string output “yes” or “no” (without quotes) depending on whether the table contains string or not.
• check i output the content of the i-th list in the table. Use spaces to separate the elements of the list. If i-th list is empty, output a blank line.

When inserting a new string into a hash chain, you must insert it in the beginning of the chain.

Input Format

There is a single integer m in the first line — the number of buckets you should have. The next line contains the number of queries N . It’s followed by N lines, each of them contains one query in the format described above.

Constraints

1 ≤ N ≤ 10 5 ; N 5 ≤ m ≤ N . All the strings consist of latin letters. Each of them is non-empty and has length at most 15.

Output Format

Print the result of each of the find and check queries, one result per line, in the same order as these queries are given in the input.

Time Limits

C: 1 sec, C++: 1 sec, Java: 5 sec, Python: 7 sec. C#: 1.5 sec, Haskell: 2 sec, JavaScript: 7 sec, Ruby: 7 sec, Scala: 7 sec.

Memory Limit

512Mb.

Sample 1

Input:

5
12
add world
add HellO
check 4
find World
find world
del world
check 4
del HellO
add luck
add GooD
check 2
del good

Output:

HellO world
no
yes
HellO
GooD luck

Explanation:

The ASCII code of ’w’ is 119, for ’o’ it is 111, for ’r’ it is 114, for ’l’ it is 108, and for ’d’ it is 100. Thus, h(‘‘world") = (119 + 111 × 263 + 114 × 263^2 + 108 × 263^3 + 100 × 263^4 mod 1 000 000 007) mod 5 = 4.
It turns out that the hash value of HellO is also 4. Recall that we always insert in the beginning of the chain, so after adding “world” and then “HellO” in the same chain index 4, first goes “HellO” and then goes “world”. Of course, “World” is not found, and “world” is found, because the strings are case-sensitive, and the codes of ’W’ and ’w’ are different. After deleting “world”, only “HellO” is found in the chain 4. Similarly to “world” and “HellO”, after adding “luck” and “GooD” to the same chain 2, first goes “GooD” and then “luck”.

Sample 2

Input:

4
8
add test
add test
find test
del test
find test
find Test
add Test
find Test

Output:

yes
no
no
yes

Explanation:

Adding “test” twice is the same as adding “test” once, so first find returns “yes”. After del, “test” is no longer in the hash table. First time find doesn’t find “Test” because it was not added before, and strings are case-sensitive in this problem. Second time “Test” can be found, because it has just been added.

What to Do

Follow the explanations about the chaining scheme from the lectures. Remember to always insert new strings in the beginning of the chain. Remember to output a blank line when check operation is called on an empty chain.

Some hints based on the problems encountered by learners:

• Beware of integer overflow. Use long long type in C++ and long type in Java where appropriate. Take everything (mod p) as soon as possible while computing something (mod p), so that the numbers are always between 0 and p − 1.
• Beware of taking negative numbers (mod p). In many programming languages, (−2)%5 6 = 3%5. Thus you can compute the same hash values for two strings, but when you compare them, they appear to be different. To avoid this issue, you can use such construct in the code: x ← ((a%p) + p)%p instead of just x ← a%p.

Complete the divide_and_conquer assignments. Specifically:

• divide_and_conquer/inversions.py
• divide_and_conquer/points_and_segments.py

Find the maximum pairwise product, that is, the largest integer that can be obtained by multiplying two different elements from the sequence a (or, more formally, max(a[i] * a[j]) where i != j and i,j <= len(a)).

The sequence a has at least 2 elements and at most 2 * 10 ^ 5. Each element of the sequence is an integer number n where 0 <= n <= 10 ^ 5.

Problem Introduction

In this problem, your goal is to simulate a sequence of merge operations with tables in a database.

Problem Description

Task

There are n tables stored in some database. The tables are numbered from 1 to n. All tables share the same set of columns. Each table contains either several rows with real data or a symbolic link to another table. Initially, all tables contain data, and i-th table has r_i rows. You need to perform m of the following operations:

1. Consider table number destination_i . Traverse the path of symbolic links to get to the data. That
   is,
   while destination_i contains a symbolic link instead of real data do destination_i ← symlink(destination_i)
2. Consider the table number source_i and traverse the path of symbolic links from it in the same
   manner as for destination_i.
3. Now, destination_i and source_i are the numbers of two tables with real data. If destination_i != source_i , copy all the rows from table source_i to table destination_i , then clear the table source_i and instead of real data put a symbolic link to destination_i into it.
4. Print the maximum size among all n tables (recall that size is the number of rows in the table). If the table contains only a symbolic link, its size is considered to be 0.

See examples and explanations for further clarifications.

Input Format

The first line of the input contains two integers n and m — the number of tables in the database and the number of merge queries to perform, respectively.
The second line of the input contains n integers r_i — the number of rows in the i-th table.
Then follow m lines describing merge queries. Each of them contains two integers destination_i and source_i — the numbers of the tables to merge.

Constraints

1 ≤ n, m ≤ 100 000; 0 ≤ r_i ≤ 10 000; 1 ≤ destination_i , source_i ≤ n.

Output Format

For each query print a line containing a single integer — the maximum of the sizes of all
tables (in terms of the number of rows) after the corresponding operation.

Time Limits

C: 2 sec, C++: 2 sec, Java: 14 sec, Python: 6 sec. C#: 3 sec, Haskell: 4 sec, JavaScript: 6 sec, Ruby: 6 sec, Scala: 14 sec.

Memory Limit

512Mb.

Problem Introduction

In this problem, your goal is to implement the Rabin–Karp’s algorithm.

Problem Description

Task

In this problem your goal is to implement the Rabin–Karp’s algorithm for searching the given pattern in the given text.

Input Format

There are two strings in the input: the pattern P and the text T.

Constraints

1 ≤ |P| ≤ |T| ≤ 5 * 10^5 . The total length of all occurrences of P in T doesn’t exceed 10^8 . The
pattern and the text contain only latin letters.

Output Format

Print all the positions of the occurrences of P in T in the ascending order. Use 0-based indexing of positions in the the text T.

Time Limits

C: 1 sec, C++: 1 sec, Java: 5 sec, Python: 5 sec. C#: 1.5 sec, Haskell: 2 sec, JavaScript: 3 sec, Ruby: 3 sec, Scala: 3 sec.

Memory Limit

512Mb.

Sample 1

Input:

aba
abacaba

Output:

04

Explanation:

The pattern aba can be found in positions 0 (abacaba) and 4 (abacaba) of the text abacaba.

Sample 2

Input:

Test
testTesttesT

Output:

4

Explanation:

Pattern and text are case-sensitive in this problem. Pattern T est can only be found in position 4 in the text testT esttesT .

Sample 3

Input:

aaaaa
baaaaaaa

Output:

123

Explanation:

Note that the occurrences of the pattern in the text can be overlapping, and that’s ok, you still need to output all of them.

What to Do

Implement the fast version of the Rabin–Karp’s algorithm from the lectures.
Some hints based on the problems encountered by learners:

• Beware of integer overflow. Use long long type in C++ and long type in Java where appropriate. Take everything (mod p) as soon as possible while computing something (mod p), so that the numbers are always between 0 and p − 1.
• Beware of taking negative numbers (mod p). In many programming languages, (−2)%5 6 = 3%5. Thus you can compute the same hash values for two strings, but when you compare them, they appear to be different. To avoid this issue, you can use such construct in the code: x ← ((a%p) + p)%p instead of just x ← a%p.
• Use operator == in Python instead of implementing your own function AreEqual for strings, because built-in operator == will work much faster.
• In C++, method substr of string creates a new string, uses additional memory and time for that, so use it carefully and avoid creating lots of new strings. When you need to compare pattern with a substring of text, do it without calling substr.
• In Java, however, method substring does NOT create a new String. Avoid using new String where
  it is not needed, just use substring.

Problem Introduction

In this problem you will implement a simple phone book manager.

Problem Description

Task

In this task your goal is to implement a simple phone book manager. It should be able to process
the following types of user’s queries:

• add number name. It means that the user adds a person with name name and phone number number to the phone book. If there exists a user with such number already, then your manager has to overwrite the corresponding name.
• del number. It means that the manager should erase a person with number number from the phone book. If there is no such person, then it should just ignore the query.
• find number. It means that the user looks for a person with phone number number. The manager should reply with the appropriate name, or with string “not found” (without quotes) if there is no such person in the book.

Input Format

There is a single integer N in the first line — the number of queries. It’s followed by N lines, each of them contains one query in the format described above.

Constraints

1 ≤ N ≤ 10 5 . All phone numbers consist of decimal digits, they don’t have leading zeros, and each of them has no more than 7 digits. All names are non-empty strings of latin letters, and each of them has length at most 15. It’s guaranteed that there is no person with name “not found”.

Output Format

Print the result of each find query — the name corresponding to the phone number or “not found” (without quotes) if there is no person in the phone book with such phone number. Output one result per line in the same order as the find queries are given in the input.

Time Limits

C: 3 sec, C++: 3 sec, Java: 6 sec, Python: 6 sec. C#: 4.5 sec, Haskell: 6 sec, JavaScript: 9 sec, Ruby: 9 sec, Scala: 9 sec.

Memory Limit

512Mb.

Sample 1

Input:

12
add 911 police
add 76213 Mom
add 17239 Bob
find 76213
find 910
find 911
del 910
del 911
find 911
find 76213
add 76213 daddy
find 76213

Output:

3Mom
not found
police
not found
Mom
daddy

Explanation:

76213 is Mom’s number, 910 is not a number in the phone book, 911 is the number of police, but then it was deleted from the phone book, so the second search for 911 returned “not found”. Also, note that when the daddy was added with the same phone number 76213 as Mom’s phone number, the contact’s name was rewritten, and now search for 76213 returns “daddy” instead of “Mom”.

Sample 2.

Input:

8
find 3839442
add 123456 me
add 0 granny
find 0
find 123456
del 0
del 0
find 0

Output:

not found
granny
me
not found

Explanation:

Recall that deleting a number that doesn’t exist in the phone book doesn’t change anything.

What to Do

Use the direct addressing scheme.

Complete the dynprog assignments. Specifically:

• dynprog/primitive_calculator.py
• dynprog/lcs3.py

Problem Introduction

In this problem you will convert an array of integers into a heap.

Problem Description

Task.

The first step of the HeapSort algorithm is to create a heap from the array you want to sort. By the way, did you know that algorithms based on Heaps are widely used for external sort, when you need
to sort huge files that don't fit into memory of a computer?

Your task is to implement this first step and convert a given array of integers into a heap. You will
do that by applying a certain number of swaps to the array. Swap is an operation which exchanges
elements a[i] and a[j] of the array a for some i and j. You will need to convert the array into a heap using only O(n) swaps, as was described in the lectures. Note that you will need to use a min-heap instead of a max-heap in this problem.

Input Format

The first line of the input contains single integer n. The next line contains n space-separated
integers a[i].

Constraints

1 ≤ n ≤ 100 000; 0 ≤ i, j ≤ n − 1; 0 ≤ a[0], a[1] , ... , a[n−1] ≤ 10^9 . All a[i] are distinct.

Output Format

The first line of the output should contain single integer m — the total number of swaps.
m must satisfy conditions 0 ≤ m ≤ 4n. The next m lines should contain the swap operations used to convert the array a into a heap. Each swap is described by a pair of integers i, j — the 0-based indices of the elements to be swapped. After applying all the swaps in the specified order the array must become a heap, that is, for each i where 0 ≤ i ≤ n − 1 the following conditions must be true:

1. If 2_i_ + 1 ≤ n − 1, then a[i] < a[2i+1].
2. If 2_i_ + 2 ≤ n − 1, then a[i] < a[2i+2].

Note that all the elements of the input array are distinct. Note that any sequence of swaps that has length at most 4_n_ and after which your initial array becomes a correct heap will be graded as correct.

Time Limits

C: 1 sec, C++: 1 sec, Java: 3 sec, Python: 3 sec. C#: 1.5 sec, Haskell: 2 sec, JavaScript: 3 sec, Ruby: 3 sec, Scala: 3 sec.

Memory Limit

512Mb