Topcoder SRM 553 Div-II-500 tutorial

The problem

Problem statement (requires login)

Summary of the statement is:

Given an array of non-negative integers program[], an integer wantedResult, and pseudocode of a peculiar program. This program takes program[] as argument, and reads it through. There’s also a stack initially filled with infinite number of 0’s. If program[i] = 0 it pops topmost two elements from the stack, adds them up, and pushes the sum into the stack, otherwise it pushes program[i] into stack. At the end of execution, it pops and prints the top element of the stack.

The trouble is exactly one of program[]‘s elements is -1. But the program operates only on non-negative integers. Return the smallest non-negative integer with which -1 can be replaced such that the program’s output is wantedResult. If no such non-negative integer exists, return -1 instead.

Topcoder SRM 551 Div-II-500 tutorial

I didn’t participate in the SRM, but solved this problem later. What follows is strictly a personal account of my attempt to this. I tried to be elaborate to make this accessible to newcomers. Hoping people facing difficulty in solving this problem may find this post helpful. My blog revives with this post!

The problem

Problem statement (requires login)

Excluding the unnecessary details, the problem statement reduces to:

Given a string chocolates[] and an integer maxSwaps, and you are allowed to swap any two adjacent elements of the string. Return length of the longest substring of identical characters achievable by no more than maxSwaps swaps.

First thoughts

Observing the sample cases, I devised a trivial one: AAABCAA. In this case BC is sandwiched between two segments of A’s. With 4 swaps, we can move BC to the right, and get the string AAAAABC. Also, 4 is the optimal number of swaps required to get a longer substring of identical characters from the given string.

Up to this point observation confirmed that, joining segments of identical characters is the only way to produce longer segments. But, how to join them with minimum possible swaps? For trivial cases like AAABCAA, solution is quite obvious—moving all sandwiched characters to either left or right whose length is shorter, a greedy approach. But, what about cases with more than two segments of identical characters, like AAABCABBACAA? What kind of complication do they introduce? Still no idea. Once I am with an idea how to do this, the rest is simple—for all possible substrings of chocolates[] flanked by segments of identical characters, find the minimum number of swaps (swap) needed to take all characters not identical to flanks’ out, if swap  minSwaps take the maximum of the lengths among all such substrings  of identical characters obtained.

CSE 141: Modular Arithmatic and Congruences

Definition:

1. If then .

Where and are integers and is a positive integer.

2. If

and

then .

Where and are integers and is a positive integer.

3. If

then, .

Where , and are integers and is a positive integer.

Example:

So

Algebra of Congruence:

If

and

then

also .

The Princeton Companion to Mathematics

Princeton University Press has recently published a book called The Princeton Companion to Mathematics. The chief editor of the book is Professor Timothy Gowers, who is a Fields Medal winner. It is a reference for every mathematician or anyone interested in Mathematics. Although world leaders in Mathematics have contributed to the book but, it will attract a wide range of audience.

Princeton Companion to Mathematics

It discusses almost all of the branches of present day mathematics, fundamental concepts of mathematics, biographical essays on famous mathematicians,influence of mathematics on other branches of knowledge etc. I believe it will provide a good introduction the subject to anyone.

I have tried some sample chapters from the book. Among them I found the Advice to a Young Mathematician very useful and stimulating. This chapter is contributed by world leading mathematicians like Michael Atiyah (Fields Medalist) and others.

Anyone interested may try some free chapters here.

WordPress posts on Princeton Companion may found here.

Solution to STEP problem-I

I have solved a STEP problem from Stephen Siklos’ book Advanced Problems in Core Mathematics. The problem and the solution follows:

Problem: Use the substitution to evaluate

Hence or otherwise show that for

Where and

Galilean and Lorentz transformation

Suppose two inertial reference frames S and S’ are moving with velocity v with respect to each other. Also suppose that an observer at reference frame S measures an event as and another observer at frame S’ measures the same event as . Now if we want to relate the measurements of S frame with S’ frame we have to use transformation equations.

If we take Newtonian mechanics granted then we use the Galilean transformation. Galilean or Classical transformation equations are:

Notice that the time co-ordinates are measured the same by both observer—that is .

But if we take Special Relativity instead of Newtonian Mechanics than we use Lorentz transformation. Lorentz transformation equations are:

The fraction is also called relativistic gamma .

Hello world!

Welcome to WordPress.com. This is your first post. Edit or delete it and start blogging!