DarthPrince's blog

By DarthPrince, history, 3 months ago, In English,
Tutorial is loading...

Writer: DarthPrince

Tutorial is loading...

Writer: DarthPrince

Tutorial is loading...

Writer: DarthPrince

Tutorial is loading...

Writer: DarthPrince

Tutorial is loading...

Writer: DarthPrince

Tutorial is loading...

Writer: Reyna

Tutorial is loading...

Writer: DarthPrince

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

»
3 months ago, # |
  Vote: I like it +28 Vote: I do not like it

Bonus question for Div1B: try to solve when sigma can be of size of m.

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

    Could you please explain how to solve this (bonus) problem? I've no idea...

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Probably something like

      DP[u][v] is the maximum character needed for a person to be on u (on his turn), the other on v and the first wins no matter what.

      • »
        »
        »
        »
        3 months ago, # ^ |
        Rev. 2   Vote: I like it +2 Vote: I do not like it

        Yes ,you are right.I misunderstood it.
        Expected Complexity:O(n*n*n)

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

          O(n^3 * logn)? The solution I described is O(n * (n + m)). Here's a submission of that solution: http://codeforces.com/contest/917/submission/34697087

          • »
            »
            »
            »
            »
            »
            3 months ago, # ^ |
              Vote: I like it -9 Vote: I do not like it

            Ohh I am sorry.I was thinking something different.Yes you are right!!!

          • »
            »
            »
            »
            »
            »
            3 months ago, # ^ |
              Vote: I like it +5 Vote: I do not like it

            How is this O(n(n+m)) ?

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

              Every (u, v) edge will be considered in state [u][i] for any i, so the transition is O(n*m) and there are O(n*n) states.

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

                There are n*n states and each transition is n*m so isnt the complexity O(n*n*(n+m)) instead of O(n*(n+m))

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 months ago, # ^ |
                  Rev. 2   Vote: I like it 0 Vote: I do not like it

                  No, because if you consider each edge, it will be considered only on the states that the first state is the vertex it starts. So each edge is considered for n states (the first state is fixed but the second can be any of the n).

  • »
    »
    3 months ago, # ^ |
      Vote: I like it -28 Vote: I do not like it

    teja trying to be smart but fails :P

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Congrats, you just caused this problem to become of positive value :P

»
3 months ago, # |
Rev. 2   Vote: I like it +68 Vote: I do not like it

I have a (maybe simpler and elegant?) solution for div1 A.

How would you solve this if no question marks were involved? Well, this is a standard problem. You iterate through the possible substrings and keep a score which starts from 0, which represents how many open brackets we have. Whenever you iterate over a '(', you add 1 and when you iterate over ')', you subtract one. The string is valid iff at the end the score is 0 and at no point during the iteration was the score negative.

For the problem at hand, we do the exact same thing, except we keep one more counter, say qmarks, which represents the number of question marks so far. Obviously, when we iterate over '?'. we increment this counter. Also, if at any point of the iteration we have qmarks > score, then at least one of the question marks has to be an open bracket (if they were all closed brackets, we would have negative score, which is illegal). Therefore, if this situation occurs, increment score and decrement qmarks.

At the end, a substring is legal iff its length is even and qmarks >= score (we can use question marks to close off all remaining open brackets).

Seems simpler than the solution in the editorial (and also doesn't use additional memory, if that's relevant).

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

    simple solution, thank u so much...u saved me from official solution

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

    Nice One :) .

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

    Thanks for such a nice solution.

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

    Huge thanks!!!!!

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I had basically the same solution but (again maybe?) just a little more natural to explain.

    At each moment we will define l and r as minimum and maximum number of unclosed brackets in the sequence before given that it is a prefix of a correct bracket sequence. For every starting position initially l = r = 0. When we iterate over '(' or ')' we obviously increase or decrease both by one correspondingly. When we iterate over '?' we decrease l and increase r by one. If r < 0 at any point we stop here and go to a next starting position. l can't be less than 0, so if l < 0 we increase it by 2. Finally the ending position is possible if and only if l = 0.

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

    Could you please explain it on a test: "???(" ?. Here, if I consider the whole substring, right from the 1st iteration, qmarks > score. so: qmarks = 1 score = -1; qmarks = 2; score = -2; qmarks = 3; score = -3; score = -2

    Hence, the length is even and qmarks >= score. Hence it's legal. But you can't form any valid bracket with this sequence. Am i missing something?

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      When qmarks > score, you decrement qmarks and increase score, not the other way around. The logic is that you turn a question mark into an open bracket, since at least one of the question marks has to be open.

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

    Thank you so much. I don't understand why editorialists don't write editorials like this.

»
3 months ago, # |
  Vote: I like it +30 Vote: I do not like it

Solution #2 for problem D is just beautiful!

  • »
    »
    3 months ago, # ^ |
      Vote: I like it -54 Vote: I do not like it

    And India is blessed to have a coder like you.

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

Div 1 E : "First two variables can be calculated using aho-corasick and segment tree." Can someone explain how to do this? Thanks in advance.

»
3 months ago, # |
  Vote: I like it +3 Vote: I do not like it

How can i solve div2 C with dp?

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

I hope someone can answer my confusion...To Div2 D,I still can't understand the rightness of the editorial.Can this ensure that both players play optimally?

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    if one's make "a" move can make other lose then it is optimally move right? so you have to find a path that the ichar(i) is big enough that the next person cant go any further

    c < int(ch(v, x) - 'a') and dp(u, x, ch(v, x)) = false its mean the ichar you have is larger than the limit now and the ichar you have ,can make the next player fail to move,( dp is false) , thus the state now is true

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

      Thanks a lot!

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

      I steal couldn't understand the problem solution :(

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

        maybe you shoulde study classical sg function first

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

          what is " sg function " ?

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

            Sprague-Grundy theorem you can google it

            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              How Sprague-Grundy theorem can be used here?? can you explain?? It seems that only DP is used here.

              • »
                »
                »
                »
                »
                »
                »
                »
                2 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                I made a mistake...sorry..

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

Could anyone please tell me what is sigma in 917B editorial?

  • »
    »
    3 months ago, # ^ |
    Rev. 3   Vote: I like it +6 Vote: I do not like it

    Sigma is the size of the constraint on the edge. In this case,its 26. If we allowed numbers(from 0 to 9) and alphabets both in the problem, then it would have been 36.

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

Could anyone confirm that this solution is actually O(N^4)? I have a nested loop in the recurrance function which already is O(N^2).

»
3 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Can someone please explain more precise how to make the the dp with matrix multiplication on Div1C/Div2E? Especially how to construct the matrix to be multiplicated and the initial step of the dp? I have tried to mulptiply the matrix m[i][j] as cost to go from state number i to state number j, but I couldn't find the recurrence

»
3 months ago, # |
  Vote: I like it +5 Vote: I do not like it

In E do you even build suffix trees for every si and ti(or just one big suffix tree)? And if you do, how to get position in small tree from position in big tree?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    In my submission (343647) I only build two big suffix trees explicitly.

    In the centroid decomposition I find for each query one node in each of these 'big trees'. After the centroid decomposition I preprocess one of the suffix trees, finding for each of the queries the last node in the suffix tree that is an ancestor of the node from the centroid decomposition and is a suffix of the special word for the query (which is probably what you call 'the position in the small tree', see wlast, oldwlast and qstidx in my code).

    Also at the same time I construct for each suffix of a special word the range in the inorder traversal for that special word that corresponds to the subtree (which is similar to an euler tour of the 'small trees', see bwlid and bwrid in my code).

»
3 months ago, # |
  Vote: I like it +10 Vote: I do not like it

I think problem E can be solve in O(n^2/32)

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

Has anyone submitted O(N2) solution for D?

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

Div1 Problem D dp[u][us][ue] × dp[v][vs][ve] × N × us why N is in this expression? and what N is?

»
2 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

admin, problem E please add this test,it can make my AC code run out of 3 second:(4.4s)

probably this isn't the worst test of my programme

the upper_bound complexity of my programme is O(n*log(n)^2*sqrt(Q))

if we cha carefully it can be failed system test....

n=1e5;

m=400;

num_q=1e5;

int i,j,s,p,q,u,v;

char ch;

for(i=0;i<=100000;i++)
{
    if(i==0)
       ex[i]=1;
    else
       ex[i]=ex[i-1]*base%mod;
}
for(i=0;i<n;i++)
   adj[i].clear();

  for(i=0;i<n-1;i++)
{
    u=i+1;

    v=i+2;

    u--;

    v--;

    ch='a';

   }


     now.id=v;


    now.ch=ch;


    adj[u].push_back(now);


    now.id=u;


    adj[v].push_back(now);


}


ke.clear();




for(i=0;i<m;i++)
{
    int len=i+1;


    for(j=0;j<len;j++)
       tmp[j]='a';


    str[i]=tmp;

    ke[tmp]=i;

}

for(i=0;i<n;i++)
{
    vr[0][i].clear();
    vr[1][i].clear();
}
for(i=0;i<num_q;i++)
{
    qy[i].u=rand()%n+1;
    qy[i].v=rand()%n+1;
    qy[i].k=rand()%m+1;
    //scanf("%d%d%d",&qy[i].u,&qy[i].v,&qy[i].k);
    qy[i].u--;
    qy[i].v--;
    qy[i].k--;
    qy[i].k=ke[str[qy[i].k]];
    qy[i].id=i;
    vr[0][qy[i].u].push_back(i);
    vr[1][qy[i].v].push_back(i);
}
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why are we build only two suffix tree ? and how to release that?