435A - Очередь на остановке
Эта задача решается за один проход по всем группам. Решение можно представить следующим кодом:
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 - Паша максимизирует
Эта задача решается жадно. Будем стараться максимальные цифры ставить как можно раньше. Алгоритм можно описать так:
1) Рассмотрим каждую позицию по очереди, начиная с 1, пусть текущая позиция i
2) Среди следующих k цифр числа найдем ближайшую максимальную, пусть она находится на позиции j
3) Если эта цифра больше текущей цифры на позиции i, то сделаем серию обменов, поставим ее на позицию i, одновременно умешьшим величину k, то есть выполним k = k - (j - i)
435C - Кардиограмма
Эта задача носила технический характер, нужно было реализовать описанное в условии. Для начала нужно было посчитать координаты всех точек ломанной. Также заведем матрицу для хранения ответа. Поскольку координата y могла становиться отрицательной, удобно было удвоить размеры матрицы и изначально сдвинуть картинку вверх на 1000. В конце нужно будет вывести ее без лишних пустых строк.
Чтобы нарисовать саму кардиограмму, можно было рассмотреть каждую пару последовательных точек ломанной и отдельно расставить символы в матрице ответа. Если ломаная возрастает, нужно нарисовать прямой слеш, иначе обратный. Чтобы лучше разобраться как это сделать, можно аккуратно нарисовать первый тестовый пример на листочке, отметить координаты и понять как изменяются значения по координатам (какие границы получаются у циклов в программе).
435D - Специальная сетка
Так как ограничения на n и m были не очень большие, должно было проходить решение за O(max(n, m)3), то есть перебор всех треугольников. А именно, нужно было перебрать все треугольники и проверить для каждого треугольника за O(1), что он удовлетворяет всем описанным условиям.
Чтобы быстро выполнять проверку, нужно было для всех диагоналей, строк и столбцов сохранить массив частичных сумм. И далее, проверять запросом на сумму, лежит ли в данном отрезке на соответствующей линии хотя бы одна черная точка.
Полезные соображения, помогающие значительно сократить реализацию описанного выше:
- все треугольники, которые нужно посчитать — равнобедренные прямоугольные треугольники;
- либо катеты треугольника параллельны сторонам сетки, либо гипотенуза параллельна одной из сторон сетки;
- если научиться решать задачу, считая, что нужно посчитать количество треугольников только двух видов, то решение для всех треугольников можно получить, посчитав ответы для 4-х поворотов матрицы.
435E - Специальный граф
Для того, чтобы решить последнюю задачу, нужно было порисовать различные раскраски на листочке бумаги. Далее путем исследований установить, что бывает два вида корректных раскрасок: вертикальные и горизонтальные.
Вертикальные раскраски выглядят следующим образом:
acbcbd...
bdadac...
acbcbd...
bdadac...
acbcbd...
bdadac...
......
Другими словами, каждая вертикаль содержит только два цвета, вертикали одной четности содержат одинаковые цвета. При этом очередность цветов на каждой вертикали может быть совершенно произвольная.
Горизонтальные раскраски выглядят аналогично, только повернуты на 90 градусов. Конечно, бывают раскраски, которые одновременно и горизонтальные и вертикальные, но для решения задачи, это не имеет никакого значения.
Давайте научимся проверять, существует или нет, корректная вертикальная раскраска, удовлетворяющая шаблону заданному во входных данных. Это достаточно просто. Достаточно просто перебрать, какие цвета и на каких вертикалях находятся. А затем проверить, что такую раскраску действительно можно составить.
Аналогично нужно проверить для горизонтальных раскрасок.
Сложность решения O(n × m).
Why greedy algorithm can solve Problem B? Anyone proved 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.
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
. whereY > 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
, andX > 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.
Странно, что так мало человек решили D, вроде бы не сложная задача. Хотя я сам не решил :)
Там просто надо всё аккуратно написать.
Waiting for the "soon"s :p
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????????????????
You can't divide the groups, they must stay on the same bus.
1st group — a[1], a[2];
2nd — a[3];
3rd — d[4];
4th — a[5];
5th — a[6];
And what is your distribution?
Подскажите пожалуйста, что такое массив частичных сумм в задаче D? И как делать поворот матрицы, просто составлять новый двумерный массив?
Допустим, у тебя есть линейный массив, и тебе в задаче нужно быстро вычислять сумму чисел с индексами с L по R. Ты просто в элементе a[i] хранишь сумму элементов с 1 по i, а потом, чтобы найти сумму от L до R, ты берёшь ответ a[r] — a[l — 1]. Маленький код:
в этой задаче составить частичные суммы для строк, столбцов и двух диагоналей таким образом.
а насчёт поворота матрицы: можно завести другой массив, а можно просто представить, что строки -- столбы и наоборот. всего 4 случая.
Can somebody explain something to me, please: wrong answer 1st lines differ — expected: ' /\ ', found: ' /\ ' What is wrong with this?
The difference must be in the number of spaces before and after
you printed extra character on each line. I edited your code and got AC.
Thank you very much for your help. I really appreciate 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?
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.
@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..
check your solution here.
And check what it says on test 4. It indicates that you didn't output extra spaces.
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
Congratulation!
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.
Подскажите, пожалуйста. Как ускорить вывод?
Код (Паскаль)
на Delphi твоё решение зашло 6755792
Спасибо. Удалось найти причину TL: посимвольный вывод. После замены вывода на построчный, решение проходит.
D-(DIV 2) I am not able to find 20 valid triangles for this case. please help me out
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)
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?
Your Solution gives wrong result. It gives 9990 on my codeblocks also.
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. :)
at first group 1 and 2 goes along in a bus..then rest of the groups go on individually