HolkinPV's blog

By HolkinPV, 11 years ago, translation, In English

260A - Adding Digits

At first try to add to the right one digit from 0 to 9. If it is impossible write -1. In other case, the remaining n–1 digits can be 0 because divisibility doesn’t change.

260B - Ancient Prophesy

In this problem you have to consider every date from 2013 to 2015 year (there is no leap years in this interval), count occurrences of this date and find maximum. In one year there is 365 days, so the complexity of the solution (3·365·N).

260C - Balls and Boxes

Firstly describe simple solution. We will get by one ball from boxes (we begin from box x) from right to left (action back). At some moment there will be 0 balls in current box. This box is the first box in our initial problem (from which we took all balls and begun to put). In this box we put all balls, which we get from all boxes.

But we can’t solve the problem in such a way, because it is too long. Note, that before we meet the situation when in some box will be 0 balls, we will go through every element of array several times and subtract 1. So we can make our solution faster. We can subtract from every element of array minv - 1, where minv — minimum in array. After that you should do O(N) operations, that were mentioned above.

260D - Black and White Tree

The problem can be solved constructively maintaining the following invariant (rule) — the sum of the white vertices equals to the sum of the black vertices. The tree is a bipartite graph, so we build bipartite graph with no cycles, which will satisfy the conditions of the problem. Parts of graph will be black and white vertices.

On each step we will choose vertex v with minimum sum from white and black vertices. Then find any vertex of opposite color u and add edge (u, v) with weight s[v], and subtract from sum of u sum of v, that is s[u] = s[u]–s[v]. After each step one vertex is deleted. That’s why there will be no cycles in constructed graph. When we delete last vertex of one of colors, all other vertices can be joined in any correct way with edges of weight 0.

260E - Dividing Kingdom

Consider 9! variants of location of integers a[i] on 9 areas. When we consider some location (some grid), we can easily find amount of cities to the left of the left vertical line, to the right of the right vertical line, below the lower horizontal line and above the upper horizontal line. All these numbers is sum of three values a[i].

We assume that the lines of the answer are always in half-integer coordinates. Then, knowing the above 4 numbers, we can uniquely determine separately for x and y how to accommodate all the 4 lines. It remains only to check that in all areas there is desired number of points.

For each of four zones (to the left of the left vertical line, to the right of the right vertical line, below the lower horizontal line and above the upper horizontal line) separately check, that all three areas have correct number of cities. It can be done offline using scan-line and segment-tree, which can find sum on interval and change value in some point. You should put all queries in some array, sort them and process from left to right. Note, when you check 8 from 9 areas for every 9! variants of location, the last area (central) could not be checked, it will be correct automatically.

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

| Write comment?
»
11 years ago, # |
Rev. 7   Vote: I like it -14 Vote: I do not like it

UPDATE : I apologize, please ignore this question. By mistake I saw my submission as correct answer and vice versa making me to raise such an awful question.

I am not able to understand this following test case for problem C. I applied the same algorithm in my code but failed for this following test case.

10 3
1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

In this test case, shouldn't the right answer be this :

0 0 10000000000 0 0 0 0 0 0 0 

as the '0' will be encountered on the third place for the first time and upto this time total balls we would be having in hand = 10^9 * 10, so we will put all the balls in hand in this box. But the correct answer for this is :

999999999 999999999 999999999 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 

How ?

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

    The correct answer is indeed:

    0 0 10000000000 0 0 0 0 0 0 0

    The third box is the one who passed the balls.

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

      My code returned the same answer but its not the correct answer. This is what has made my submission go wrong on pretest 4.

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

        Did you use a 64 bit integer?

        I already checked my submission and made sure that was the correct solution, and it is.

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

        I already checked your submission. Your program is the one outputing:

        999999999 999999999 999999999 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000

        (It's incorrect) :P

        In the evaluator, the "Output" is your program output, and "Answer" is the correct answer that is expected for that test case.

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

    I think you misunderstand what is written on the submission page.

    Your program's output is written under the 'Output'. The correct answer is written under 'Answer'.

    The answer for the 4th pretest is correct. You could simulate the process of moving balls manually to make sure.

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

In the problem B, test case 22: 31-12-201331-11-201331-11-2013

My answer is 31-11-2013, but it's wrong, the test case's answer is 31-12-2013 and that isn't right because 31-11-2013 appear twice.

Can somebody help me? PD: sorry for my english.

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

    11th month — November — has only 30 days. It means that 31-11-2013 is incorrect date.

    Statement: A date is correct if the year lies in the range from 2013 to 2015, the month is from 1 to 12, and the number of the day is strictly more than a zero and doesn't exceed the number of days in the current month.

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

In problem 260D — Black and White Tree, how can you prove that that algorithm will leave a connected tree?

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

    Because we add n - 1 edges and there are no cycles.

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

.

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

In problem — Black and White trees, its written that when we delete the last vertex of one of the colors, all other vertices can be joined together with edges of weight 0. Wouldn't this be a voilation as all other vertices remaining at this point will only be of single color and we would be connecting nodes of same color this way.

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

    Well you just add them to a vertex of the opposite colour. The author ment that after you have come up with such a sittuation you just have to connect them someway but you have completed the part with the weights. Thats why you should just connect them with weight 0 to a vertex with opposite colour

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

      Wouldn't it create a cycle then ?

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

        There is no Cycle. Every vertex has edges which connect to vertexes with the other color. It means two-partite graph. In two-partite graph never will be cycles. I think that my solution easy to understand.

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

          i am only talking about the case when there are no vertices left of one color but some vertices are left of other color. then how would you connect those vertices of same color since connecting them will voilate the rule above in statement ( i.e edge should connect nodes of only two DIFFERENT colors).

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

            Like I said, you dont connect them to a vertex of same colour. You just take any used vertex of opposite colour and connect all these which are unused to it like leaves in a tree. There will be no cycles because you will have just added leaves to a tree and the rule wont be violated because they are connected to a vertex of opposite color but not to each other.

            I think you cant understand how the constructed graph looks in that situation. Just imagine a tree and some vertexes which have to be connected as leaves to a vertex(which can also be a leaf) of opposite color. Since last vertex we used was opposite color and is a leaf, you can connect them to it, although you can connect them to a vertex which is not a leaf. I hope you were able to imagine this picture :) Have a nice New Year's Eve :)

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

A question about using pointers: Why the default value of a pointer is NULL when it is declared in global scope, but it is not NULL in the local scope(main scope)?

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

    This is not specific to pointers. In C/C++, a global variable is initialized to its default value implicitly, but local variables are not (their value is indeterminate until you assign something to them).

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

    Furthermore, another significant difference between global and local variables is that you can declare much more memory globally rather than locally.

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

thanks for your solution but I think for problem D there is a shorter solution

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

The solution to the problem A has an error, in case "3 131 2" and others similars the solution fail, because the output is "-1", but the answer is "393".

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

    No, it's correct. Note that a should be divisible by b after each operation, not only after all iterations.

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

      Its correct, but you add digits to a until a have at least the same digits that b, for example: 3 131 2

      3 is not divisible by 131, 39 is not divisible by 131, 393 is divisible by 131.

      If this case had been used in the test, many solutions fail.

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

        please read the problem statement carefully.

        One operation of lengthening a number means adding exactly one digit to the number (in the decimal notation) to the right provided that the resulting number is divisible by Vasya's number b.

        so you have a=3 what is the digit that if you add it to the right of a you get a number divisible by 131 ???

        clearly there is no digit nor 9 because 39 is not divisible by 131 so the correct answer for this testcase is -1

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

260C Balls and Boxes 3rd case input: 3 3 2 3 1 my output: 0 1 5 answer: 1 2 3 I got a Wrong Answer. but why? "If there are multiple correct solutions, you are allowed to print any of them." isn't it? i=3 0 1 5, 0 1 0, 1 1 0, 1 2 0, 1 2 1, 2 2 1, 2 3 1. it's another answer!

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

empty content

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

In first question if gave 4 150 10 then according to your algo it will -1 but actually it can be formed as 45000000000

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

    If we add one digit to 4 we cant get number divisible by 150. So, we cant do the first step.

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

      Thanks i was interpreting the question wrongly.

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

For problem D, how can we prove that the algorithm will print the most optimal set of edges? Is there a case where the only vertex left has a residual value?

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

my answer for test case 7 is wrong, i use my answer to build the test case and it produce the same, it should be accepted. Take a look at my code https://codeforces.com/contest/260/submission/52624959

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

I think the solution to the problem 260A is incorrect, as it gives -1 as output for the query

5 100 2.

Obviously, the answer is 500.

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

    You cannot add a digit to the right of 5 to make a number divisible by 100. According to the problem statement, this means the answer should be -1.