HolkinPV's blog

By HolkinPV, 10 years ago, translation, In English

435A - Queue on Bus Stop

The problem could be solved in one cycle by groups. The solution could be implemented in this way:

int result = 1;
int people = 0;

for(int i = 0; i < n; i++)
{
    if (people + a[i] <= m)
        people += a[i];
    else
    {
        result++;
        people = a[i];
    }
}

cout << result << endl;

435B - Pasha Maximizes

The problem could solved by greedy algorithm. We will try to pull maximum digits to the beginning. The algorithm could be described in this way:

1) Consider every position in the number from the first, assume that the current position is i
2) Find the nearest maximum digit from the next k digits of the number, assume that this digit is on position j
3) If this maximum digit is greater than current digit on position i, then make series of swaps, push this digit to position i, also decrease k, that is do k = k - (j - i)

435C - Cardiogram

This problem is technical, you should implement what is written in the statement. First, you need to calc coordinates of all points of the polyline. Also create matrix for the answer. Coordinate y could become negative, so it is useful to double the sizes of the matrix and move the picture up to 1000. In the end you should print the answer without unnecessary empty rows.

To paint the cardiogram you should consider every consecutive pair of points of the polyline and set characters in the answer matrix between them. If the polyline goes up then set slash, otherwise set backslash. To understand the solution better please paint the first test case on the paper, mark coordinates of the points and find what values to set in cycles in your program.

435D - Special Grid

Values n and m are not so large, so the solution with complexity O(max(n, m)3) should pass. It means that you should consider all triangles and check all conditions in O(1).

To make this check you should precalc arrays of partial sums on all diagonals, rows and columns. After that you could check, that there is no black nodes on the side using one sum-query.

Some hints about this problem and the implementation:

  • all correct triangles are isosceles right triangles;
  • either all legs or hypotenuse of the triangle is parallel to the sides of the grid;
  • if you know how to solve the problem for two types of the triangles, you can get the whole solution making 4 rotates of the matrix.

435E - Special Graph

To solve this problem you have to paint different correct colorings on the paper. After it you could observe that there are two types of them: vertical and horizontal.

Vertical colorings looks like this:

acbcbd...
bdadac...
acbcbd...
bdadac...
acbcbd...
bdadac...
......

In other words, each vertical has only two colors, odd verticals have equal colors, even verticals have two others. The order of the colors on every vertical could be arbitrary.

Horizontal colorings are the same, they are rotated by 90 degrees. Of course, there are both vertical and horizontal colorings, but it doesn't change the solution.

So, you should consider every type of described colorings and check them. That is, you could choose what colors are on the verticals or what colors are on horizontals and check that obtained coloring matches the given matrix.

The solution's complexity is O(n × m).

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

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

Why greedy algorithm can solve Problem B? Anyone proved it?

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

    A number is greater than another if it is lexicographically greater than the other. For position i (0, 1, ..) you want Number[i] to be as big as possible. That's why you want to look at the next i + 1...i + k and see if you can improve Number. If you can, you have spent at most k adjacent swaps. Example: 98765, k = 2. no way to make it better. 87965, k = 2: 98765 is a greater number: 89765, 1 adjacent swap 98765, 2 adjacent swaps.

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

    By the simple fact that: Y???????? > X???????? is guaranteed if Y > X regardless of the other digits in the number, where Y, X, and ? are digits from 0-9, and X != 0 and Y != 0.

    So, by traversing the number from leftmost position to the rightmost position, and placing the largest digit that exists to the right of that index you are in (including the index you are in), you are guaranteed to end having the largest possible number.

    The problem here, you don't have that luxury here, you have a limited number of swaps or shifts (which is k). So, the maximum amount of shifts, you can get is (k) .. so in order to find the largest digit on the right, it should be at most k shifts away.

    So far the greedy algorithm works, what if the largest digits is more than k shifts away, can it contradict the algorithm suggested.

    It's simple to prove it doesn't .. If you are in position D and have a digit Z, and the largest digit right of digits is Y at position I, where |D - I| > k. where Y > Z.

    So, the question is, is it better to move Y to position (I + K), or find an element X at position J where |D - J| <= k, and X > Z?

    Notice the new numbers are X * 10^D + G1 (don't care digits) & Z * 10^D + Y * 10^(I+K) + G2 (don't care digits) ..

    So, the largest number is X * 10^D + G1.

    And so on, with the next index, until you reach the end of the string, or you used all the k shifts you are allowed.

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

Waiting for the "soon"s :p

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

for problem queue on bus stop the answer for 6th test case is given as 5...how is it be 5?? test case: (n=6 m=4) 1 3 2 3 4 1 IS IT NOT 4????????????????

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

    You can't divide the groups, they must stay on the same bus.

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

    1st group — a[1], a[2];

    2nd — a[3];

    3rd — d[4];

    4th — a[5];

    5th — a[6];

    And what is your distribution?

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

Can somebody explain something to me, please: wrong answer 1st lines differ — expected: ' /\ ', found: ' /\ ' What is wrong with this?

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

    The difference must be in the number of spaces before and after

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

    you printed extra character on each line. I edited your code and got AC.

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

      Thank you very much for your help. I really appreciate it.

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

i continued to get WA in Q3 on pretest 4 but i got the exact same outputs as they had in their sample output files. was there anything unusual with space checking or a concept that i missed?

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

    The solution appends spaces on every line except the longest one so that each line has the same length. Seeing your last submission, I think that's what you are missing.

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

    @HldenoriS i did the changes to append each line in the pattern to 'pad' with spaces (after) till same as equal to the longest line. still its missing sumthng..

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

      check your solution here.

      And check what it says on test 4. It indicates that you didn't output extra spaces.

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

        well thnx so much. i figured it out. i was doing a mistake in the sort function. rectified it now :) thanx a lot for lookin in

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

My first C pretest passed in 249 div2. Congs to myself:) It turns out run time error when system testing, but after a little modification, I ACed it. Here shared my idea: find max value of |y(i) — y(k)|, this is simple, u just need to calc 0, a1, a1-a2, a1-a2+a3, ..., these are y seq. so you can figure it out. This value is actually the hight of the result image.

so we need to calc sum{a(i) | i = 0 -> n}, to get the width of the result image.

then find the peak line, draw left and right of the result image by this peak line. the peak line is related to max value of |y(i) — y(k)| if you think a while about it.

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

D-(DIV 2)  I am not able to find 20 valid triangles for this case. please help me out

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

    Assume the grid is as follows: X 1 2 3 4

    X 6 7 X 9 X are the bad nodes.

    A B C D X

    The triangles are:

    (1, 6, 7), (1, 2, 6), (1, 2, 7), (2, 6, 7), (2, 3, 7), (3, 4, 9), (6, A, B), (6, B, C), (6, 7, B), (6, 7, C), (7, B, C), (7, C, D)

    (1, 7, 3), (1, 7, B), (2, 6, C), (A, 6, C), (B, 7, D)

    (1, B, D), (2, A, C), (1, 3, B)

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

My submission for problem B(6896216) give me correct results in local,i.e. with 1990 1 it prints 9190, but when I submit it, it print different results, like 9990, how is it possible?

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

    Your Solution gives wrong result. It gives 9990 on my codeblocks also.

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

Hi! I have a question about problem A. I get WA on test: 6 4 1 3 2 3 4 1 My output is 4, and the correct output is 5. Why is that? Please answer. :)

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

    at first group 1 and 2 goes along in a bus..then rest of the groups go on individually