slycelote's blog

By slycelote, 14 years ago, In English

A. Almost Prime

This is a straightforward implementation problem: factor every number from 1 to n into product of primes and count the number of distinct prime divisors.

B. Regular Bracket Sequence

Read the string from left to right and calculate the balance of brackets at each step (i.e., the difference between the number of "(" and ")" characters written out). We need to keep this balance non-negative. Hence, every time when the balance equals 0 and we read the ")" character, we must omit it and not write it out. The answer to the problem is twice the number of ")" characters that we wrote out.

C. Parquet

We'll derive several necessary conditions for the parquet to be possible. If some of them is not fulfilled, the answer is "IMPOSSIBLE".
1. m*n must be even, because it equals the total area of the parquet, and the area of each plank is even.
2. Suppose m (the number of columns) is odd. Paint the living room in two colors — black and white — in the following way: the first column is black, the second one is white, the third one is black, ..., the last one is black. The number of black squares is n greater than the number of white squares. The planks 1x2 and 2x2 contain an equal number of black and white squares, so we must compensate the difference with 2x1 planks, and their number must be at least n/2. In this case we can parquet the last column with these planks, decrease b by n/2 and decrease m by one.
3. If n is odd, then by similar reasoning a ≥ m / 2.
4. Now m and n are even. A similar reasoning shows that the number of 1x2 planks used must be even, and the number of 2x1 planks used must be even. So, if a is odd, we decrease it by 1, and the same with b.
5. Now we must have mn ≤ 2a + 2b + 4c, because otherwise the total area of planks would not be enough.
6. If all the conditions were fulfilled, we can finish the parquet: divide it into 2x2 squares, and use one 2x2 plank, two 1x2 planks, or two 2x1 planks to cover each square.

D. Tickets

If we picture the graph of the number of 10-euro banknotes, it will be a broken line, starting at the point (0, k) and ending at the point (m+n, n+k-m). Exactly m segments on the line are 'going down', and other n segments are 'going up'. Hence the total number of possible graphs is C(m + n, m) (the binomial coefficient). We need to find out the number of graphs which don't go under the X axis. To do that, we'll calculate the complementary number: the number of graphs which go under the X axis, or, equivalently, intersect the line y=-1.

Here we'll use the so-called 'reflection principle'. Consider any graph that intersects the line y=-1, and take the last point of intersection. Reflect the part of the graph from this point to the end with respect to the line y=-1. We'll have a new graph, ending at the point (m + n,  - 2 - n - k + m). Conversely, any graph ending at this point will intersect the line y=-1, and we can apply the same operation to it. Hence, the number of graphs we're interested in equals the number of graphs starting at the point (0, k) and ending at the point (m + n,  - 2 - n - k + m). Let a and b be the number of segments in such a graph which go up and down, respectively. Then a + b = m + n, a - b + k =  - 2 - n - k + m. It follows that a = m - k - 1, and there are C(m + n, m - k - 1) such graphs.

So, the probability that the graph will go down the X axis is C(m + n, m - k - 1) / C(m + n, m) = (m!n!) / ((n + k + 1)!(m - k - 1)!) = (m(m - 1)... (m - k)) / ((n + 1)(n + 2)... (n + k + 1)). The answer to the problem is 1 - (m(m - 1)... (m - k)) / ((n + 1)(n + 2)... (n + k + 1)).

E. Multithreading

It's clear that we must have 1 ≤ w ≤ Σi ni. If this condition is true, we show how to achieve the desired result in the following cases:
1. N = 1, w = n1. Obvious.
2. N ≥ 2, w ≥ 2. For w = 2, the schedule is the following: 1, all loops of processes 3..N, n2 - 1 loops of the second process, 1, 2, n1 - 1 loops of the first process, 2. For w > 2, we just need to move several loops from the middle of the sequence to the end.
3. N ≥ 2, w = 1, and there exists an index i such that ni = 1. Then the schedule is the following: i, all loops of other processes, i.

Now we'll show that in any other case the result w is impossible. The case N = 1, w ≠ n1 is obvious. We have one more case left: N ≥ 2, w = 1, and ni > 1 for each i. Suppose that there exists a schedule which results in y = 1. Consider the last writing operation in this schedule; suppose it is executed by the process i. Then the corresponding reading operation should have read the value y=0. This means that there were no writing operations before. But this is impossible, since ni > 1, and this process executed ni - 1 read/write loops.
  • Vote: I like it
  • +24
  • Vote: I do not like it

| Write comment?
14 years ago, # |
  Vote: I like it +6 Vote: I do not like it
Thanks, nice reflection trick explanation.
only seems after we reflect (n+k-m) we get (-2-n-k+m)
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Great! Thank you!
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Give me pls test #8 in C problem
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Regular bracket sequence
Why  WA  on test 3?
#include<iostream>
#include<string>
using namespace std;
string a;
long int k(long int );
int main(){
cin>>a;
long int j=a.length(),b,d=0,g=0;
long int c=0;
for(long int i=0;i<j-1;i++)
{
         b=k(i);
         if(b>1)
         i+=b-1;
         if(b!=0)
         {
         d=d+b;
         }
         else
         {
         d=0;
         }
         if(d>g)
         g=d;
}
cout<<g<<endl;
cin>>g;
return 0;
}
long int k(long int h)
{
    if(a[h]==')')
    return 0;
    long int s=0,f=0,n=0,j;
    j=a.length();
    for(long int i=h;i<j;i++)
    {
             if(a[i]=='(')
             s++;
             if(a[i]==')')
             f++;
             if(f==s)
             {
             n=i-h;
             return n+1;
             }
    }
    return n;
}
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
My English is bad, I can't understand the solution  for problem C , can anyone explain it for me,plz ? I'm confused from this " To do that, we'll calculate the complementary number....".
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Well, instead of counting the number of 'good' graphs, we count the number of  'bad' ones and then subtract it from the total number of graphs, that's all :)
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any other technique to achieve the formula for problem D except the reflection method?

»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Here in problem D tickets isn't the permuation important.If suppose we have a favourable order i.e. order which will smoothly run so we can also permute the people having 10 euros and 20 euros amongst themselves in m! and n! ways.This will account for a different pattern .I am unable to guess why is that not taken into account.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good tutorial

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain how the reflection principle work in D? I cant see how - 2 - n - k + m has been derived?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If points y1 and y2 are symmetric with respect to y0, then we must have y0-y1 == y2-y0, which gives y2 == 2*y0 - y1. In this case y0 == -1, y1 == n+k-m.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Old is Gold..