Loading...
zisov4eto avatar zisov4eto 19 Точки

[C# Sample Exam 13.06] Problem 2. Jedi Galaxy

Здравейте колеги!

Имам поблем с намемирането на оптимизирано решение на тази задача и под оптимизирано имам предвид без нито една излишна итерация.

На кратко това което правя е да намеря диагоналите по, които Иво и злата Сила се движат като използвам формулката от проблема от отвореният курс по Алгоритми - Eight Qeens. След това използвам един бърз while, който да ми намери най-първата клетка от текущият диагонал, която е в матрицата. Правя същото нещо и за двата диагонала. Нататък логиката продължава стандартно с един while, който се движи само по диагонала и в зависимост дали е Иво или злата Сила, събира или унищожава клетките през, които минава.

 

Проблемът: 0/100 точки в judge. Двата нулеви теста минават. Също така минават и комбинирано.

 

SOURSE CODE

Тагове:
0
C# Advanced 16/06/2016 15:50:12
vani4ka66 avatar vani4ka66 24 Точки

Много сложна си направил задачата. Понеже в момента не мога да видя къде гърми, ако искаш виж друго решение, според мен е доста оптимизирано!

 

https://github.com/vani4ka66/Melrah-Shake/blob/master/Jedi%20Galaxy

1
zisov4eto avatar zisov4eto 19 Точки

Моят код дава само грешни отговори. Застраховал съм се да не гърми никъде. 

 

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

 

До колкото разбирам от условието трябва да се обходи целият диагонал независимо къде са подадени координатите. Ами ако те са вътре в матрицата това значи, че трябва да се обходи освен от дадената клетка нагоре, също така и на доло. 

 

Знам, че съм си ослужнил работата, но целта ми е перформънс, да не излизам от рамката на матрицата. 

0
16/06/2016 17:16:03
RoYaL avatar RoYaL Trainer 6849 Точки

Не можеш ли да Min()-неш дадения координат и border-а на матрицата и да почнеш от там?

1
vani4ka66 avatar vani4ka66 24 Точки

         Първоначално го бях направила така - 

 

                        int currentRow = evilStartRow  < 0 ? 0: evilStartRow ;
                        intcurrentCol = evilStartCol < 0 ? 0: evilStartCol;

 

 


 

0
zisov4eto avatar zisov4eto 19 Точки

Ако се вървеше само по вертикала и хоризонтала да, но за да хвана диагонала с Min() поне аз не мога да си го представя.

0
vani4ka66 avatar vani4ka66 24 Точки

Ти проверяваш само данните, които ти подават на входа дали са в матрицата, ако  едната ти е -1 например,  я правиш да е 0, и после вървиш по диагонала, като само си следиш да не излезеш от матрицата, докато вървиш нагоре. 

0
vani4ka66 avatar vani4ka66 24 Точки

Фейсбука умря :) 

та като имаш 5-та колона, вадиш 1, и така вземаш  4-ти ред , -2 ти става 0, и те нали ти казват в условието, че иво винаги върви от долу ляво към горе дясно, а дявола върви от долу дясно само нагоре по диагонал наляво. 

0
k_mitova avatar k_mitova 15 Точки

Където и да е началото на диагонала на Иво се взимат стойностите само нагоре, същото се отнася и за диагонала на злата сила. 

0
zisov4eto avatar zisov4eto 19 Точки

Демек ако клетката ти се пада в центъра на матрицата тръгваш само нагоре по диагонала и забравяш за диагонала надолу от клетката, така ли?

0
Ivanov.Ivan avatar Ivanov.Ivan Trainer 558 Точки

Точна така

1
zisov4eto avatar zisov4eto 19 Точки

Ами надявам се качат тестовете на задачката, че ми стана много любопитно.

0
TihomirDimov avatar TihomirDimov 161 Точки

Това е моето решение - дава 70 от 100 точки. Цяла вечер се опитвам да си разбера проблема с останалите 30 точки. Може ли за помощ. Благодаря

http://pastebin.com/AZfYEQua

0
k_mitova avatar k_mitova 15 Точки

В методът където проверяваш дали клетката е в матрицата подаваш като параметри int galaxyCol, int galaxyRow , а като ги използваш в Main метода си ги разменил galaxyRows,galaxyCols.

1
12/08/2016 13:34:15
TihomirDimov avatar TihomirDimov 161 Точки

Благодаря!

0
sevdalin avatar sevdalin 38 Точки

Колеги, не ми става ясно едно нещо. В условието на задачата се казва: "The given columns will be valid integers in the range [MinInt32, MaxInt32]."

А в кода на vani4ka66 правим следната проверка:

        while (ivoRow >= 0 && ivoCol < matrix.GetLength(1))
        {
            if (IsInMatrix(ivoRow, ivoCol, matrix))
            {
                sum += matrix[ivoRow, ivoCol];
            }
            ivoRow--;
            ivoCol++;
        }

С тази проверка в While цикъла за ivoCol ние изключваме input от задачата с координати от сорта на 5 -100, което е извън матрицата, но по условие е позволено.

А това ни е 2-рата проверка:

        while (evilCol >= 0 && evilRow >= 0)
        {
            if (IsInMatrix(evilRow, evilCol, matrix))
            {
                matrix[evilRow, evilCol] = 0;
            }
            evilCol--;
            evilRow--;
        }

Тук с проверката, която правим на evilCol (evilCol >= 0) отново изключваме input с координати, колона -N.

Не разбирам, защо е направено по този начин. В условието се казва, че единият диагонал(на Иво) започва от "from the lowest left to the upper right", а на Evil от " From lowest right to the upper left. ".

Constraints ни покриват row:

- The given rows will be valid integers in the range [0, 2000].

Но не и col, както вече споменах, а ние го ограничаваме собственоръчно при проверката.

Не разбирам защо  е така. Някой може ли да ми обясни?

0
vani4ka66 avatar vani4ka66 24 Точки

Не знам дали правилно съм разбрала въпроса ти, но ти трябва да провериш само данните, които ти подават на входа дали са в матрицата, ако  едната ти е -1 например,  я правиш да е 0, и после вървиш по диагонала, като само си следиш да не излезеш от матрицата, докато вървиш нагоре.         

                        int currentRow = evilStartRow  < 0 ? 0: evilStartRow ;
                        intcurrentCol = evilStartCol < 0 ? 0: evilStartCol;

0
sevdalin avatar sevdalin 38 Точки

Да но ти тази if проверка с тернарният оператор, не я правиш в кода тук

https://github.com/vani4ka66/Melrah-Shake/blob/master/Jedi%20Galaxy

0
vani4ka66 avatar vani4ka66 24 Точки

Ами предполагам, че дори и да ти подадат отрицателно число за колоната на Иво, ivoStartCol докато е по-малка стойност от cols, ще се върти цикъла, и на всяка итерация ivoStartCol ще се увеличава с едно, докато попадне в матрицата и не се изпълни проверката в цикъла. 

 

while (ivoStartRow >= 0 && ivoStartCol < cols)
  {
  if (IsInMatrix(matrix, ivoStartRow, ivoStartCol))
  {
  sum += matrix[ivoStartRow, ivoStartCol];
  }
   
  ivoStartRow--;
  ivoStartCol++;
  }
0
sevdalin avatar sevdalin 38 Точки

Тъй като се разбрахме във ФБ, само да добавя за някой друг ако чете. Стигнахме до извода, че условието на задачата не е написано както трябва и е некоректно, защото колоната пише че може да е пълният диапазон на Int32, а матрицата е с размери 5, 2000 макс, което може да доведе до input по-голям от матрицата, при който няма да влезе в while цикъла, така както е написано. Интересното е че минава 100/100, което означава грешно условие на задачата...

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