|
|
|
Проблема с TopCoder-а
|
|||
|---|---|---|---|
|
#18+
Вот проблема с TopCoder-a, я ее сделал. Но за такое можно свобоно оторвать мне руки. Как мне избежать такой вложоности if/for, как по другому написать чтоб было понятно и другим ? Проблема Problem Statement Sometimes when computer programs have a limited number of colors to use, they use a technique called dithering. Dithering is when you use a pattern made up of different colors such that when the colors are viewed together, they appear like another color. For example, you can use a checkerboard pattern of black and white pixels to achieve the illusion of gray. You are writing a program to determine how much of the screen is covered by a certain dithered color. Given a computer screen where each pixel has a certain color, and a list of all the solid colors that make up the dithered color, return the number of pixels on the screen that are used to make up the dithered color. Each pixel will be represented by a character in screen. Each character in screen and in dithered will be an uppercase letter ('A'-'Z') representing a color. Assume that any pixel which is a color contained in dithered is part of the dithered color. Definition Class: ImageDithering Method: count Parameters: String, String[] Returns: int Method signature: int count(String dithered, String[] screen) (be sure your method is public) Constraints - dithered will contain between 2 and 26 upper case letters ('A'-'Z'), inclusive. - There will be no repeated characters in dithered. - screen will have between 1 and 50 elements, inclusive. - Each element of screen will contain between 1 and 50 upper case letters ('A'-'Z'), inclusive. - All elements of screen will contain the same number of characters. Examples 0) "BW" {"AAAAAAAA", "ABWBWBWA", "AWBWBWBA", "ABWBWBWA", "AWBWBWBA", "AAAAAAAA"} Returns: 24 Here, our dithered color could consist of black (B) and white (W) pixels, composing a shade of gray. In the picture, there is a dithered gray square surrounded by another color (A). 1) "BW" {"BBBBBBBB", "BBWBWBWB", "BWBWBWBB", "BBWBWBWB", "BWBWBWBB", "BBBBBBBB"} Returns: 48 Here is the same picture, but with the outer color replaced with black pixels. Although in reality, the outer pixels do not form a dithered color, your algorithm should still assume they are part of the dithered pattern. 2) "ACEGIKMOQSUWY" {"ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWX", "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWX", "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWX", "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWX", "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWX", "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWX"} Returns: 150 A picture of vertical stripes, every other stripe is considered part of the dithered color. 3) "CA" {"BBBBBBB", "BBBBBBB", "BBBBBBB"} Returns: 0 The dithered color is not present. 4) "DCBA" {"ACBD"} Returns: 4 The order of the colors doesn't matter. This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved. Мой код Код: java 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32. 33. 34. 35. 36. 37. 38. 39. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.07.2013, 17:22:07 |
|
||
|
Проблема с TopCoder-а
|
|||
|---|---|---|---|
|
#18+
Вы бы начали с табуляции. А то косоглазие сторо будет от восьми пробелов на отступ. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.07.2013, 17:25:53 |
|
||
|
Проблема с TopCoder-а
|
|||
|---|---|---|---|
|
#18+
Табуляция нормальная но когда ставил код из эклипс тут по другому все выглядит, и какбудто нажимал 2 раза таб. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.07.2013, 17:29:37 |
|
||
|
Проблема с TopCoder-а
|
|||
|---|---|---|---|
|
#18+
VigooleТабуляция нормальная но когда ставил код из эклипс тут по другому все выглядит, и какбудто нажимал 2 раза таб. Ну, дык перенастройте на 4. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.07.2013, 17:41:50 |
|
||
|
Проблема с TopCoder-а
|
|||
|---|---|---|---|
|
#18+
Первые три блока - превалидация. Их лучше отделить от реализации логики. Код: java 1. 2. 3. 4. 5. 6. 7. else System.exit(1); - тоже сильный ход. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.07.2013, 17:44:56 |
|
||
|
Проблема с TopCoder-а
|
|||
|---|---|---|---|
|
#18+
переменная i не нужна. enhanced for loop будет проще. Переменная j хранит длину, а не индекс вводит читателя в заблуждение. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.07.2013, 17:55:04 |
|
||
|
Проблема с TopCoder-а
|
|||
|---|---|---|---|
|
#18+
BlazkowiczПервые три блока - превалидация. Их лучше отделить от реализации логики. Код: java 1. 2. 3. 4. 5. 6. 7. else System.exit(1); - тоже сильный ход. Поддерживаю. Аналогично меняется:, Код: java 1. 2. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.07.2013, 18:59:39 |
|
||
|
Проблема с TopCoder-а
|
|||
|---|---|---|---|
|
#18+
Blazkowiczelse System.exit(1); - тоже сильный ход. Недавно написал простую программку и выдавало какуюту ошибку в eclipse связано с JRE так нашол что можно обойти именно с этой команды. Табуляция по умолчанию настроена на 4 Спс за ответы ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.07.2013, 19:02:07 |
|
||
|
Проблема с TopCoder-а
|
|||
|---|---|---|---|
|
#18+
rfqАналогично меняется:, Код: java 1. 2. Забыл обратить булевы значения условий. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.07.2013, 19:02:19 |
|
||
|
Проблема с TopCoder-а
|
|||
|---|---|---|---|
|
#18+
VigooleТабуляция по умолчанию настроена на 4 Спс за ответы Это она в Эклипсе настроена на 4. В тексте ставится символ '\t', а здесь он считается за 8. Лучше избавьтесь от табуляций в тексте вообще, пишите одни пробелы - в Эклипсе есть такая опция. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.07.2013, 19:04:49 |
|
||
|
Проблема с TopCoder-а
|
|||
|---|---|---|---|
|
#18+
А еще лучше попытаться сначала найти правильное решение, и потом заниматься украшательствами. - судя по примеру №2 должны учитываться не только горизонтальные, но и вертикальные совпадения. Приведенное решение ищет только в строках - судя по примеру №3 учитываются "разреженные" совпадения вывод: Задача сформулирована небрежно, либо примеры неправильные. Подозреваю, что можно обобщить на диагонали и ломанные. Исходя из этого обобщения решение следующее: - весь массив свалить в кучу - убедиться что в этой куче есть все символы из шаблона (решается в один проход с помощью HashSet) - в этом же проходе выкинуть все лишние символы - посчитать результат ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.07.2013, 19:49:33 |
|
||
|
Проблема с TopCoder-а
|
|||
|---|---|---|---|
|
#18+
ivanraА еще лучше попытаться сначала найти правильное решение, и потом заниматься украшательствами. - судя по примеру №2 должны учитываться не только горизонтальные, но и вертикальные совпадения. Приведенное решение ищет только в строках - судя по примеру №3 учитываются "разреженные" совпадения вывод: Задача сформулирована небрежно , либо примеры неправильные. Подозреваю , что можно обобщить на диагонали и ломанные. Исходя из этого обобщения решение следующее: - весь массив свалить в кучу - убедиться что в этой куче есть все символы из шаблона (решается в один проход с помощью HashSet) - в этом же проходе выкинуть все лишние символы - посчитать результат Обратите внимания в проблеме одномерный масив строк ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.07.2013, 21:48:18 |
|
||
|
Проблема с TopCoder-а
|
|||
|---|---|---|---|
|
#18+
VigooleОбратите внимания в проблеме одномерный масив строк Problem в данном контексте - "задача", а не "проблема" ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.07.2013, 21:58:13 |
|
||
|
Проблема с TopCoder-а
|
|||
|---|---|---|---|
|
#18+
VigooleНедавно написал простую программку и выдавало какуюту ошибку в eclipse связано с JRE так нашол что можно обойти именно с этой команды. Т.е. "не знаю что было, не знаю зачем сделал, но есть как есть" ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.07.2013, 21:59:15 |
|
||
|
Проблема с TopCoder-а
|
|||
|---|---|---|---|
|
#18+
По оформлению: ограничения (constraints) обычно не проверяются, это то, что "дано", на вход подаются данные уже удовлетворяющие перечисленным условиям. Понятно, что лишняя проверка не повредит, но в общем случае это лишний код: Код: java 1. 2. 3. 4. Но если очень хочется, то проверку можно вынести в отдельный метод. По самому решению. Вот массив из 2 примера: Код: java 1. 2. 3. 4. 5. 6. Все 48 "пикселей" этого массива удовлетворяют шаблону BW, в том числе и угловые, отсюда и можно сделать вывод, что учитываются не только горизонтальные, но и вертикальные и диагональные совпадения (и даже ходы "конем"). То есть пиксели не должны стоять рядом, достаточно найти любое совпадение. Для примера, такой массив должен тоже дать в результате 48: Код: java 1. 2. 3. 4. 5. 6. Далее просто обобщаем на ломанные в случае с более длинными шаблонами. В конце концов, в условиях задачи нигде не сказано, что пиксели должны составлять линию, либо находиться на определенном расстоянии друг от друга. Ну, и отсюда решение: - проверить, что на экране есть все пиксели из шаблона, если это не так, результат 0. - посчитать на экране те пиксели, которые имеются в шаблоне - это и есть ответ. Я предложил решать с помощью множеств, но это для ленивых, более эффективный алгоритм можно написать с использованием целочисленных массивов. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.07.2013, 09:35:57 |
|
||
|
|

start [/forum/topic.php?fid=59&msg=38340989&tid=2128936]: |
0ms |
get settings: |
9ms |
get forum list: |
19ms |
check forum access: |
5ms |
check topic access: |
5ms |
track hit: |
55ms |
get topic data: |
15ms |
get forum data: |
4ms |
get page messages: |
65ms |
get tp. blocked users: |
2ms |
| others: | 280ms |
| total: | 459ms |

| 0 / 0 |
