We discuss another code jam problem today

This one is about N-quails running away from a person where initially the person stands at the origin and the quails are on a straight line at some offset Pi from the origin. They are running  away from the person either to the left or to the right of the origin and continue to run in that direction with their respective constant speed Si. The speed of the man is Y another constant and he can change his direction at any time to collect all the quails.  How much time does it take at the minimum to collect all the quails.
For the quails moving in the same direction, he will have to catch up at the max of pi + Si × t. This will be the quail whose abs (pi ×si) weighting factor is greatest.  For the quails running in the other direction, he can finish running in one direction first and then switch to catching up on another side.  This will save him the trouble of covering already negotiated distances repeatedly. Consequently he must first pick the direction with the shorter weighting factor is greatest.
Assume si is all positive it's direction given by pi which is minus for left and plus for right
Int getMinTime (list <int> Pi, list <int> Si, int K)
{
Int min = 0; int leftmost=-1;
Int max = 0; int rightmost=Pi.count+1;
For ( int I = 0; I < Pi.Count; i++)
{
 If (Pi × Si < min) {min = Pi × Si;
 leftmost = i}
 If (Pi × Si > max) {max = Pi x Si;
rightmost=i;}
}
If (rightmost < pi.count +1 && K - S [rightmost] == 0) return -1;
If ( leftmost > -1 && K - S [leftmost] == 0) return -1;
Int t-right = 0;
Int t-left = 0;
If (rightmost < Pi.Count +1) t-right= P[rightmost]/ K - S [rightmost];
If (leftmost > -1) t-left = P [leftmost] / K  - S [leftmost];
Int total = 0;
If (abs(min) > abs (max))
{
// first right then left
total = t-left + 2 × t-right;
}
else
{
// first left then right
total = t-right + 2 x t-left;
}
return total;
}

Today we continue to discuss the paper on Jigsaw
Efficient, low effort mashup isolation by James Mickens and Matthew Finifter. Mashups are web applications that contain code from different principals.
Jigsaw lets mashups be isolated with its framework  and lets them selectively expose private state. We saw how iFrames differ from boxes and why boxes are helpful with the Jigsaw design goals.
First boxes have no way to communicate with each other even if they belong to the same origin. Only functions marked public on principal objects can make cross domain calls. Boxes define the set  of domains they interact with by exposing their principal objects
Second boxes can use hierarchical relationships to manage resources. The topmost box has full access as possible. The descendants are further narrowed in scope. The delegations are possible from parent to child but with increasing strictness.  The integrator can set acts that restrict access of a child to its local storage but cannot allow access to its own storage.
Third boxes allow synchronous calls with objects being passed by reference. This is a significant improvement over asynchronous calls with significant marshalling.

Today we continue reading Jigsaw : Efficient, low effort mashup isolation by James Mickens and Matthew Finifter. Mashups are web applications that contain code from different principals.
Jigsaw lets mashups be isolated with its framework  and lets them selectively expose private state. We saw some of the features and design goals of Jigsaw. We got familiar with some of the terms such as domain, principal and integrator. We also reviewed box which is an isolation container much like an iFrame for each principal  however there are three differences between a box and an iFrame . Two iFrames can directly access each other's Javascript's namespaces using frame references. But box explicitly prohibits this.  The only way to allow cross principal access is with access modifiers on the principal object. IFrames share same origin.
But boxes enable fault isolation and privilege separation from different principals that originate from the same domain
Another difference is that boxes use nesting relationships to secure the resoutces of the children. With this hierarchy, common object oriented practice of encapsulation and inheritance can be used to better facilitate the management of resources. The third difference between box and iFrame is their use of communication channels.  IFrames uses asynchronous  postmessage calls . These calls can only transmit immutables and not pass objects by reference. Boxes facilitate synchronous calls and don't require marshaling of objects with the use of proxy.
#coding exercise
Find least common multiple of two integers
Int lcm (int x, int y)
{
Return (x*y)/gcd (x,y);
}

#codejam problem

A R x C matrix of positive numbers wraps around a drum. Each number represents the number of cells that share an edge with the cell of the same number. For eg the front and back of the drum can be :

3  3  3

3  3  3

2  2  2

The top and bottom of the drum can be different so the line containing 2 can appear in the first line instead of the last and this will make it a different arrangement. If an arrangement can be rotated to get another, they are the same. How many different arrangements exist for given R x C

const int a[5][6]={1,1,4,1,1,10,2,2,2,6,2,2,1,1,7,1,1,19,1,1,7,9,1,19,2,2,14,10,2,92};

int GetMinArrangements(int R, int C)

{

assert(R > 0 && C> 0);

Int answer = 0;

For (int I = 1; I <= C; i++)

{

    Int d = gcd(C, i)

    answer += a[R-2][d-1];

}

return answer/C;

}

 

Int gcd(int x, int y)

{

If y == 0 return x;

return gcd(y, x % y);

}

Today we continue reading Jigsaw : Efficient, low effort mashup isolation by James Mickens and Matthew Finifter. Mashups are web applications that contain code from different principals.
Jigsaw lets mashups be isolated with its framework  and lets them selectively expose private states. Jigsaw had four goals:
Isolation by default: The integrator has access to browser resources and the guest may be provided some access. However by default a guest cannot access these resources. Most principal's JavaScript namespace is hidden from external code by default .
Efficient, synchronous sharing: Jigsaw enables synchronous, pass-by-reference sharing. If an object is to be shared outside its local domain, a proxy or 'surrogate' automatically wraps and unwraps the object.
Simplicity: Using the above two, Jigsaw can secure mashups with a few lines of policy code
Fail-safe legacy code: If legacy code has not been adapted for Jigsaw, it will work within a single domain and unmodified legacy code will fail safely when accessed by external domains.

Jigsaw prohibits  some Javascript features but these are advanced features that are typically not used and usually exploited by malicious programs. Jigsaw also makes some changes to the core JavaScript language  only to make it behave more like an object oriented. Jigsaw also preserves many of the language features that make JavaScript an easy to use scripting language. For example, objects are passed by reference even when they are exposed out of the isolation domain.
Jigsaw does mashups from different domains. Domains are origins just as we use it in the term cross origin policy. A principal is an instance of web-content provided by a particular domain. An integrator is one that includes another principal by explicitly downloading content from the other principal's origin. Principals can be chained and consolidated just like in a tree hierarchy. A user visiting a top level site is visiting an integrator.
Jigsaw also has a concept of a box. Each box is associated with the following resources:
a JavaScript namespace containing application defined objects and functions
a DOM tree which represents the HTML or CSS of the principal
an event loop which captures mouse and keyboard activity intended for that box
a rectangular visual region with a width, height and location within the larger browser viewport
a network connection which allows the principal to issue HTTP fetches and data.
a local storage area which stores cookie and implements the DOM storage abstraction.
#codejam problem
A R x C matrix of positive numbers wraps around a drum. Each number represents the number of cells that share an edge with the cell of the same number. For eg the front and back of the drum can be :
3  3  3
3  3  3
2  2  2
The top and bottom of the drum can be different so the line containing 2 can appear in the first line instead of the last and this will make it a different arrangement. If an arrangement can be rotated to get another, they are the same. How many different arrangements exist for given R x C
Solution:
htamas gave a python solution as follows:
Take an inital pattern with the positive integer 1 and take initial patterns of these numbers for arrays of 1 x 5 When arranged vertically we can take the arrays corresponding to rows a1, a3, a4, a6, a12. For all rows greater than five  to R + 1, we can repeat their sequences as a pattern of the previous. That is a3 can be extended based on a sequence of a3 and a1 and so on.
The initial answer will be sum of the R and R - 2 column in a.
If the column C is divisible by 3, 4, 6 and 12, the corresponding columns from the a3, a4, a6 and a12 will cumulate to the answer and when we take a modulo with a sufficiently large number we can be accurate to that extent.

Today we continue reading Jigsaw : Efficient, low effort mashup isolation by James Mickens and Matthew Finifter. Mashups are web applications that contain code from different principals.  These principals often have a lop sided trust relationships with each other. For example, a page that shows local news may receive data from a news feed component  and a  map component.  The integrating page may want to isolate both components from each other and present them with an extremely narrow interface to the integrators state. We read that Jigsaw is a framework that extends Javascript and facilitates securing the data sources with simple keywords like public and private.
There have been previous approaches as well but the frameworks were overly complex and presented an unwieldy tool. Many of these approaches force developers to use asynchronous, pass-by value channels for cross principal communication channel.The difficulty with pass-by-value asynchronous calls besides introducing subtle data races is that it introduces high serialization overheads Previous work that involves object views were too general often requiring policy code for each property access on a shared object. The same goes for ConScript policy files where the policy consists of arbitrary Javascript code. They are not only expensive, unnecessary but also too cumbersome for large graphs of objects. The mashups only need to be secured with a yes-no mechanism to define whether they are externally shareable and a simple grammar that restricts access to persistent storage and visual display. These two policy primitives are sufficient for mashups. Consequently they require only simple constructs.
Jigsaw does this and better. It not only lets mashups be isolated with its framework but also it lets them selectively expose private state with the following four goals:
Isolation by default: The integrator has access to browser resources and the guest may be provided some access. However by default a guest cannot access these resources. Most principal's JavaScript namespace is hidden from external code by default .
Efficient, synchronous sharing: Jigsaw enables synchronous, pass-by-reference sharing. If an object is to be shared outside its local domain, a proxy or 'surrogate' automatically wraps and unwraps the object.
Simplicity: Using the above two, Jigsaw can secure mashups with a few lines of policy code
Fail-safe legacy code: If legacy code has not been adapted for Jigsaw, it will work within a single domain and unmodified legacy code will fail safely when accessed by external domains.
#codejam problem
Why does two datapoints suffice in the deer hike problem we saw earlier
Because there are limited number of positions that can be taken on the trail. For example there are 0 to 360 both ends included and a single hiker can occupy all these positions at some point of time. Therefore we are only looking for a safe spot between two hikers which can give an intermediate position for the deer. Since one position is enough, either that position will have encounter or not. Therefore we get our answer.

Today we read a different paper.  This one is titled Jigsaw : Efficient, low effort mashup isolation by James Mickens and Matthew Finifter. Mashups are web applications that contain code from different principals.  These principals often have a lop sided trust relationships with each other. For example, a page that shows local news may receive data from a news feed component  and a  map component.  The integrating page may want to isolate both components from each other and present them with an extremely narrow interface to the integrators state. Another example might be where a social networking page might embed a third party application and an advertisement.  As we can see this applies to web application rendering content from different microservices.  Securing such a mashup application is challenging because the source of the data may not want to expose anything more than a narrow interface to their private code and data. Jigsaw is a new framework that isolates these mashup components.It is an extension of Javascript language and requires a Jigsaw to Javascript compiler. Jigsaw differs from its predecessors in the simplicity of its syntax to make it easy for a domain to tag internal data as externally visible. It uses the well-understood public / private keywords which developers are familiar with. Also unlike previous approaches, it allows mutually distrusting code to runs inside the same frame, this allows scripts to share state using synchronous method calls instead of asynchronous message passing. Yet it provides strong iframe like isolation, Since the code runs within the iframe, Jigsaw allows code to share state using synchronous method calls instead of asynchronous message passing. Also Jigsaw introduces a new encapsulation mechanism called surrogates. Surrogates allow domains to safely exchange objects by reference instead of by value. This improves sharing efficiency by eliminating cross-origin marshaling overhead.  A developers primary challenge in creating mashups is the wide range of trust relationships between mashups.  Sharing information between principals is desired but often required in explicit and controlled ways. This framework makes alleviates this onus and makes it easier for the developers. By implementing it in Javascript, the framework is available to include as client side scripts. This framework also improves the language' support for encapsulation.

#codejam problem

There are N hot water  taps that can be opened and closed one at a time to fill a reservoir with volume V and temperature T. Each tap has a rate Ri and temperature Ti. Find the minimum time required to fill the reservoir. 

If N == 1,
       if T != T0 return -1;
       return time-taken  = v/R0
If N > 1
     If T < min (T0, T1) or T > max ( T0, T1)
              Return -1;
     If T0 == T1 return time taken = v/ (R0+R1)

        t0 = (V - V * T / T1) / (R0 - R0 * T0 / T1)

        t1 = (V * T - t0 * R0 * T0) / (R1 * T1)
      #The respective contributions are taken into account above and since they are independent they can be opened simultaneously
       Return max (t0, t1);
       Courtesy: Zibada Similar to the deer hike problem mentioned earlier

#codingexercise
For simultaneous flow from more than two taps above, we would have the forms
(V - V×T/T1 -V× T/ T2)/ (R0- R0*T0/T1 - R0*T0/T2)

We continue discussing the paper "Shielding applications from an untrusted cloud with Haven,” written by Andrew Baumann, Marcus Peinado, and Galen Hunt. We were reviewing Hardware security modules (HSM) and Trusted Hardware  or Trusted Platform Modules(TPM) that isolate applications from an untrusted OS. We also reviewed related work in shielding application from an untrusted OS. We also looked at hybrid applications that also used encryption. When compared to these systems, Haven seems the first to implement shielded execution of unmodified server applications in an untrusted cloud host. This is roughly equivalent to a user operating their own hardware in a locked cage at a collocation facility.  The host only provides raw resources such as  processor cycles, storage and networking. It can deny service but cannot but cannot observe or modify user data except those in transit and this is called shielded execution. A shielded execution fundamentally guarantees confidentiality and integrity. The former implies that the execution of the shielded program appears as a "black box" to the rest of the system. The latter implies that the system cannot affect the behaviour of the program.  Haven leverages Intel SGX which allows a process to instantiate a secure region of address space known as an enclave. Then execution of code within this enclave is then protected. While the code assumes the OS would behave correctly, the host OS may be malicious. Therefore Haven implements a protected runtime using an in-enclave Library OS (LibOS) using a mutually distrusting interface with the host OS. Combined with a remote attestation mechanism, Haven gives the user end to end guarantee of application security without distrusting the cloud provider, it software or hardware beyond the processor itself. The studies in this paper furthered improvements to SGX to enable efficient shielded execution. SGX performs memory protection by mediating page mappings at enclave setup and maintains shadow state for each page. These pages are allocated by the OS but must occupy a specific region of the physical memory. SGX supports CPU based attestation enabling a remote system to verify cryptographically that specific software has been loaded within an enclave, and establish shared secrets allowing it to bootstrap an end to end encrypted channel within the enclave. SGX also mediates transitions into and out of the enclave and protects the enclave's register file from the OS exception handlers. Revised SGX includes new instructions that allow the enclave and the host OS to co-operatively add/remove pages and modify their permissions. In addion to leveraging SGX, Haven builds on Drawbridge that supports low overhead sandboxing of Windows applications. Thus Haven's design is based on a shield module, an untrusted interface and an untrusted runtime.
#codejam problem
A country has D denominations of its currency.  A new rule mandates that only C number of any denomination may be used. How many minimum new dominations must the mint owner issue to enable all sums from 1 to  a given value V?
int GetMinNewValues(List<int>N, int D, int C, int V)
{
Assert  (N.count == D);
int r = 0;
int m = 1;
while (m <= V)
{
   if  (N.Count > 0 and N[0] <= m)
   {
         m += N[0] * C;
         N.RemoveAt(0);
    }
    else
    {
            r  += 1;
            m += m * C;
     }
}
return r;
}
http://1drv.ms/1RcXlib