caustique's blog

By caustique, 10 years ago, translation, In English

349A - Cinema Line

In the problem you need to decide whether cashier can give a change to all customers if the price of the ticket is 25 rubles and there's 3 kinds of bills: 25, 50 and 100 rubles. There's no money in the ticket office in the beginning.

Let's consider 3 cases.

  • Customer has 25 rubles hence he doesn't need a change.
  • Customer has 50 rubles hence we have to give him 25 rubles back.
  • Customer has 100 rubles hence we need to give him 75 rubles back. It can be done in 2 ways. 75=25+50 и 75=25+25+25. Notice that it's always worth to try 25+50 first and then 25+25+25. It's true because bills of 25 rubles can be used both to give change for 50 and 100 rubles and bills of 50 rubles can be used only to give change for 100 rubles so we need to save as much 25 ruble bills as possible.

The solution is to keep track of the number of 25 and 50 ruble bills and act greedily when giving change to 100 rubles — try 25+50 first and then 25+25+25.

349B - Color the Fence

In the problem you're asked to write the largest possible number given number of paint that you have and number of paint that you need to write each digit.

Longer number means larger number so it's worth to write the longest possible number. Because of that we choose the largest digit among those that require the least number of paint. Let the number of paint for that digit d be equal to x, and we have v liters of paint total. Then we can write number of the length .

Now we know the length of the number, let it be len. Write down temporary result – string of length len, consisting of digits d. We have supply of vlen·x liters of paint. In order to enhance the answer, we can try to update the number from the beginning and swap each digit with the maximal possible. It's true because numbers of the equal length are compared in the highest digits first. Among digits that are greater than current we choose one that we have enough paint for and then update answer and current number of paint.

If the length of the answer is 0 then you need to output -1.

348A - Mafia

In the problem you need to find out how many games you need to play in order to make all people happy. It means that each of them played as many games as he wanted.

Let the answer be x games. Notice that max(a1, a2, …, an) ≤ x. Then i-th player can be game supervisor in xai games. If we sum up we get — it's the number of games in which players are ready to be supervisor. This number must be greater or equal to x — our answer.







Don't forget about that condition: max(a1, a2, …, an) ≤ x.

348B - Apple Tree

In the problem you need to find out minimal number of apples that you need to remove in order to make tree balanced.

Notice, that if we know the value in the root then we know values in all other vertices. The value in the leaf is equal to the value in the root divided to the product of the powers of all vertices on the path between root and leaf.

For every vertex let's calculate di — minimal number in that vertex (not zero) in order to make tree balanced. For leaves di = 1, for all other vertices di is equal to k·lcm(dj1, dj2, ..., djk), where j1, j2, ..., jk — sons of the vertex i. Let's calculate si — sum in the subtree of the vertex i. All that can be done using one depth first search from the root of the tree.

Using second depth first search one can calculate for every vertex maximal number that we can write in it and satisfty all conditions. More precisely, given vertex i and k of its sons j1, j2, ..., jk. Then if m = min(sj1, sj2, ..., sjk) and — minimal number, that we can write to the sons of vertex i, then it's worth to write numbers to the sons of vertex i. Remains we add to the answer.

348C - Subset Sums

This problem is about data structures.

First step of the solution is to divide sets to heavy and light. Light ones are those that contains less than elements. All other sets are heavy.

Key observation is that every light set contains less than elements and number of heavy sets doesn't exceed because we have upper bound for sum of the sizes of all sets.

In order to effectively answer queries, for every set (both light and heavy) we calculate size of the intersection of this set and each heavy set. It can be done with time and memory . For every heavy set we create boolean array of size O(n). In i-th cell of this array we store how many elements i in given set. Then for each element and each heavy set we can check for O(1) time whether element is in the set.

Now let's consider 4 possible cases:

  • Add to the light set. Traverse all numbers in the set and add the value from the query to each of them. Then traverse all heavy sets and add (size of intersection * the value from the query). Time is .

  • Add to the heavy set. Just update the counter for the heavy set. Time is O(1).

  • Answer to the query for the light set. Traverse all numbers in the set and add values to the answer. Then traverse all heavy sets and add to the answer (answer for this heavy set * size of intersection with the set in the query). Time is .

  • Answer to the query for the heavy set. Take already calculated answer, then traverse all heavy sets and add (answer for this heavy set * size of intersection with the set in the query). Time is .

We have O(n) queries so total time is .

348D - Turtles

In the problem you're asked to find the number of pairs of non-intersecting paths between left upper and right lower corners of the grid. You can use following lemma for that. Thanks to rng_58 for the link. More precisely, considering our problem, this lemma states that given sets of initial A = {a1, a2} and final B = {b1, b2} points, the answer is equal to the following determinant:

where f(x, y) — is equal to the number of paths from point x to point y. You can calculate this function using dynamic programming.

Finally we need to decide what sets of initial and final points we choose. You can take A = {(0, 1), (1, 0)} and B = {(n - 2, m - 1), (n - 1, m - 2)} in order to make paths non-intersecting even in 2 points.

348E - Pilgrims

Let’s build a simple solution at first and then we will try to improve it to solve problem more effectively given the constraints.

For every vertex let’s find the list of the farthest vertices. Let’s find vertices on the intersection of the paths between current vertex and each vertex from the list that don’t contain monasteries. If we remove any of these vertices then every vertex from the list is unreachable from the current monastery. For every vertex from the intersection increment the counter. Then the answer for the problem is the maximum among all counters and the number of such maxima.

Let’s solve the problem more effectively using the same idea. Let’s make the tree with root. For every vertex we will find the list of the farthest vertices only in the subtree. While traversing the tree using depth first search we return the largest depth in the subtree and the number of the vertex where it was reached. Among all of the sons of the current vertex we choose the maximum of depths. If maximum is reached one time then we return the same answer that was returned from the son. If the answer was reached more than one time then we return the number of the current vertex. Essentially, we find LCA of the farthest vertices according to the current vertex. Before quitting the vertex we increment the values on the segment between current vertex and found LCA. One can use Eulerian tour and segment tree for adding on the segment.

Finally, the last stage of solving the problem – to solve it for the case when the farthest vertex is not in the subtree of the current vertex. For solving of that subproblem we use the same idea that was used in the problem of the finding the maximal path in the tree. For every vertex we keep 3 maximums – 3 farthest vertices in the subtree. When we go down to the subtree, we pass 2 remaining maximums too. In that way, when we’re in any vertex, we can decide whether there’s a path not in the subtree (it means, going up) of the same or larger length. If there’re 2 paths of the same length in the subtree and not in the subtree, it means that for the pilgrim from the current monastery there’s always a path no matter what town was destroyed. If one of the quantities is larger then we choose the segment in Eulerian tour and increment the value on the segment. The case where there’s several paths (at least 2) out of the subtree of the same maximal length, is the same with the case in the subtree.

LCA and segment tree can be solved effectively in O(logN) time per query so the total memory and time is O(NlogN).

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

| Write comment?
»
10 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Very nice idea for problem D. :) It's actually possible to solve problem E in O(n) time. LCA is not necessary, the "counting" process can be done by two dfs, first count the occurences of nodes in the "going up" part of paths, then count the occurences of nodes in the "going down" parts. You may see my solution for detail..

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

There's actually no need to use binary search in problem C, when finding intersections of sets. A brute-force implementation consumes only time.

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

    I still don't get how it's done. There are intersections to calculate, and each one takes n time..

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

      For each element of each set see if it's contained in each big set (storing big sets in boolean arrays). There are N elements in total and big sets, so it's time and space.

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

        Ah, that's a nice way to analyze it. And if we use binary search instead of boolean array, it'll be n*sqrtn*logn. But then I don't get the n*sqrtn "brute force" approach.

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

          I guess huzecong meant boolean arrays for big sets.

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

          Sorry for not being clear, but a boolean array was what I meant... I thought that compared to the binary search approach this one seems pretty "brute-force"...

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

            In the editorial we defined heavy sets to be those which contained elements. Denoting , we have atmost heavy sets. If we go through each element of each set (X of those) and check if its contained in every heavy set ( of those), we have a complexity of which is out of limits. Am I missing anything?

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

              According to problem statement, It is guaranteed that the sum of sizes of all sets Sk doesn't exceed 10^5. Naive solution works in (10^5)*(10^5)/sqrt(10^5), it is just few hundred millions of operations.

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

                X ≤ 105, but with small n (like 4), which is TLE? In the editorial is X = n ?

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

                  If you'll take heavy_size>=sqrt(X) — it will be ok, right? :)

                  I am not sure, but it looks like you are right, taking heavy_size>=sqrt(n) is bad idea.

                  But it will pass system tests) It do not proves that this solution is OK, it just shows us that tests are very weak. Take a look at 7288633, TsunamiNoLetGo has array for heavy sets of size 320 only, and heavy_size>=sqrt(n). It is easy to constuct testcase with 100000 heavy sets — just take n=1, m=100000, and all sets of size 1. But this solution passed, therefore i guess that such cases are missed in testdata.

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

                  Yes thats exactly what I meant. Setting heavy_size >= sqrt(X) is okay with me. SealView also told me that in the messages. He advises to set it to a constant (like 300). Thanks for looking into my problem. :D

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

in problem Apple trees can somebody explain the idea of finding intersections of sets using binary search

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

    I think, you're talking about "Subset sums" problem.

    Sort all lists. Iterate over one set and check whether element from this set is in another set. You can do it using binary_search() function from STL.

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

      no apple trees 348B

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

        There is no binary search and no sets in 348B.

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

I get a memory limit on problem Apple Tree. here is my submission : http://codeforces.com/contest/348/submission/4630566 Anybody knows why ?

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

    The leaf of the Apple Tree can be 0. So lcm can be zero.

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

Can someone explain 348A — Mafia with more details, please? :|

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

    Let's say you're going to play x games. If someone wanted to play more than x games, he wouldn't be able to do so, so he would be unhappy. Therefore, if everyone is happy, x ≥ ai must hold for each i, so

    x ≥ max(a1, a2, ..., an)

    Let $b_i$ be number of games, where i-th player is supervisor and let ci be number of games, where he plays. In each game i-th player is playing, XOR supervising, so ci + bi = x. Also, he wants to play at least ai games, so ai ≤ ci, thus bi ≤ ci + bi - ai, so bi ≤ x - ai.

    Each game is supervised by one player, so x = b1 + b2 + ... + bn. Giving it all together:

    x = b1 + b2 + ... + bn ≤ (x - a1) + (x - a2) + ... + (x - an)

    Now we have two lower bounds for $x$ . Smallest x satisfying both of them is

    This number of games is enough, because if first $x - a_1$ games are supervised by first player, next x - a2 games are supervised by second player etc., until the x-th game, then everyone plays enough games and each game is supervised by someone.

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

In 348A-Mafia, How does this condition ensures that the value of 'x' found is minimum?

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

    We simple do the binary search. Because of the principle of the binary search. We wouldn't be able to decrease x lower that lower bound in binary search(we checked the lower bound and found it impossible to fulfill the conditions by making only "lower bound" number games), similar for upper bound.

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

    read discrete binary search from topcoder...you will understand

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

can some one explain following line from apple tree editorial. Line : The value in the leaf is equal to the value in the root divided to the product of the powers of all vertices on the path between root and leaf. how this come ?

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

    value in a node = weight of a node.
    power of a node = number of children of a node.
    Let the value in the parent be X and power of it be K. Then value in each of its children will be X/K, as values of each children needs to be equal. Example:
    A is the root and D is a leaf.
    A (weight:X, power:3) --> B (weight:X/3, power:2) --> C (weight:X/(3*2), power:3) --> D (weight:X/(3*2*3)).

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

In Div. 1 Problem B, I didn't understand the idea behind d[i]. Why are we taking the lcm of all the children of the i'th vertex? What is the logic behind the solution. Could someone please help me out and elaborate?

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

Can someone provide a more detailed explanation for Div1 B ??

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

I don't know why does my solution for Div1B gets TLE... Can somebody help and take a look at it? Thanks in advance.

http://codeforces.com/contest/348/submission/19399532

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

Actually , We can solve Problem 348A-Mafia in a simpler way. let S = Σ a(i) for all i , c(i) = number of rounds played by the ith person so far , S2 = Σ c(i) for all i.

Then S2 is the Summation of the number of rounds played by each person so far. Actually , we need the number of Rounds X Which will make S2 >= S holds.

You Can Notice that after X Rounds , S2 Will be Equal to X*N — X , Were N is the number of People. Because simply , After each Round S2 will be incremented by the number of People -1 because all of them will play except one will be the supervisor.

So we just need to Search using Binary Search on the value X which will make X*N — X >= S holds .

NOTE : X should be >= max (a(i)).

Here is the link for my code.

20368610

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

    Shouldn't we also need for all i (c[i]>=a[i]) after playing X rounds, & how does the condition S2>=S guarantees that

»
6 years ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

Problem B (div 2) has a tag of DP. how we can implement dp on this problem?

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

DIV 2 B has dp tag, but it's a greedy problem :/

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

Div1 B, when we are calculating d[i] we are not considering the children of other nodes of the same level ?? for example, if root has 2 children and one of them has 3 children and another one has 2 children then we need to have the lcm of both 3 and 2 which is 6. please help !!

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

Anudeep's Submission of Problem Div1 C https://codeforces.com/contest/348/submission/4596270

Close to editorial!!!

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

    We can use the DP solution below. The approach is simple known as reconstructing the solution where we keep storing the optimal path in terms of parent of the state and then when we want to print we backtrack on the parent array. https://codeforces.com/contest/349/submission/107398509

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

      Great code man. Really loved the code and idea behind it. Have you done similar problems before or is this the only problem you have ever encountered with this type of logic?