Блог пользователя zscoder

Автор zscoder, история, 6 недель назад, По-английски,
Bank Robbery
Cutting Carrot
Naming Company
Labelling Cities
Choosing Carrot
Leha and security system
Replace All
 
 
 
 
  • Проголосовать: нравится  
  • +126
  • Проголосовать: не нравится  

»
6 недель назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

What a fast editorial :))) tnx a lot

»
6 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

why problem B。 the input abc aaa

and the output is aab.

why is not aba.

  • »
    »
    6 недель назад, # ^ |
    Rev. 4   Проголосовать: нравится +3 Проголосовать: не нравится

    If Oleg didn't put 'b' in last postion in the first turn, then he must put 'b' in a position lower than last position which he doesn't want as he wants to make string lexicographically small. Hence, in the first turn, he will put 'b' in the last position.

»
6 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Need help for Problem B using Binary Search. I need clear explanation.

  • »
    »
    6 недель назад, # ^ |
    Rev. 4   Проголосовать: нравится +2 Проголосовать: не нравится
    const double MAX = 1e7;
    double s(double &t)
    {
        double l = 0, r = MAX, mid;
        for (int i = 0; i < 1000; ++i)
        {
            mid = (r+l)/2;
            if(mid*mid > t) r = mid;
            else l = mid;
        }
        return mid;
    }
    
    • »
      »
      »
      6 недель назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      This is the binary search.For double, you just iterate enough times to improve your accuracy.This just like the common binary search. I think you will know it.

»
6 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anybody explain me this line of the editorial of B:

Since the area of this smaller isosceles triangle is the sum of areas of the first i pieces, which is i/n of the whole carrot. Thus, (Xi/h)^2 = i/n

  • »
    »
    6 недель назад, # ^ |
      Проголосовать: нравится +25 Проголосовать: не нравится

    I used the fact that if the ratio of similitude between two similar triangles is r, then the ratio of their areas is r2.

»
6 недель назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

It is said that "It can be proven that in this case, each person will place their current worst (largest if Oleg, smallest if Igor) letter at the back of the string in the optimal strategy." Could someone explain this to me, please?

  • »
    »
    6 недель назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I also wonder how to prove it,could someone explain??

    • »
      »
      »
      6 недель назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      I've thought a little and changed my mind on this question. I still don't understand why should we occupy the last question mark if it is the least significant position in the sequence. Let p be the number of smallest elements of Oleg's set which are greater than max of Igor set. Why shouldn't we put one of our letters to the position i + p, for instance?(i is the position we are trying our opponent to place letter in)

  • »
    »
    6 недель назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    That's what I thought:

    If you have any better letter than your opponent, you should place in the leftmost position. In other case, you should force your opponent to place their letters in the leftmost position, the only way to do that is to place any letter in the last possible position of the string, and the letter chosen is the worst letter, because you want to discard it in the least significant digit — it's nice to notice that you also have the worst letter of the game for you in this case.

»
6 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Someone please explain me the cutting carrot problem's solution?

  • »
    »
    6 недель назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    You just need to make equations making the area of the first trianlge made by the first cut equal to the overall area over n (and so on).

    That is x1*b1/2 = (h*b/2)/n where b1 is the base of the first triangle made by the first cut. b1 is equal to x1 times some constant k. You can determine the exact value of the constant (depending on the relation of b and h) by pitagoras, but this is not necessary. Also notice that this same constant multiples b in the equality h = b*k, therefore you can cross all k's (and all 2's) and get x1*x1 = h*h/n -> x1 = h*sqrt(1/n).

    For the second area, between the first and second cut in the trianlgle, you need to make a subtraction of areas of triangles. (x2*b2/2)-(x1*b1/2) = h*b/(2*n) which implies that x2 = h*sqrt(2/n).

    By induction you get the editorial's formula xi = h*sqrt(i/n).

    • »
      »
      »
      6 недель назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Didn't get this h=b*k; will u please explain it to me? Plz.

      • »
        »
        »
        »
        5 недель назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        let angle of isosceles triangle be i, which will be same for all the isosceles triangle considered so tan i will be constant, let it be k. We know tan i = h/b or k = h/b. So we get h = b*k.

»
6 недель назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

In C in 4 test we have: abc && aaa. The answer is aab, but it isn't correct. The answer is aba. First choice of Oleg — put 'a' at the start, sounds good. But Igor will put his 'a' into the end, because he knows, that letters of Igor will be more useful for him in such case. Wtf?

»
6 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

but in the Naming Company question , is'nt it strictly mentioned that Oleg has to move first.

  • »
    »
    6 недель назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    That's true, but players are free to put their letts in any position that contains a '?'. So Oleg is not necessarily to put his letter in the first or last postion.

    • »
      »
      »
      6 недель назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      oh yes. Thanks. Thats why author made it clear later that each player can see other's letters.

»
6 недель назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

problem B

I do not know why i did not use Binary Search.I use a mathematics method.

scanf("%d %lf",&n,&h); double area=h*0.5/n; n--; double s=0.0; int k=0; int m=n; double base=1.0; double tan=1.0/(2*h); while(n--){ double dis=sqrt(base*base-4*tan*area); double x=(base-dis)/(2*tan); a[k++]=h-x-s; s+=x; base=base-2*x*tan; } for(int i=m-1;i>0;--i) printf("%.12f\n",a[i]); printf("%.12f\n",a[0]);

»
6 недель назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Hi, could someone explain to me what leads to the very first step of the solution of Div 2 D, i.e. "Add each vertex to its own adjacency list"? After reading the tutorial I have no problem to solve it and already got AC, but I was wondering for those who solved it during the contest, does this idea just come out of nowhere or is it a not-well-known trick? During the contest I considered several special cases and tried to categorized vetex by their adjacent neighbors which don't help at all. Are there any similar problems?

  • »
    »
    5 недель назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    A vertex is added to its own adjacency list so that all pairs of vertices which are connected to each other and have the same set of neighbours will have the same adjacency lists.

    Lets say a and b are connected by an edge, and they also have the same neighbours c,d,e etc. (excluding themselves). Adj(a) = [b,c,d,e,...] Adj(b) = [a,c,d,e,...]

    By adding a vertex to its own adjacency list, in this case, the lists become as follows. Adj'(a) = [a,b,c,d,e,...] Adj'(b) = [a,b,c,d,e,...]

    • »
      »
      »
      5 недель назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thansk for your comments, but what confused me here is not "how/why does this solution work", I already understand it and implement it after reading the tutorial. I want to know how those high rating people come to this idea "add a vertex to its adjacent list and group vertex with same adjacent list into one". Because to me it's not obvious or straightforward at all, so I was asking are there any similar problems that use this trick as well.

»
6 недель назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Can somebody explain to me how the test 5 works on problem C. Like what are the movements of the 2 friends. reddit abcdef answer is dfdeed somebody explain why and how the arrived to this answer, thanks.

»
6 недель назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Very nice C problem.

»
6 недель назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

Nice !

  • »
    »
    6 недель назад, # ^ |
    Rev. 3   Проголосовать: нравится +12 Проголосовать: не нравится

    Wont codeforces take any measures? this guy clearly used two accounts and the rating he won was taken from the other contestants.

    UPDATE: Codeforces did take a measure! In his profile there is no sign of participating in this contest (and his rating is the same as before the contest). I wonder if the rating from others changed.

»
6 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It can be proven that in this case, each person will place their current worst (largest if Oleg, smallest if Igor) letter at the back of the string in the optimal strategy.

Mind proving that please?

  • »
    »
    6 недель назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Suppose It is oleg's turn and he knows that the smallest letter he has is bigger or equal to the largest letter Igor has. Thus Oleg would clearly want all of Igor's letters to be ahead of all his letters in the final string. Also, Oleg knows he must place his largest letter somewhere in the resultant string.(Ofcourse when I say largest I only consider ceil(n/2) of his letters). The best place(according to him) for his largest letter,then, is clearly the last available place in the final string. The argument in Igor's case is symmetric.

    • »
      »
      »
      6 недель назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Why should he begin with placing his worst letter in the end? For example, if he wants Igor's letters to be before his(let Igor has x letters) he should place his best letter to the position i + x as it is much more significant than the last, shouldn't he?

      • »
        »
        »
        »
        6 недель назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I mean I don't understand why is it better to occupy farthest positions first whether their contribution to lexicographical order isn't that big.

        • »
          »
          »
          »
          »
          6 недель назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          You have just said the answer ! Its because the influence of the farthest positions are smaller ! For example if:

          Oleg — {a , z , z}

          Igor — {c , d , d}

          First Oleg will put a in the first place, and we have 'a??' .

          Then Igor want to make the string as 'big' as possible. But, look! All Igor characters are smallers then Oleg's one! So if Igor put his d in the second position we would have :

          adz ( after another move from Oleg)

          But if Igor made the move in the way the editorial tells the string would be :

          azd ! ( that is 'bigger' than adz ).

          The point is, if Oleg has a 'small' character, then, for sure, its worth putting it at the left. But if his character is 'bigger' than Igor's one, when he put it at the right most position he will force Igor to put a smaller one in a position to the left of that one ( so, the string will be ' bigger ' )

          Another (extreme) example:

          Oleg — {z, z}

          Igor — {a , a}

          I think now its clear. Oleg has to put the z at the right most position to get 'az', instead of 'za'.

          If not, try with numbers to get the idea:

          Oleg — {9 , 9}

          Igor — {0 , 0}

          a 09 is much better then a 90 for Oleg. The thinking is just what you writed on your comment. A 9 will influence the number much less in the rightmost position, so Oleg places it there, to make Igor place a smaller number at a more significative position.

  • »
    »
    6 недель назад, # ^ |
    Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

    One possible way would be induction and the exchange argument.

    Suppose it's Oleg's turn (the argument is the same for Igor's turn)

    With our claimed strategy, Oleg will place his largest letter x at the back, forming the string ??????....?x (we ignore all the non-question mark characters in between as they're currently irrelevant)

    Suppose Oleg can do better by placing a letter y ≤ x not at the back, so forming the string ???...?y??...?. (If Oleg wants to put a letter at the back, he might as well place his largest one)

    By induction hypothesis, we already know what the other question marks should be replaced. We know that the set of letters Igor have after Oleg's current move is still the same, whereas Oleg will not have x in the first case and not have y in the second.

    ???...?AB....?x

    ???...?yC....??

    Now, you can see that it cannot happen that the second string is less than the first string. It is impossible for any of characters before y to be less than the corresponding letter in the other string by the induction hypothesis (and what Oleg has left is not better than what he would've had if he throw x away). If the character denoted by A is placed by the second player in the optimal strategy, then the first string will be smaller than the second, as all the letters the second player have are smaller. Otherwise, A is placed by the first player and we can see that A is not greater than y or else y would've appeared before A appear and that would mean the matching letter to that y in the second string is larger. However, this implies C is also placed by the first player and B is placed by the second player, and B is not larger than C. If B is equal to C, then we can continue to use the fact that Oleg's letter set after producing the second string is worse than his letter set after producing the first string to see that the second string cannot be strictly smaller than the first.

»
6 недель назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

For the 5th test case :- reddit abcdef why is the answer dfdeed ?

In the first turn, oleg could place d at 1st position, then igor places f in 2nd position, then oleg places d at 3rd position, igor places e at 4th, and in the last step oleg places e at 6th position, and igor places d at 5th. Since oleg wants to create a lexicographically smaller string he places his final larger character(than igor) at the last position. Where am i misunderstanding the idea?

  • »
    »
    6 недель назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    Igor shouldn't place e at 4th position in the 4th turn, but place d at the last position. Then, no matter what Oleg does, dfdeed is the final string.

»
6 недель назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

If I changed my random function "(((ll)rand()<<48)+((ll)rand()<<32)+((ll)rand()<<16)+rand())" to anything else. I would get Accepted on problem D.

rand() in windows is a really excellent function.

»
6 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is there any more intuitive approach for the problem D. I find it very difficult to come up with such a solution during the contest. Thanks for your help in advance!

»
6 недель назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

in problem D solution, I cant findout why in the second graph , labels are diffrent ?

if the above statement is not True so why we cant have a vertex with degree>=3 ?

  • »
    »
    6 недель назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    If two vertices have the same labels they must have the same adjacency list (if we include itself in the adjacency list)

    • »
      »
      »
      6 недель назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Why is this true? I see that vertices with the same adjacency lists have the same label but I can't prove that vertices with the same label must have the same adjacency list.

      • »
        »
        »
        »
        6 недель назад, # ^ |
        Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

        Let's say there are two vertices u and v that have the same label X but different adjacency lists. It means there is some vertex w that is connected to u/v but not to v/u. Now, w's label must be X - 1, X or X + 1. In any of the three cases, the absolute difference between w's label and the label of the node it is not connected to (u or v) is surely less than or equal to 1, which breaks condition.

»
6 недель назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Problem setter is just a High school student, even not in university still? WOW, asian people are astonishing at math. They often say that all is just a hard work. But when I work too hard I do not improve better rather get no improvement at all.

»
6 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Even Petr was not able to solve the last problem by zscoder... I feel demotivated lol.

»
6 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone explain why time complexity for C is O(n)? At the beginning of my solution I've sorted both input strings, that's why I think it should be O(nlogn), and I don't see how to do that without sorting... Am I missing something here?

  • »
    »
    6 недель назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    You don't actually need to sort them, given they are english lowercase letters, meaning characters 'a'-'z'. You can store the total count of each character in arrays oleg[26], igor[26] and if any of it is placed to the resulting string, just subtract 1 (and if 0, move the the next/previous non-zero one).

    • »
      »
      »
      6 недель назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Oh, that's right. Thank you a lot — somehow I didn't think of this... Thanks ;)

»
6 недель назад, # |
Rev. 2   Проголосовать: нравится +55 Проголосовать: не нравится

I've got a slightly different solution for C, but it is boring to explain, so here is the code: 27098472 (upd: slightly cleaner version)

  • »
    »
    6 недель назад, # ^ |
      Проголосовать: нравится +23 Проголосовать: не нравится

    Cool but we would request you to explain further

    • »
      »
      »
      6 недель назад, # ^ |
        Проголосовать: нравится +14 Проголосовать: не нравится

      The idea is: if the current player can profit from placing his best letter at the first position (that is, it is strictly better than allowing the other player move there), he must do so. Otherwise, nobody ever has the incentive to move there, hence it will be free until the last move, when the last to move player will place his best letter there. Therefore, we can store who is the first and the last to move, as well as pointers to the best letters of both players, and construct the answer from left to right.

      In the code above t[0] and t[1] are the pointers, and p[0] and p[1] are indices of the first and the last to move players (although in reverse order and negated to make formulas more compact).

  • »
    »
    6 недель назад, # ^ |
      Проголосовать: нравится +20 Проголосовать: не нравится

    Well, I didn't know you could call functions which depends on the input outside the main... How does it work? Are all of them called prior to any action of the main function?

»
6 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Anyone know how to solve F without getting RE on the test case 8? My solution is almost the exact same as the editorial, but I keep getting RE for some strange reason.

»
6 недель назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

My O(NlogN+M) solution for D problem using hashing. http://codeforces.com/contest/794/submission/27087484

  • »
    »
    6 недель назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can you explain your solution?

    • »
      »
      »
      6 недель назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Let a type of vertex v be the set of vertices that it is connected to, including the vertex v. Each type has its own label.

      For example, if we have the edges:

      1 2

      1 3

      The set of vertices of 1 is {1, 2, 3};

      For optimal comparing we hash the sets.

      From condition |xu-xv| ≤ 1, it's clear that each vertex can only be connected with 3 other types of vertices, one with the same type and label, and two with different types: one with a label+1 and one with a label-1.

      When xu-xv = 0, u and v need to be connected to the same set of vertices (be the same type), otherwise the answer is NO.

      When |xu-xv| = 1, u and v need to be connected to different sets of vertices (be different types)

      For each vertex, we keep two types that it is connected to, D[x] — type of vertex with decreased label and I[x] type with increased one.

      Construction and checking:

      We start in an arbitrary vertex v, put it a label 5000000 (to have a reserve in decreasing) and check if it isn't connected to more than mentioned 3 types. Put the different types in D[x] and I[x], doesn't matter we way of attributing.

      Start a BFS or DFS from v and do the same algorithm.

  • »
    »
    6 недель назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    OK, I got it.

»
6 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In naming company pqr dca than if player 1st play optimal than p?? now 2nd player play optimal since he lnow other player move so p?d now 1st player pqd so answer should be pqd but your code gives pdq hows this possible can u explain this..........

»
5 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

problem c how this test turn

abc aaa

»
5 недель назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

i am not getting how to get to formula in question choosing carrot can someone plzz explain it more

»
5 недель назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Hi, I'm trying to solve the problem F, using segment tree and simply saving digits in separate arrays, only to got a WA on test 8, tried bunch of debug, do someone give me a hand? 27292086

»
3 недели назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

hi

there is greedy solution with O(n + m) for question D (Labelling Cities).

here is the link

i use hashing, bfs and i do something on neighbours of root.

»
3 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It seems that there had some mistakes in the data of the problem D.My code didn't make a special judge when the new graph has cycle.For example,if the input data is : 6 6 1 2 2 3 3 4 4 5 5 6 6 1,the output should be a single line containing the string "NO",but my code will got RE of it.However,my code still got AC after submit.Here is the link

»
2 недели назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Failed to solve F in virtual participation because of the case when x=y. Tricky problem:/