Софтуерно Инженерство
Loading...
moholovka avatar moholovka 169 Точки

ProblemSolvingMethodologyHomework

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

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

Благодаря!

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

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

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

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

1
moholovka avatar moholovka 169 Точки

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

0
moholovka avatar moholovka 169 Точки

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

0
dim4o avatar dim4o 289 Точки

User: student

Pass: student

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

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

0
Filkolev avatar Filkolev 4486 Точки

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

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

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

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

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

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 4486 Точки

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

1
dim4o avatar dim4o 289 Точки

Ето и едно решение с матрица на съседство: 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 4486 Точки

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

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

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