HolkinPV's blog

By HolkinPV, 9 years ago, translation, In English

490A - Team Olympiad

The teams could be formed using greedy algorithm. We can choose any three children with different skills who are not participants of any team yet and form a new team using them. After some time we could not form any team, so the answer to the problem is minimum of the number of ones, twos and threes in given array. We can get O(N) solution if we add children with different skills into three different arrays. Also the problem could be solved in O(N2) — every iteration find new three children for new team.

490B - Queue

This problem can be solved constructively. Find the first student — it is a student with such number which can be found among ai and could not be found among bi (because he doesn’t stand behind for anybody). Find the second student — it is a student standing behind the first, number ai of the first student equals 0, so his number is a number in pair [0, bi].

After that we will find numbers of all other students beginning from the third. It can be easily done using penultimate found number. The number of the next student is a number bi in such pair where ai equals to number of penultimate found student number (that is a number in pair [ans[i - 2], bi]). Look at the sample to understand the solution better.

490C - Hacking Cypher

At first, let’s check all prefixes of specified number — do they have remainder 0 when divided by the a? It can be done with asymptotic behavior O(N), where N -length of specified number C. If we have remainder of division by a of prefix, which ends in position pos, we can count remainder in position pos + 1: rema[pos + 1] = (rema[pos] * 10 + C[pos + 1]) % a.

Then we need to check suffixes.If we have remainder of division by b of suffix, which begin in position pos, we can count remainder of position pos - 1: remb[pos - 1] = (C[pos - 1] * P + remb[pos]) % b, where P — it is 10^(L - 1) module b, L — length of suffix (P we can count parallel).

Now let’s check all positions pos — can we cut specified number C in this position. We can do it if next four conditions performed: prefix of number C, which ends in pos is divisible by a; suffix of number C, which begin in pos + 1 is divisible by b; length of prefix and suffix more than 0; first digit of suffix is different from 0. If all four conditions performed we found answer. If we did not find any such positions, than print NO.

490D - Chocolate

We can change the numbers by dividing their by two or by dividing their by three and multiply two. Firstly remove all 2 and 3 from factorization of chocolate and determine equals their square or not. If their squares are not equals answer doesn’t exists. Otherwise calculate of difference between number of three in factorization, we should remove this amount of threes from the some chocolate, it depends from the sign, and recalculate difference between number of two in factorization and do the same.

490E - Restoring Increasing Sequence

Let’s iterate on specified numbers and try to make from current number minimal possible, which value more than value of previous number. Let’s current number is cur, previous number is prev.

If length of number cur less than length of number prev — let’s print NO, this problem has not solution.

If length of number cur more than length of number prev — replace all signs ? in number cur to digit 0, except case, when sign ? in first position — replace him on digit 1, because numbers in answer must be without leading zeroes.

Another case when lengths of numbers a and b are equal. Let’s iterate on positions pos, in which prefix number cur more than prefix of number prev. Now we need to try for this position make minimal possible number, which more than prev. In all positions posi, which less than pos, replace all ? on prev[posi]. In all positions posi, which more than pos, replace all ? on digit 0. If cur[pos] =  = ? than make cur[pos] = max(prev[pos] + 1, 9).

If received number less or equal to prev — this position is bad. From all good positions choose minimal number, received with operations above and assign him number cur and will continue iteration. If count of such positions is 0 we need to print NO.

490F - Treeland Tour

The problem is generalization of finding maximal increasing subsequence in array, so it probably can be solved using dynamic programming. We will calс dynamic d[(u, v)], the state is directed edge (u, v) in tree. Value d[(u, v)] means the maximum number of vertices where the band will have concerts on some simple path ended in vertex v going through vertex u. Also the concert in vertex v must be certainly.

To calc d(u, v) we should consider all such edges (x, y) that there is simple path started in x, going through y, u and ended in v. These edges can be found using dfs from vertex u which is not going through vertex v. All edges used by dfs should be reoriented. So if r[y] < r[v] then d[(u, v)] = max(d[(u, v)], d[(x, y)] + 1). The solution needs O(N2) time and O(N2) memory. The memory could be O(N) if you get indexes of directed edges without two-dimensional array.

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

| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

comments soon

»
9 years ago, # |
  Vote: I like it -7 Vote: I do not like it
Why soon ?
»
9 years ago, # |
  Vote: I like it -9 Vote: I do not like it

How to find a student which in first place in problem B?

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

    You might use map-container. Every non-first and non-last student appears in the input twice. Just keep the map <Student ID, appearances> and traverse it at the end.

»
9 years ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

In problem E, case: lengths of number a and b are equal, if (cur[pos]=='?') then cur[pos] = max(prev[pos] + 1, 9) or cur[pos] = min(prev[pos] + 1, 9) ?

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

    it can't be max(prev[pos] + 1, 9)

    it should be min(prev[pos] + 1, 9)

    i think it is a typing mistake

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

Will someone please explain approach to problem D : Cholocate ?

I am not able to get the explanation described...

Thanks

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

    +1, the comment says: " Firstly remove all 2 and 3 from factorization of chocolate and determine equals their square or not.". This sentence makes no sense....

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

      You can factorize the dimensions of the chocolate. Taking the second sample case, you have 36 × 5 and 10 × 16; the factorizations are 36 = 22·32, 5 = 5, 10 = 2·5, and 16 = 24.

      Now you remove all factors of 2 and 3. Thus, 36 turns to 1, having all factors removed. 10 turns to 5, having the 2 removed but not the 5. 5 remains a 5.

      After doing this, we are left with 1 × 5 and 5 × 1. The areas are equal (both are 5), so we can solve this (at least by cutting all chocolates by thirds, then by halves; we will always end up with 1 × 5 and 5 × 1 if we keep doing the cutting, although there might be a better solution). If the sizes aren't equal (such as in third sample case, where you have 1 × 5 = 5 and 1 × 1 = 1), you can't solve it.

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

        I got wrong answer for test 12, but when I checked the results from jury's and my outputs, they are both correct, I mean number of minutes in both outputs are the same and aXb equals cXd where a,b,c,d are the sides of those chocolates. here is my code 11133391 and judge result http://postimg.org/image/4qmj8m90b/

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

Is there any faster solution for F than O(N2) ?

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    I can't follow all the logic, but this looks like O(N * logN) to me: 8816064

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      I'm not sure but I think it's O(N*(logN)^2). In each "MergeQuery" operation, it takes O(logN) for every node in tree2 to query and insert. By controling the size of t2 smaller than t1, it can be guaranteed that every node will be involved in a MergeQuery option for at most logN times. I think this upper bound can be reached in a full binary tree.

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

      Hey I_love_Hoang_Yen, I implemented the O(N^2 * logN) solution in Java similar to your submission but it gives me TLE. I'd appreciate it if you could take a look and point out if I'm doing something wrong: Treeland Java submission

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

Hey! could you further explain D.chocolate more clearly? What do you mean by saying: "Firstly remove all 2 and 3 from factorization of chocolate and determine equals their square or not". Whose square equals who? Really appreciate it......

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

    Well, I think it means you should check whether the products of the width and height after removing all 2 and 3 are the same. The "square" in the sentence seems weird to me though.

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

Is there any sample code of problem F using the idea in the tutorial? I can't understand how to implement this......

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

    My submission (http://codeforces.com/contest/490/submission/8886626) is pretty much like that.

    Things to be aware of: You have to add a dummy edge coming from (but not to) any leaf to a dummy node.

    I also do not use DP, but rather memoization, that way I do not have to worry about the order in which I process the edges.

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

My program on pretest 8 in question A, gives the wrong answer, but why? Please somebody help me. My program:(in Python 3)

N=int(input())
T=list(map(int,input().split()))
Output=[]
I=0
while 1 in T and 2 in T and 3 in T:
   try:
      if T[I]==1:
         Output.append([I+1])
         T[I]=0
         for I in range(N):
            if T[I]==2:
               Output[len(Output)-1].append(I+1)
               T[I]=0
               for I in range(N):
                  if T[I]==3:
                     Output[len(Output)-1].append(I+1)
                     T[I]=0
                     break
               break
   except IndexError:break
   I+=1
print(len(Output))
for I in range(len(Output)):
   for I2 in range(3):
      if I2==2:print(Output[I][I2])
      else:print(Output[I][I2],end=' ')
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well, you use index I twice inside the try block... I'm pretty sure that changing the index to a unique name (for example, use "for J in range(N)" the first time and then "for K in range(N)") will lead to a correct answer in that test. Also, I think the algorithm will be too slow to pass all the tests. The condition in the while loop takes O(N) to evaluate, and then you make an O(N^2) loop inside.

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

      No,Python it does. If two "for" at the same time to counter the "I" the two "I", by mistake do not move . My problem is that when all the students in the teams my program one fewer runs Anyway, thank you that you are trying to debug my program but my problem still remains ...

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

        Oh, sorry for my ignorance :( Yesterday I made a submission based on your code, would you mind taking a look at it? 8849662 If I understood correctly, this solution passes the test you mentioned. If not, I apologize for my mistakes.

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

          Thank you very much. I have no problem with my program & I think Time Limit Only in python codes(for this question)

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

            No, you have TLE everywhere. O(N3) algorithm will not pass for N = 5000 even with C/C++ (two of the fastest languages on Codeforces). You need to rethink your algorithm.

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

        No, it doesn't. True, the I in the outer for (the one directly inside try) will not be affected as it iterates along range(N), but the I outside (the global variable) will be affected; when it exits the for/for loop, I will be equal to N-1 (being the last value in the inner list).

        Here is a modified version of your code, where I removed the output code and added a print statement for what value of I and in which loop the program is currently reading. As you can see, after breaking out from the innermost loop, I retains its value, leading to global 5 instead of the expected global 1. (This also means 1 1 2 2 3 3 fails your program, as you only got the first 1 2 3, not finding the second.)

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

          Oh, Yes! Your edit is best edit with my code. I'm a Python newbie programmer. Thank you for helping me.

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

Could anyone tell me what's wrong with my code for F? 8840730 I get TLE on test #53 and I'm not sure why :/

Thanks !

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Your algorithm seems to be O(N3), when it should actually be O(N2) or a low constant factor O(N2 * logN).

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

      Thanks! :) I think I get it, it's because I do the LIS search at the end of every path, so there are a lot of repetitive search.

      I don't see why it is O(N3) though, I would think my solution is O(N2logN) which is why it doesn't pass as it is supposed to be O(N2). Am i wrong ?

      • »
        »
        »
        »
        9 years ago, # ^ |
        Rev. 4   Vote: I like it +1 Vote: I do not like it

        O(N2logN) can pass easily, I think. My solution is O(N2logN) because of some unnecessary binary search, but it still pass in 124ms. I think your solution is O(N3logN) because you have to enumerate all the vertex in the tree as the root. Maybe there's a more accurate analysis though... Edit: My example is wrong, but I still think it's not O(N2logN).

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

          I think you are right ! I believe my solution is O(N2 + PNlogN) where the O(N2) is for the dfs and the O(PNlogN) where P is the number of paths to search LIS can be up to N2 (let's say each node is match to all the other nodes) so effectively the total complexity is O(N3logN) which is too slow!

          Thanks for the help !

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

I am unable to understand D-Chocolate.All I can understand is iff you have a1*b1 and a2*b2 first remove all 2's and 3's from them and after removing if a1*b1!=a2*b2 then answer is NO else we have to do something. Can anybody tell me what next we are supposed to do?

  • »
    »
    9 years ago, # ^ |
    Rev. 3   Vote: I like it +7 Vote: I do not like it
    • Each time you do a type 1 operation, if the area of the rectangle is 2i * 3j, then it will become 2i - 1 * 3j.
    • Each time you do a type 2 operation, if the area of the rectangle is 2i * 3j, then it will become 2i + 1 * 3j - 1.

    The idea is to make the exponents in a1*b1 and a2*b2 equal.

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

Is it possible to get full test-cases of Problem-E ? I am getting WA in test-case 9, but the test-case is truncated after some values. There are dots (...) which means continue, but the full test-cases are not there.

Is there anyway to get this I am missing?

Thanks.

  • »
    »
    9 years ago, # ^ |
    Rev. 8   Vote: I like it 0 Vote: I do not like it

    Mistake is in lines 55-66 of your code. Your programm doesn't react if two numbers are equal

    Test:
    2
    1
    1

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

      Thanks Kefaa!

      My code had another major problem. After submitting 17 times I got Accepted!!! Yaaayyyy...!!! :D :D :D

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

After reading the tutorial, I realized how unnecessary this solution by me is: http://codeforces.com/contest/490/submission/8829276

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

In D-Chocolate could any one explain that why does a solution exist after removing all 2's and 3's as factors ??

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    You can see the no. of segments in each chocolate bar, as factorized by 2 and 3:  . the actions only change x and y, not K. So if two K do not equal, answer doesn't exist.

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

well, i am a beginner....here in PRBLM A told to print any of the solution....for the first pre test why it is ans 3 5 2 and 7 6 4 why not 1 5 2 and 3 6 4....

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

    Both of them are right answer for test 1 so you can output one of them.

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

Well,I'm not familiar to this website,I want to know where can I get the whole test data◔ ‸◔? I don't know why I'm wrong on test 7,and the test data on the website is not complete(..•˘_˘•..)

Here: http://codeforces.com/contest/490/submission/8895986

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

hello PROB : B http://codeforces.com/contest/490/my#

got TLE on test case 46 what can I do?

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

could anyone help me on how to solve Div2 Problem B using disjoint set data structure, as I found dsu tag attached with this problem.

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

I didn't understood the explanation for 490F so I went for browsing other's code instead, and here is a much more easier solution related to LIS with O(n^2 * log(n)) time complexity.

If you happen to be familiar with the LIS algorithm, you would understand that each time we visit a new node we just find the place where the new node could just fit into the optimal LIS, the only problem left is how do we choose the first position of the sequence and how do we handle a node leaving the LIS. (i.e. it has reached it's end in the euler tour)

So far I haven't come up with a brilliant answer with the first question, so it would be left as brute force from each node instead.

For the second question, keep a 2D-vector(or stack to be precise) to store the values, when a node leaves, just pop it from it's corresponding position and update the value from the updated top of the stack. This resets the LIS back to the state before visiting the subtree.

My implementation after viewing others ideas: http://codeforces.com/contest/490/submission/19867543

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

    Hi haleyk100198 do you know why works when only calls the dfs from leaves?

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      If you are talking about my approach, it only works when it is called from the starting point of the journey.

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

    haleyk100198 what's the complexity of your solution?
    thanks!

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

      "here is a much more easier solution related to LIS with O(n^2 * log(n)) time complexity."

      Here, you are required to run O(n) dfs which takes O(n) time each, and the LIS algorithm inserts each node with a O(logn) time complexity.

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

in problem C why %b is done after multiplying with 10

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

    i think that we need a proof :/

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

    as we know number's length can be bigger than 10^6 so we have to make it smaller . ( to check %b) , so we go from rightmost number . keep in mind that in modular arithmetic we have properties :

    (a+b)%c = (a%c + b%c) % c

    (a*b)%c = ((a%c) * (b%c)) % c

    suppose we have ...262 and b is 13 .

    let's start from 62 we are interested in what is

    (62)%13 . 62 = 6*10 + 2 ,

    62 % 13 = (6*10 + 2) % 13 -> (6*10 % 13 + 2 % 13) % 13

    then take 262

    262 = (2*100 + 6*10 + 2),

    262 % 13 = (2*100 %13 + 6*10 % 13 + 2 % 13) % 13 ,

    we already know ( 6*10 % 13 + 2 % 13 ) % 13 so we take it from previous step , and we have to make 1 more thing , because our number 100 can get 10 ^ 6 , we have to make it smaller too , so we take (100%13) , then ((100%13)*10)%13 and so on ... i hope it helps :d

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