RetiredAmrMahmoud's blog

By RetiredAmrMahmoud, 4 years ago, In English,

507A - Amr and Music

Problem: We have to split the number k into maximum number of elements of ai such that their sum is less than or equal to k.

Hint: To maximize the answer we have to split the number into the smallest numbers possible.

Solution: So and since the limits are small we can pick up the smallest element of the array and subtract it from k, and we keep doing this n times or until the smallest number is larger than k. Another solution is to sort the array in non-decreasing order and go on the same way.

Time complexity: or

Implementation: 9529124 .

507B - Amr and Pins

Problem: We have a circle with radius R at position (x, y) and we want to move it to (x', y') with minimum moves possible. A move is to choose an arbitrary point on the border of the circle and rotate the circle around it with arbitrary angle.

Hint: What is the shortest path between two points? A direct line. So moving the center on that line with maximum move possible each time will guarantee minimal number of moves.

Solution: Let's draw a straight line between the two centers.

Clearly to move the center with maximum distance we need to rotate it around the intersection of the line and the circle with 180 degrees. So the maximum distance we can move the center each time is 2 * R. Let's continue moving the center with 2 * R distance each time until the two circles intersects. Now obviously we can make the center moves into its final position by rotating it around one of the intersection points of the two circles until it reaches the final destination.

Every time we make the circle moves 2 * R times except the last move it'll be  ≤ 2 * R. Assume that the initial distance between the two points is d So the solution to the problem will be .

Time complexity:

You have to be careful of precision errors. Here is a code that used only integer arithmetic operations 9529147.

507C - Guess Your Way Out!

Hint: Simulate the algorithm until we reach a leaf node assume that it's not the exit. Now the question is Are there some nodes that are guaranteed to be visited before trying to reach the exit again?

Solution: The first observation is that in order to return to a parent we will have to visit all nodes of the right or the left subtree of some node first. Now imagine we are in the situation below where E is the exit.

By applying the algorithm we'll reach node X. Both the E and X are in different subtrees of the root. Which means before going to the proper subtree in which the Exit exists we'll have to visit all the nodes of the left subtree (marked in red).

This means we have to get the node which the Exit and the current leaf node X are in different subtrees which will be the least common ancestor (LCA) of the two nodes. Assume the subtree height is h1. This means we visited node. By adding the nodes above the subtree which we visited during executing the string for the first time the total number of visited nodes will be . Now let's go to the other subtree. Obviously we don't need any other nodes except this subtree. So let's do the same we did to the original tree to this subtree. Execute the algorithm until we reach a leaf node, get the LCA, add to the solution where h2 is the height of the subtree of the LCA node where the leaf node exists. And so on we keep applying the rules until after executing the algorithm we will reach the exit.

Also we can do the same operations in O(h) by beginning to move from the root, if the exit is located to the left we go to the left and ans++ and then set the next command to 'R' else if it is located to the right we will visited the whole left subtree so we add the left subtree nodes to the answer and then set the next command to 'L' and so on.

Time complexity: or

Challenge: What if the pattern is given as an input (e.g. "LRRLLRRRLRLRLRR..."), How can this problem be solved?

Implementation: 9529181

507D - The Maths Lecture

Hint: Dynamic programming problem. To handle repetitions we have to construct the number from right to the left and calculate the answer when we reach a number equivalent to 0 modulo k.

Solution: Let's define as a recursive functions calculates the number of numbers consisting of n digits satisfying the conditions of the problem and with a specific suffix of length i Si such that .

We want to avoid repetition so by constructing the number from the right to the left when we reach a state with j = 0 with suffix  ≠ 0 we return the answer immediately so any other suffix that contains this suffix won't b calculated.

So the base cases are , .

So state transitions will be (We add a digit to the left).

And we can handle j = 0 case coming from a zero suffix easily with a boolean variable we set to true when we use a digit  ≠ 0 in constructing the number.

Time complexity:

Implementation: 9529210

507E - Breaking Good

Hint: Consider we've chosen a certain path with length d where d is the length of the shortest path from 1 to n and it has x edges that are working. Assume that y is the total number of edges that are working in the whole country. So we need to make d - x changes (to make the malfunctioning edges on the path work) and y - x changes (to blow up all other edges that don't lie on the path). So we will totally make d + y - 2 * x changes where d and y are constants. So the optimal solution will depend only on number of working edges along the path. So we'll have to maximize this number!

Solution: We will use dynamic programming on all nodes that lies on some shortest path. In other words, every node x that satisfies that the shortest path from 1 to x + the shortest path from x to n equals d where d is the length of the shortest path from 1 to n. Let's define Max[x] is the maximum number of working edges along some shortest path from 1 to x. We can calculate the value Max[x] for all nodes by dynamic programming by traversing the nodes in order of increasing shortest path from node 1. So at the end we'll make d + y - 2 * Max[n] changes. We can get them easily by retrieving the chosen optimal path.

Time complexity:

Implementation: 9529272

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

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

Problem C can be solved in O(h) aswell :D.

Here is my solution: 9530015

('D' means you are/ you want to go on the right son and 'S' means you are / you want to go on the left son)

»
4 years ago, # |
  Vote: I like it -13 Vote: I do not like it

507C done in O(h) and challenge part can also be done in O(h) using the similar logic my Solution 9530023

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

    How can you solve the challenge part in O(h) ? According to problem rules if we skip two consecutive commands we move to parent node. For example if the left node is traversed and current input comes out to be LL then we wont move to right node but to parent of current node.

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

      here is my solution in O(h): http://codeforces.com/contest/507/submission/9524186

      Algorithm in problem looks like DFS, but in DFS you always search in the left subtree, then in the right. In DFS you'll visit leafs in the following order: 1, 2, 3, ... , 2 ^ h

      Here you'll visit leafs in different order.

      So you only need to understand how to calculate this bijection in O(h).

      And then you can simply calculate the answer.

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

        Yeah i get. I too did it that way. Solution

        I was asking for the challenge part of Problem 507C which i think is removed from the post now.

        Challenge: What if the string is given as an input (e.g. "LRRLLRRRLRLRLRR..."), Can this problem still be solved in O(h2)?

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

          You can see my comment where I explain my algorithm to solve the problem. Taking L analogous to 0 and R analogous to 1 we can convert to given input string to "011001110101011..." That means the leaf which is ("011001110101011...")in base two, will be the first node to be visited and in any place where the pattern does not match, we would add 2^(h-i) for each iteration so as to mark the nodes as visited (i being the index from the left side of the binary string). This would help us to solve the problem in O(h) time.

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

        I guess this solves the proposed more general problem too. Can you explain how to compute the bijection in O(h)?

»
4 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Got a O(h) solution for C. Solution for B is interesting, I didn't figure it out. Nice round!

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

Thanks a lot... I have find my solution.

»
4 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Problem E could be also solved with a bfs to mark the level of each node, and a dijkstra from node n to node 1, following the bfs tree, with cost of edges 0 or 1. It's time complexity is O(|E| * log |E|), but it's still good enough.

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

    Why so much negative votes? It is just how I've solved it :/

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

    Yes, really, why so much negative votes? It's a good solution I believe.

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

An interesting round... though I nearly solved E...:P (but failed in the end...T T)

»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Finally blue :) Yay!

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

Has someone tried to solve problem C "backwards"? As in generating it's path back to the root? Couldn't you calculate the answer as move up to the root summing up the size of subtree rooted at it's sibling (in case it's sibling happens to be visited first with the given traversal in the problem statement)? Also, is valid to consider that it's sibling is visited first only if the actual node we're currently on has the same parity (odd or even) as it's father (if you label them from 1 to 2^h+1 from left to right as you move to lower levels of the graph)?

I hope I made myself clear, any ideas are welcome.

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Problem C can be solved in O(h) time. This was a really good question and my approach is stated below. The problem first requires you to convert (n-1) to its binary form (we took n-1 since we want to number the leaf nodes starting from 0). Next we observe that the binary conversion of (n-1) gives you the location of the node from the parent tree . Example if h=3 and n=6 we want to reach the leaf numbered 5 (taking 0 as the starting first leaf).

Converting 5 to its binary form, we get 101 What the number 101 tells us is that we reach this node by taking the path R-L-R. We then observe that the first element tells us if we have to take a right. But according to the pattern given we must traverse the left side of the tree. This would consist of (2^h)-1 (number of nodes on the left part of the parent node) nodes and 1 node (the parent itself). So in the first step we add 2^h to the number of nodes visited.

Now, we look at the next bit. In the previous step, since we already took a right we should take a left according to the guessing pattern given in the question. Even in the RLR pattern we observe for the number 5, we have to take a L so we mark the present node is visited by adding only 1 this time. This process continues till you reach the leaf of the tree.

To get a better understanding you can see my code in the link shown(I have written the necessary comments to help make it easier to read my code) http://codeforces.com/contest/507/submission/9531335

Now answering the challenge question to C if we want to solve the question for "LRRLLRRRLRLRLRR..." We repeat the process by converting n-1 to its binary form and proceed with the above algorithm by taking the new string into consideration. A pointer to the present index of the string would suffice. Thus, we can solve the challenge question in O(h) time as well.

»
4 years ago, # |
Rev. 6   Vote: I like it +14 Vote: I do not like it

Green again :-)

O(h) Gentle solution of С using bit manipulation in Java:

    public void solve(int testNumber, InputReader in, PrintWriter out) {
        int h = in.nextInt();
        long n = in.nextLong() - 1;
        long res = 0;
        for(int i = h - 1; 1; i >= 0; i--) {
            if ((n >> i & 1L) == 1) {
                res += 1L << i + 1;
            } else {
                res += 1;
                n = ~n; //inversion
            }
        }
        out.println(res);
    }
»
4 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In problem E: how can we find the shortest path from 1 to x and the shortest path from x to n in time?

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

For problem E, I have another solution.

  • Initially, let k be the number of usable roads, hence the ones we must destroy if we don't use it.
  • Consider any path from 1 to N. If we use a usable road, we must subtract 1 from k, since we won't need to destroy it. If we use a broken road, we need to add 1 to k, since we'll need to repair it.
  • We can solve it with Dijkstra. But we have the problem that we also want a path with minimum number of edges, so we can simply assign a cost of 105 + 1 to each edge, that way we'll make sure that the shortest path Dijkstra finds will be one with the shortest number of edges. Additionally, using a broken road will cost 105 + 2 while using a usable road will cost 105. That way, in case of a tie in number of roads, the path where the minimum number of roads have to be demolished in the end will prevail.

My solution: 9530019

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

    I also solved it by this way =)

    Here is my solution: 9533709

    P.S I think that this problem E is much easier than "usual" problem E on CF.

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

can any one tell me what is wrong with my solution to problem D ??

http://codeforces.com/contest/507/submission/9533089

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

I didn't understand the idea for problem D. How did you come up with such solution? I have an idea for the problem though it didn't produce the right answer right from test #3. Let's define dp[i] the number of suffixes y with length i such that and there is no true suffixes of y that divides k. Also we define cal[i][j] as suffixes y' with length i and . Also all suffixes y' have no suffix that divides k.

First we calculate cal[1][j] by trying out all numbers from 1 to 9. Then set dp[1] as cal[1][0] and we set the base value cal[i][0] = 1 (0 only). Then, for general i, j we shall have

(P[i][j] = number of indicies of )

Therefore the answer will be

Of course, all of them would be modded by m when actually coded. Please correct me if i'm wrong. Thank you all!

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

    I don't understand your transition for cal[i][j]. Why don't you calculate cal[i + 1][...] from cal[i][...]? It seems easier to me. You set the first digit for the i + 1 digit number (from 0 to 9), the current modulo (which must be bigger than 0 so that we don't count suffixes more than once) and calculate the resulting modulo. Something like this...

    for(int j = 1; j < K; j++)
      for(int d = 0; d <= 9; d++)
      {
            long long modulo = (pow(10,i)*d + j) % K;
            DP[i+1][modulo] += DP[i][j];
            DP[i+1][modulo] %= M;
      }
    
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I understand pow(10,i)*d is to set the 1st digit num, but what if j>=pow(10,i)*d or at least they have the same digit? Besides, can you explain a little bit why suffixes are counted more than once if modulo==0?

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

        It doesn't matter because in that case DP[i][j] would be 0, so it won't alter the answer.

        We'll be counting suffixes more than once if j = 0 in that code above, because we'll potentially be using the suffixes of the current length to build future longer suffixes. For example, consider K = 3 and the suffix 36, which is a multiple of K. If we set 4 to be the first digit of the next suffix (j = 0, d = 4 in the code above), we will get a number which is modulo 1 (436). If we then use this modulo 1 number to build a 4-digit number with 5 as the first digit (j = 1, d = 5 in the code above), we will get number 5436, that is modulo 0 but contains 36 as a suffix, which we already counted earlier. That's why we only consider j in the range [1, 9] in our code.

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

      Thank you OwO ~~ . Yes after some thinking I finally found out that my solution is really really weirdly and complicatedly implemented >_> . Still I have a lot to learn 3.3~~ Also, isn't it better for us to pre-calculate all pow(10,i)s instead of putting it straight into code @.@ ?

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

    It seems you can not is considered that y > 0.

    And optimization: cal[i][j] = sum x = 0..9 cal[i - 1][(j - x * 10 ^ (i - 1)) mod k] better that cal[i][j] = sum l=0..k-1 p[i][l] * cal[i - 1][(j - l) mod k] (first O(10), second O(k))

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

      The y > 0 condition is calculated by setting all cal[i][0] = 1 (we only allow solutions x00000..0 to exist). All others we ignored by not applying the j = 0 calculation into cal[i][j] calculations. There should be no problems with that `~` And yes, thanks for your optimization!!~~

»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Why count(n,0) = 1 in 507D? There are more than 1 n-digit number divisible by k aren't there?

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

    yeah i totally agree, count(n,0) is not always equals to 1

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

    "for every certain suffix"

    This is he answer for every unique suffix with length n as I'm calculating the answer recursively from the right to the left.

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

      I did not understand how you derived your state transitions and how it does not count sub-problems more than once. Also what exactly is the deal with j = 0 and the boolean variable? Kindly elaborate!

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

        I've enhanced the editorial for D. If you have any problems kindly ask.

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

          Thanks! I gained a little more insight but still have one doubt. How do we compute the final answer using the notations you have given?

          If count(i, j) gives us the number of numbers of length n such that a suffix of length i leaves remainder j, then according to me the answer should be summation over count(i, 0) where i varies from 1 to n.

          But you say that count(n, 0) = 1 "for every certain suffix". What does that mean? From the notation given, I am interpreting that if k = 1, then for count(n, 0) the answer should be 9 * 10^(n-1) and not 1 like you say.

          Kindly resolve my mistake :)

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

            The answer will be count (0, 0) :)

            As I said the function counts only the result of the digits that is located to the left of i as we are constructing the number from the right to the left.

            Consider a case where the number generated so far is 12345 where n = 10 function count (5, 12345 % k) will count the number of combinations XXXXX12345 that satisfies the problem's conditions.

            So by default a number like 1234512345 if it's equivalent to zero modulo k then count (10, 0) will be 1 an there is only one combination of the number.

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

              Got it! Thanks a ton! Btw is there any iterative approach as well?

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

                Yes!

                We can easily convert the approach into an iterative one:

                // handle base cases
                for(int i = 1;i <= n;i++)
                  for(int j = 1;j < k-1;j++)
                     for(int x = 0;x < 10;x++)
                      count[i+1][(j+(x*10^i))%k]+=count[i][j]
                

                And the answer will be

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

                  Thanks!!!

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

                  Won't there be repetitions?

                  Because, count[i][0] is actually measuring the number of suffixes of length i which are divisible by k, and we are adding all possible numbers before it, so it would also include any number with suffixes greater than size i, say j. And, because we add number with suffixes of length j also, same number would be included multiple times.

                  For Example, for n = 2 and k = 3,

                  33 would be included for two times.

                  One time in 9 * count[1][0], Second time in count[n=2][0].

                  Please let me know where am I wrong.

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

                  Note that in the second loop j is starting from 1 so that we will not count the case where the suffix equals zero.

                  So count[2][0] won't have count[1][0] in it.

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

                  Thanks! That clears!

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

                  Why doesn't the middle loop run until j<=(k-1) ?

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

                  I think my approach is the same iterative idea...can someone tell me why it does not give correct answer :(

                  9909747

                  Edited: nvm...I found the problem..! :)

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

The one problem that i face is that i am unable to calculate the square root of the number in gcc(compiler). math.h file contain the function but math.h cannot be linked to code. how to resolve that problem i want to look at the solution which are submitted by the other in c.

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

    when you are running add the -lm flag on your compile command e.g. gcc -o exe filename -lm

    I think CF runs its compilers with the flag , even if not math.h links properly

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I didnt understand the purpose of binary search in 507-B solution link provided in editorial...can anyone please explain...as suggested in editorial, we could have simply got the answer by ceil(dist/2*R).

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

    binary search is to find optimal number of moves, in each iteration it tries some value x as number of moves and checks whether the distance is covered or not and tries to find minimal x that covers the distance.

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

    It's to avoid precision errors.

    If the limits were up to 109 even solutions that used double datatype would fail.

»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

can anyone elaborate on the solution of problem D-the maths lecture...

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

Here's really simple solution for problem C: http://codeforces.com/contest/507/submission/9522115 (in O(h))

»
4 years ago, # |
  Vote: I like it -12 Vote: I do not like it

very bad round the problems were easycoding and not interesting

»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

In problem E — we actually don't need to know whether some node lies on shortest path or not; there are also different possible solutions with Dijkstra's algorithm described in comments, but you also don't need it. Solution with a single BFS sounds simpler.

Here is the idea — you can calculate values of dynamic programming right inside this bfs. If you'll store number of bad edges in shortest path to given vertex, along with length of this path — you will have answer for a problem after running single bfs from vertex 1 to vertex n.

My solution 9516327 from a contest works this way.

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

    Actually I had a solution combining both bfs and DP but in O(m log m) using a priority queue but your solution looks simpler. :)

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

Nice :)) thanks a lot:))

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

I think the complexity of problem D is O(n*k*10)

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

What's the use of boolean change in 9529210 (D-Maths Lecture). I think it's used just to check that do we have atleast one non-zero number in the suffix so far?.

Also the condition if(ind == n || (rem == 0 && change)) return 0; can be if(ind == n) return 0;. because if (rem==0&&change) is true we must have already return-ed from above.

Can I categorize it as Digit-DP?

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

I have difficulty comprehending


We want to avoid repetition so by constructing the number from the right to the left when we reach a state with j = 0 with suffix  ≠ 0 we return the answer immediately so any other suffix that contains this suffix won't b calculated.

Can someone explain to me what this means?

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

    a detailed example of the construction process would be very appreciate.

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

can someone good man explain me problem D more detail? i mean to tell me clear dp state

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

507E Use 2 BFS one from 1 and other from n,mark the valid vertices then use 0-1 BFS.