JA1-Task-4-Roxettes
Не знам дали е прието да си поставяме кода тук, ако не е прието обещавам да не правя повече така. Та идеята ми е къде може да се оптимизира кода по-долу защото judge гърми та трещи от 6-ти тест нататък за време и на последния за памет.
#include <iostream>
#include <vector>
#include <sstream>
using namespace std;
int main() {
string dnaSequence {};
vector<short int> dnas;
unsigned short int pos;
cin >> dnaSequence;
unsigned int length = dnaSequence.length();
if (length > 15) {
string currDna{};
for (int i = 0; i <= length; i++) {
if (i % 5 == 0 && i > 0) {
short int x = stoul(currDna, nullptr, 16);
dnas.push_back(x);
currDna = {};
}
currDna = currDna + dnaSequence[i];
}
unsigned int numDna = (length - 1)/5;
for (int i = 0; i < numDna; i++) {
bool isUnique{true};
for (int j = 0; j < numDna; j++) {
if (i != j && dnas[i] == dnas[j]) {
isUnique = false;
break;
}
}
if (isUnique == true) {
pos = i;
break;
}
}
for (int i = pos * 5; i <= pos * 5 + 4; i++) {
cout << dnaSequence[i];
}
}
else if (dnaSequence.length() == 6){
cout << dnaSequence << endl;
}
return 0;
}
Здравей Георги.
В предишния курс задачата ме изяде, тогава не успях да взема 100те точки точно поради 2та мегабайта ограничение.В момента си мисля, ако използвам двумерен масив от чарове в които една Роксет ДНК ще бъде 5бита, ще ми позволи ли да се вмъкна във времето и 2MB памет?
Здравей,
В паметта може и да се вмъкнеш (както е настроена сега за 16 МБ, вместо 2-та които пише в условието), но във времето почти със сигурност няма да се вмъкнеш само с масив - търсенето ще ти отнема твърде много време. set би бил по-добър вариант (търсенето е много по-бързо).
При всички положения това, което обясних на лекцията, е доста по-бързо и ефикасно от всички други подходи, които се мъчат да пазят самите елементи.
Поздрави,
Жоро
Задачата наистина е много добра! :)
В предишното издание на курса успях да се вмъкна в изискването за памет като ползвах bitset (това решение може да се приложи за произволен брой уникални ентрита), но правилното решение е друго (hint - побитови операции).
Жоро, направих нещата както даде hint на 3-тата лекция, но пак гърми за памет на последния 10-ти тест. Ако имаш време и желание може да погледнеш тук. Аз не се сещам какво още може да оптимизирам на тоя код от 13 реда реална програма.
Четеш всички входни данни наведнъж и при голям входен поток минаваш лимита за памет.
Лесно (и неоптимално) решение на този проблем е да четеш символ по символ от конзолата. По-смислено решение е да използваш буфер с фиксиран от теб размер, който се вписва в лимитите за памет и ускорява изпълнението на програмата (по-малко заявки към конзолата).
Да, Мартин правилно е отбелязал, че няма смисъл да четеш целия string в паметта, и чак след това да го обработваш. На теб във всеки един момент от задачата ти трябва само текущото "число"/dna, не ти трябва да си пазиш в паметта всички. Тоест за тази задача работи да си имаш char xorred[5] за "резултата", който xor-ваш, и още един char current[5], в който четеш с по един cin всеки елемент.
Разбира се да четеш много пъти по 1 елемент е по-бавно отколкото веднъж да прочетеш толкова на брой елементи. Затова Мартин предлага да четеш колкото памет ти е разрешено в judge в един масив/стринг и след това да обработиш това парче, след това пак да прочетеш толкова и т.н. - това ще е още по-бързо, но за текущите ограничения варианта с 5-те cin-а на всяка итерация също върши работа.
Поздрави,
Жоро
Жоро, Мартине благодаря, преборих ги до 100/100. Без вашите hints нямаше как да се усетя, все пак съм само на един Cpp basics към момента.
Аз си поиграх малко с тая задачка и тествах различни неща. Успях да направя няколко работещи решения, които се вместват в ограничението за 2MB памет. Най-доброто е това
Постига се когато се чете само по един символ. Ако се четат няколко символа едновременно, времето за изпълнение е малко по-голямо.
@kolioi
Ето моето най-бързо решение (link expires in 2 weeks) от предишното издание на курса (наблягам на "най-бързо", защото кодът не от най-лесно разбираемите, въпреки че е само 30-на реда):
Memory: 1.85 MB
Time: 0.103 s
BTW eдин колега беше успял да смъкне времето до 0.062 с още микрооптимизации и по-голям буфер.
Ами аз забравих да кажа, че моят код е оптимизиран за памет. Цялата програмка е само 5-6 реда и имам само тези променливи
Ако я оптимизирам за бързина, естествено трябва да чета по-голям буфер, т.е. да намаля входно-изходните операции. Което ще стане за сметка на паметта. Ако ми остане време тия дни, ще си поиграя още малко.
@MartinBG
Оптимизирах малко кода за бързина и успях да я докарам до тук
С една забележка: кода ми е на С. Анси си. Голямо значение има размера на буфера и предполагам, че може да се оптимизира още, но не ми се занимава повече. Ще пусна малко код (поне 2-3 разични решения) след като мине срока.