USACO 1.2 Milking Cows (C++) Solution

Hints

We know that this problem will need a complete search approach. Steven and Felix Halim in their book Competitive Programming give a few tips for complete search:

• generating v.s. filtering
• prune infeasible search space early
• utilize symmetries
• pre-computation/pre-calculation
• solve the problem backwards
• optimizing source code

, so an approach with two nested loops won’t work. A lot of complete search problems are much easier if we sort them first.

Solution

When does something interesting happen? Imagine drawing all the time intervals on a sheet of paper. The only time anything interesting happens is when there’s a jump between intervals, because that’s when there’s idle time and also when there’s a break in continuity of milking cows. All we need to check is if the next interval is a “real” jump, keeping track of the “current greatest right value” and the left point of the current interval.

Code is at: https://github.com/ilogin/Competitive-Programming/blob/master/USACO/milk2.cpp

UVA 957 Solution (C++)

The hint given in Competitive Programming by Steven and Felix Halim for this problem says: Complete Search + Binary Search: upper_bound.

I was really, really confused when I read that. Aren’t those two separate problem solving paradigms? How could you do both? I was stuck on this simple problem for a long time, for about two weeks.

My first approach was to divide the last year by two and check to see which side had more “years”. That immediately doesn’t work with the given sample input, though:

5
20
1
2
3
6
8
12
13
13
15
16
17
18
19
20
20
21
25
26
30
31

Because 31/2 ~ 16. 16-1 = 15, 31 – 16 = 15.

I went running today and had a realization that the input size, was big enough that I could check every year, see how many popes there are in the year + Y, and store them into an array. Then every time there was a new “max” I could update the beginning and end of the Pope years.

At this point, I could see what the hint meant when it said complete search. But binary search?

I figured that the only room for improvement was checking how many popes there are in a given year + Y period, so you could use the upper_bound binary search to look for the year of election of a specific pope, namely the year of the (given year + Y)th pope’s election.

Here’s my solution, also on Github:

#include <bits/stdc++.h>
#define ll long long
#define forit(it, a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define pb push_back
#define mp make_pair
using namespace std;

int main(){

 int y, p; 

 while(scanf("%d %d", &y, &p) != EOF){
 vector<int>popes;
 for (int i = 0; i < p; i++){
 int a; cin >> a; popes.pb(a);
 } 

 int ans = 0;
 int begin = 0; int end = 0;
 forit(it1, popes){
 vector<int>::iterator it2 = upper_bound(popes.begin(), popes.end(), *it1 + y - 1);
 if (it2 - it1 > ans){
 ans = it2 - it1;
 begin = *it1;
 end = *(it2-1);
 }
 }

 printf("%d %d %d\n", ans, begin, end);

 }
 return 0;
}

What is Concurrency?

Using a broom, you have to sweep three floors: the living room, the bedroom, and the kitchen. You don’t want to spend a lot of time cleaning, so you get two friends to help. By delegating the task of sweeping three floors, the process is much faster. The interesting bit is that the order you sweep the floors don’t matter, because in the end all three floors will be swept.

Just like how you called some friends to help, concurrency is breaking down something into smaller, order-independent bits. Concurrency is very desirable in operating systems because it can make processes happen much more quickly.

UVA 10360 Solution (C++)

A few optimizations on complete search include generating v.s. filtering, pruning infeasible search space early, utilizing symmetries, pre-computation/pre-calculation, and trying to solve the problem backwards. This problem is really easy if you solve it backwards.
Abridged problem statement: Imagine a 2-D array (up to 1024 x 1024) containing rats. There are n <= 20000 rats at some cells, determine which cell (x, y) should be gas-bombed so that the number of rats killed in square box (x-d, y-d) to (x+d, y+d) is maximized. The value d is the power of the gas-bomb (d is up to 50).

Create an array (int killed[1024][1024]). For each n rat population at coordinate (x,y) add the value of array killed[i][j] with the number of rats in (x, y) that will be killed if a bomb is placed in (i, j) and (i, j) is within the square-bombing radius.

Be careful of segmentation faults. Make sure that the index you're accessing in any array is in the allocated boundary (it's possible for the square-bombing radius to be negative if you're not careful).

#include 
#define ll long long
#define forit(it, a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define pb push_back
#define mp make_pair
using namespace std;

int main(){

	int t; cin >> t; while(t--){
		int d; cin >> d; int n; cin >> n;
		int killed[1025][1025] = {0};
		for (int i = 0; i > a >> b >> c;
			for (int j = a-d; j = 0 && j <= 1024 && k <= 1024) killed[j][k] += c;
		}

		int left, right, ans(0);

		for (int i = 0; i <= 1024; i++)
			for (int j = 0; j  ans){
					left = i;
					right = j;
					ans = killed[i][j];
				}

		printf("%d %d %d\n", left, right, ans);
	}

	return 0;
}

#define, #include

OS Interview (Multi-Cores), V3

Which of the following applies to a multi-core system?

a. multiple users can use the system at the same time

b. the kernel can run in SMP mode

c. multiple tasks can execute in parallel without the need for scheduling

d. semaphores and mutexes should be replaced with spinlock

A multi-core system has more than one core, a unit that can read and execute program instructions.

An answer I saw said:

Answer (A): Correct. In a multiprocessor system, you can do more than one task at the same time. In a single processor, it’s not possible and what you have is a emulation due to schedule features.

That’s not correct. A multi-core system can multiprocess, using two or more CPUs to allocate tasks between them. This doesn’t imply that multiple users can use the system at the same time. It does imply that there is the possibility that multiple processes can execute at the same time because there is more than one CPU to execute program instructions.

Apparently SMP is an acronym for symmetric multiprocessing. I always thought it stood for shared memory processing. SMP architecture has two or more identical processors that connect to a single, shared, main memory and is controlled by a single operating system instance that treats all processors equally. So, yes, the kernel can run in SMP mode in a multi-core system. In the case of multi-core processors, the SMP architecture applies to cores, treating them as separate processors.

Tasks always need to be scheduled to process.

A semaphore is a variable or abstract data type that is used for controlling access to a common resource in a concurrent system. A mutex is a program object that allows multiple program threads to share the same resource, but not simultaneously. As mentioned in a previous answer, the decision on what “lock” to use really depends. Spinlock is a great and simple if the wait for the lock is expected to be short. The use of a mutex, semaphore, or a spinlock isn’t dependent on whether or not the system in question has multiple cores. So, answer A, C, and D are incorrect, and B is correct.

(Really) Easy Google Interview Questions

Check if an array is unique.

checkarray(int array[], int N){
  //assuming array is of length N
  sort(array, array+N);

  bool ans = true;
  for (int i = 0; i < N; i++)
    if (array[i] == array [i+1]) ans = false;

  if (ans) cout << "Yes, the given array is unique."
  else cout << "No, the given array is not unique."
}

You are given a matrix with N rows and N columns. Elements in the matrix can be either 1 or 0. Each row and column of matrix is sorted in ascending order. Find the number of 0-s in the given matrix.

Example:

0 0 1

0 1 1

1 1 1   Answer: 3

0 0

0 0 Answer: 4

int matrix[n][n];

int check(){
  int ans(0);  

   for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++)
        if (matrix[i][j] == 0) ans++;

  cout << ans;
}

 

OS Interview (Spinlock), V2

Implement a trivial spinlock and a spinunlock function using C-psuedo code:

void spinlock (int *lock){}
void spinunlock (int *lock){}

A spinlock is a lock which causes a thread, a small sequence of programmed instructions, trying to acquire it to simply wait in a loop, or spin, while repeatedly checking if the lock is available.

A possible answer to the question is simply:

void spinlock (int *lock){
    while (lock == 1) 
}

void spinunlock (int *lock){
    lock = 0;
}

There are obvious improvements that can be made to the code above. In scenarios where the wait for the lock is expected to be short, spinlock offers better performance than other forms of locking. The given problems with spinlock is that there is too much contention (multiple threads are fighting for use of the data structure), it does not exploit caches, and it disrupts useful work.

Understanding Recursion

Recursion is a function that calls itself. To avoid a never-ending loop, a recursive function has to check for a condition to determine if it should call itself again or not.

That’s why this code stumped me:

#include <cstdio>
#include <vector>
using namespace std;

int track[21];
int N, T; // T is number of tracks
vector<int> Container; // 遞迴時暫存track
vector<int> Ans;
int Maxsum;
void combination(int pos, int sum);

int main()
{
 while (scanf("%d %d", &N, &T) != EOF) {
 for (int i = 0; i < T; ++i)
 scanf("%d", &track[i]);
 Container.clear();

 Maxsum = 0;
 combination(0, 0);

 int sum = 0;
 for (int n : Ans) {
 printf("%d ", n);
 sum += n;
 }
 printf("sum:%d\n", sum);
 }
}
void combination(int pos, int sum)
{
 if (sum > Maxsum) { // 不斷刷新Maxsum,使得Maxsum更接近N
 Ans = Container;
 Maxsum = sum;
 }

 for (int i = pos; i < T; ++i) {
 if (track[i] + sum <= N) {
 sum += track[i];
 Container.push_back(track[i]);

 combination(i + 1, sum);

 sum -= track[i];
 Container.pop_back();
 }
 }
}

When does this function ever stop? It doesn’t seem like there is a condition that the recursive function would check to determine if it would stop calling itself.

An answer from stackexchange brought some insight as to why the code above doesn’t need “return”:

“…if there is no code, nothing is done.

All your functions are of type void; this means they should return nothing. Basically, you should only use return to stop the function.”

The code above doesn’t need a return because it continues until the function doesn’t satisfy the given conditions. Once the function goes down “the wrong path”, it automatically backtracks and starts from another position.

OS Interview (Virtual Memory), V1

Virtual memory can be handled by which of the following?

a. demand paging

b. demand segmentation

c. both a and b

Virtual memory is memory stored on the disk when there is not enough memory available in the RAM. Demand paging is a type of swapping in which pages of data are not copied from disk to RAM until they are needed. Demand segmentation allows for pages that are often referenced with each other to be brought into memory together, decreasing the number of page faults.

So, the answer is c – both demand paging and demand segmentation can handle virtual memory.

UVA 10662 Solution (C++)

Abridged problem statement: Given k integers in ascending order specifying the set S, print out all subsets of S with six numbers in lexicographical order.

For example, if given the input:

7 1 2 3 4 5 6 7

the output would be:

1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 6 7
1 2 3 5 6 7
1 2 4 5 6 7
1 3 4 5 6 7
2 3 4 5 6 7

Because 6 < k < 13, the input size we’re dealing with is very small. A complete search will work fine.

In each subset, the integers have to be in ascending order and they have to be different elements of the set S. Use six nested loops with the variable in each loop larger than the previous variable by one to print out the elements of each subset.

Here’s my code:

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for (int i = a; i < n; i++)

int main(){

 int n; cin >> n;
 while (true){
 int arr[n];
 for (int i = 0; i < n; i++) cin >> arr[i];

 rep (i, 0, n)
 rep (j, i+1, n)
 rep (k, j+1, n)
 rep (l, k+1, n)
 rep (m, l+1, n)
 rep (na, m+1, n)
 printf("%d %d %d %d %d %d\n", arr[i], arr[j], arr[k], arr[l], arr[m], arr[na]);
 
 cin >> n;
 if (n == 0) break;
 cout << endl;
 }
 
 return 0;
}

I have been practicing coding, but I’ve been lazy. There are about 60 problems I have solved that need documentation. I’ll start posting problem solutions more frequently.

I’m noticing that I’m forgetting a lot of the material in the classes I’ve taken (something I tried to avoid by updating the notes…), so I’ll make a habit to post solutions to interview questions on topics my classes covered.

I’m getting started on freelance programming. I noticed a lot of the projects available are in Javascript and PHP, so expect a lot of posts about Github projects in those languages and posts about updating resumes and portfolios in general.