Loading...
moholovka avatar moholovka 169 Точки

ProblemSolvingMethodologyHomework

Здравейте, дали някой от екипа може да качи тестовете, защото на нулевите имам верен резултат, а на другите нула и започвам лекинко да се изнервям :) Другият вариант е някой колега да удари едно рамо ако му се занимава, ето кода: 

https://github.com/IvanMladenov/Algorithms/blob/master/ProblemSolvingHomework/ProblemSolvingHomework/RectangleProgram.cs

Благодаря!

Тагове:
Filkolev avatar Filkolev 4482 Точки

Ето ги тестовете: ЛИНК

По принцип за тези задачи има някаква вероятност да са ми грешни решенията, съответно тестовете, но виждам, че има хора с по 100, така че по-скоро няма грешки.

Относно задачата с най-краткия път в матрица - уточнение, което добавих в условието тези дни - ако има два пътя с еднаква дължина, избира се този, в който участват клетки, които са на по-горен ред или в по-лява колона (т.е. обхождането е стандартно по редове отгоре надолу и по колони от ляво надясно). Има няколко души с грешка на 1 тест, които връщат верен път, но просто пътят е различен от този в тестовете. Понеже в джъдж се сравнява изхода 1:1, възможно е верни решения да не минат, затова добавих това допълнително условие.

1
moholovka avatar moholovka 169 Точки

Ами не, аз се сетих къде ми е грешката, въпроса сега е да се сетя как да я оправя :D Мерси за тестовете.

0
moholovka avatar moholovka 169 Точки

Иска потребителско и парола за сървъра.

0
dim4o avatar dim4o 288 Точки

User: student

Pass: student

1
Ivaylo.Goranov avatar Ivaylo.Goranov 68 Точки

Може ли да дадеш линк и към тестовете за първата задача (Shortest Path in Matrix). За примерите от домашното ми върви (нулевите в judge), всички други не минават.
Благодаря предварително.

0
Filkolev avatar Filkolev 4482 Точки

^ Имаш тайм лимити и ексепшъни, виж да не си хардкоднал някакви променливи или проверки, примерите са с еднакъв размер матрици, но в тестовете има всякакви.

IndexOutOfRangeException - това е, което виждам, би трябвало да можеш да го намериш ако изтестваш.

Ще ги кача и тези тестове по някое време.

1
20/11/2015 17:14:04
Filkolev avatar Filkolev 4482 Точки

Тестовете за задачата с матрицата са ТУК.

1
Ivaylo.Goranov avatar Ivaylo.Goranov 68 Точки

Мерси много. Оправих exception-а (от хардкодната стойност беше наистина). Тайм лимитите ми явно са при големите матрици, понеже използвам backtracking да обхождам матрицата и заспива програмата. Ще гледам до утре да измисля някаква оптимизация. Сега не се сещам за нищо. Мислих си за greedy подход да избира най-малката от съседните 4-ри стойности, но така пък не мисля, че ще се изчислят правилно разстоянията.

0
moholovka avatar moholovka 169 Точки

С едно обхождане по всички нодове трябва да стане, като стигнеш до някъде трябва да запазиш пътя до там. Аз го направих с клас Node, където пазя най малкото разтояние до нода, оригиналната стойност и нода от където се стига до него. Като свърши Дийкстрата можеш да получиш най-краткият път от който и да е нод до стартовия. https://github.com/IvanMladenov/Algorithms/blob/master/ProblemSolvingHomework/ShortestPathInMatrix/Program.cs 

Не е най-умното нещо дето съм писал ама мисля че работи добре.

1
Filkolev avatar Filkolev 4482 Точки

Задачата е класическо приложение на Dijkstra, просто графът е даден като матрица. На мен най-трудната част ми беше да го преобразувам като ползвах списък на съседство (защото с него най-лесно боравя, а и най-често сме ползвали май).

1
dim4o avatar dim4o 288 Точки

Ето и едно решение с матрица на съседство: http://pastebin.com/kcm8QNbC. Стори ми се по-естествено, защото имам на входа матрица и защото съм го правил вече с матрица и имам кода готов. Ако ми остане време смятам да направя и Dijkstra със списък на съседство. Но наистина преобразуването на входната матрица беше най-засуканата част - макар и доста по-кратка и лека от Dijkstra като логика.

3
21/11/2015 12:03:25
Ivaylo.Goranov avatar Ivaylo.Goranov 68 Точки

Днеска докато преговарях лекцията за динамично оптимиране попаднах на алгоритъма за "Move Down/Right Sum" задачата. Според мен задачата за най-кратък път в матрица може да се сведе до нейна версия. Реших я по този начин, в джъдж 75/100, но нямам време да дебъгвам.

0
Filkolev avatar Filkolev 4482 Точки

Според мен няма как да се получи така, понеже нямаш ограничение накъде може да се ходи и съответно имаш грешни отговори на няколко теста, в които дължината на пътя е по-голяма от оптималната.

В един от тестовете пък връщаш правилен отговор, но не спазваш условието за обхождане, понеже има два пътя с еднаква дължина, а за да се направи задачата тестваема трябва да минеш по точно определен от тях. Ако имаш два пътя с еднаква дължина трябва да минеш по този, който минава по клетки, които са на по-малък ред/колона.

1
Ivaylo.Goranov avatar Ivaylo.Goranov 68 Точки

Да, прав си. А "move down/right" поставя ограничение за движение...

0
moholovka avatar moholovka 169 Точки

С едно обхождане по всички нодове трябва да стане, като стигнеш до някъде трябва да запазиш пътя до там. Аз го направих с клас Node, където пазя най малкото разтояние до нода, оригиналната стойност и нода от където се стига до него. Като свърши Дийкстрата можеш да получиш най-краткият път от който и да е нод до стартовия. https://github.com/IvanMladenov/Algorithms/blob/master/ProblemSolvingHomework/ShortestPathInMatrix/Program.cs 

Не е най-умното нещо дето съм писал ама мисля че работи добре.

0
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.