Sayakiss's blog

How to check whether an arbitrary graph is 3-colorable in time O(2^N)?
By Sayakiss, 13 years ago, In English

n is the number of vertex and Bruteforce is O(3^n)..Thanks in advance. 

(it's a additional exercise of SRM487D1_550pt)

Full text and comments »

  • Vote: I like it
  • +2
  • Vote: I do not like it

a O(n^2) solution for SRM517D1_600pt
By Sayakiss, 13 years ago, In English
I just reduce this problem to another:
Given the relations(larger than or less than) of permutations, find out how many permutation satisfy the relations.
(D-f[i]>f[i+1],I-for f[i]<f[i+1])
if the relation is 'DD',then there is only one permutation satisfies the relation:3 2 1.
if the relation is 'DI',then there is two permutations satisfy the relation:3 1 2,2 1 3.

if i-th relation is D,assign a direct edge from i to i+1.
if i-th relation is I,assign a direct edge from i+1 to i.
(DI - 1->2<-3,DD - 1->2->3)
then the ans is the number of topological sorts of this graph.
A friend told me he solved this problem use a n^2 dp:
dp[i][j] is the number of ways which I have decided the i-th number,and there is still j unused numbers larger than the i-th number.
(note that if there is n relations in total,then there is n+1 numbers.)
take an example:
if the relation is DI
dp[1][1]=2 - 21(only 3 is larger than 1 and 2 is uesed),31.(32 is invaild,because there is no unused number than 2).

it's obvious that any instance of the SRM517_600pt can be reduce to this problem's and can be solved by n^2(and I passed the ST).

it's my code(you can view my whole code in the practice room):


        for(int i=0;i<=n;i++) dp[0][i]=1;
        for(int i=1;i<=n;i++)
        {
            if (f[i]==1)
            {
                int sum=0;
                for(int j=n-i;j>=0;j--)
                {
                    dp[i][j]=(0ll+dp[i][j]+dp[i-1][j+1]+sum)%m;
                    sum=(sum+dp[i-1][j+1])%m;
                }
            }
            if (f[i]==2)
            {
                int sum=0;
                for(int j=0;j<=n-i;j++)
                {
                    dp[i][j]=(0ll+dp[i][j]+dp[i-1][j]+sum)%m;
                    sum=(sum+dp[i-1][j])%m;
                }
            }
        }
        int ans=0;
        for(int i=0;i<=n;i++) ans=(ans+dp[n][i])%m;
return ans;
I just wonder,is there any batter explain for this algorithm?

Full text and comments »

  • Vote: I like it
  • +1
  • Vote: I do not like it

Misunderstood the problem but miraculously got an AC
By Sayakiss, 13 years ago, In English

Given a node in Stern-brocot Tree,the task is to output its path to the root.

At my first attempt to solve this problem, I glanced through the description and mistake it for Calkin-Wilf Tree(probably because I just knew Calkin-Wilf tree at that time),and I just output the path in Calkin-Wilf tree,and got an Ac.Just then I noticed the difference between the tree in my mind and the problem's.The appearance of these two trees is entirely different,but the path is the same!How it could happen?
I tried to prove the correctness of my solution,but failed at last.(I got no positive result although spending several hours on it)
can anyone explain this miracle?

The path to root of Calkin-Wilf Tree is quite simple.
a node(a,b),the father is：
(a-b,b) a>b
(a,b-a) a<b
(1,1) a==b (it's the root!)
if you are familiar with the Euclidean Algorithm,the repeated subtraction obviously can be replaced by modulo operation for efficiency.
this is my code:

  • #include<cstdio>  
  • int main()  
  • {  
  •     int a,b;  
  •     while(scanf("%d%d",&a,&b)&&(a!=1||b!=1))  
  •     {  
  •         for(;a&&b;)  
  •         {  
  •             int t;  
  •             if (a>b)  
  •             {  
  •                 t=a/b;  
  •                 if (!(a%b)) t--;  
  •                 for(int i=0;i<t;i++) putchar('R');  
  •                 a%=b;  
  •             }  
  •             else  
  •             {  
  •                 t=b/a;  
  •                 if (!(b%a)) t--;  
  •                 for(int i=0;i<t;i++) putchar('L');  
  •                 b%=a;  
  •             }  
  •         }  
  •         puts("");  
  •     }  
  • }  





    • Full text and comments »

    • Vote: I like it
    • 0
    • Vote: I do not like it

    The root of ax+by=c given by Extended Euclidean algorithm is always smaller(or equal) than max(abs(a),abs(b))?
    By Sayakiss, 13 years ago, In English

    void exgcd(int a,int b,int &x,int &y)

    {
    if (b) {exgcd(b,a%b,y,x);y-=x*(a/b);}
    else x=1,y=0;
}
int main()
{
    int x,y;
    for(int i=1;i<=1000;i++)
    for(int j=i;j<=1000;j++)
    {
        exgcd(i,j,x,y);
        assert(max(abs(x),abs(y))<=max(i,j));
    }
}

    this code ends without exception,that is to say,the root x,y equals or smaller than max(i,j) in [1..1000,1..1000].
    I just wonder if it will hold for any i,j?
    can anyone prove or disprove it?

    Full text and comments »

    • Vote: I like it
    • 0
    • Vote: I do not like it

    How to find the old topics without recent actions?
    By Sayakiss, 13 years ago, In English

    Sometimes I just want to review a topic which I have ever read before,but there is no convenient approach to find it unless it is still appeared in "recent actions".

    It seems that the only way to view old topics is to memorize who post it and to find the topic from his profile page.

    Full text and comments »

    • Vote: I like it
    • 0
    • Vote: I do not like it

    how to solve an n,m-knight jumps reachable problem?
    By Sayakiss, 13 years ago, In English

    My threads in Topcoder forums  

    (SRM 514 250) In this problem n or m will be 1 and there is a elegant conclusion to solve this problem -- if you have a (1,even),you can go any girds,and if you have a (1,odd),you can go to any girds(x,y) which x+y is even


    Similar to SRM 514 D1250,you can go from (0, 0) to (n, m), (n, -m), (-n, m), (-n, -m), (m, n), (-m, n), (m, -n) or (-m, -n) by a n,m-jump.
    Given a set of valid jumps,can go from (0,0) to (X,Y)?

    it seems to find a integer root of these equations:
    n1*k1+n1*k2-n1*k3-n1*k4+m1*k5+m1*k6-m1*k7-m1*k8+n2*k9...=X
    m1*k1-m1*k2+m1*k3-m1*k4+n1*k5-n1*k6+n1*k7-n1*k8+m2*k9...=Y
    ki means performs the (i%8)-th directions of (i/8+1)-th jump-types ki times.

    if the set of jumps is {(1,2)} and X=5 Y=4,the equations will be like that:
    k1+k2-k3-k4+2*k5+2*k6-2*k7-2*k8=5
    2*k1-2*k2+2*k3-2*k4+k5-k6+k7-k8=4
    a integer root of that equations is k1=1,k5=2,k2=k3=k4=k6=k7=k8=0.
    (1+2*2=5 2+2*1=4)
    that means (0,0)->(1,2)->(3,3)->(5,4)

    but i can't solve equations like this...or there may be a more elegant algorithms to solve this problem?

    sorry for my poor English.
    ————————
    if there is one element in jump set,it just the same as this problem:
    http://acm.timus.ru/problem.aspx?space=1&num=1286
    ----------------
    I just thought out a 2^(2n)(n is the size of valid jumps set) algorithm to solve this problem,but not to solve this equations.

    assume (ni,mi) is the ith jump type.
    first of all,I notice that you can go from (0,0) to (0,2*ni) and (0,2*mi).
    that is the point (0,X) which 2k1n1+2k2m1+2k3n2+2k4m2..=X is reachable.

    it can be proved that X=k*gcd(2*n1,2*m1,2*n2,2*m2...).
    let g=gcd(n1,m1,n2,m2...)
    you can go from (0,0) to (0,k*2g).
    Similarly, (k*2g,0) is reachable.

    So,(k1*2g,k2*2g) is reachable.
    if the destination point is in (2k1*g,2k2*g) so the answer will be yes.

    any jumps performs twice will go from a (2k1*g,2k2*g) to another (2k1*g,2k2*g), 
    and the point ignored is the point from a (2k1*g,2k2*g) reached by perform no two same jumps.

    So,we just enumerate the ways of single jumps and just to calculate the destination whether to be reach by single jumps from (2k1*g,2k2*g).
    there is 2^2n ways.

    Considering my poor English, I take a example to illustrate my algorithm.
    let jumps set={(1,even)},the g=1.2*g=2.
    so the (even,even) is reachable.
    and the single move and combinations will be (1,even) (even,1) (even+1,even+1)<-that is the combinations of moves of first two type .

    case1:if destination is (even,even), it obviously can be reached.
    case2:if destination is (even,odd), it minus (even,1) leaves a (even,even).that is to say,we perform a single (even,1) and then perform some double same moves can get the destination.
    case3:if destination is (odd,even),it just similar to case 2.
    case4:if destination is (odd,odd),we minus (even+1,even+1) and we also get (even,even).

    So,(1,even) can go anywhere.
    ————————
    there is a more elegant algorithm.That is O(nlogn).The main idea is compressed the space by g.
    How about this:
    Let g=gcd(m1,n1,m2,n2,....)
    Now, if X%g != 0 or Y%g != 0, then we do not have a solution.
    So now, you can divide X, Y, m1, n1, m2, n2, ... all of them by g.
    Now, if (X+Y)%2==0, then we have a solution
    Otherwise, if atleast one of the (mi+ni)%2!=0, then also we have a solution
    Otherwise, we do not have a solution.

    Full text and comments »

    • Vote: I like it
    • +15
    • Vote: I do not like it