APRENDIZAJE AUTOMÁTICO PARA CATEGORIZAR LOS
VEREDICTOS TIME-LIMIT EN JUECES EN LÍNEA
MACHINE LEARNING FOR CLUSTERING TIME-LIMIT VERDICTS
IN ONLINE JUDGES
TRABAJO FIN DE GRADO
CURSO 2022-2023
AUTOR
MIGUEL MENÉNDEZ GALINDO
DIRECTORES
PEDRO PABLO GÓMEZ MARTÍN
MARCO ANTONIO GÓMEZ MARTÍN
GRADO EN INGENIERÍA INFORMÁTICA
FACULTAD DE INFORMÁTICA
UNIVERSIDAD COMPLUTENSE DE MADRID
APRENDIZAJE AUTOMÁTICO PARA CATEGORIZAR LOS
VEREDICTOS TIME-LIMIT EN JUECES EN LÍNEA
MACHINE LEARNING FOR CLUSTERING TIME-LIMIT VERDICTS
IN ONLINE JUDGES
TRABAJO DE FIN DE GRADO EN INGENIERÍA INFORMÁTICA
AUTOR
MIGUEL MENÉNDEZ GALINDO
DIRECTORES
PEDRO PABLO GÓMEZ MARTÍN
MARCO ANTONIO GÓMEZ MARTÍN
CONVOCATORIA: SEPTIEMBRE 2023
GRADO EN INGENIERÍA INFORMÁTICA
FACULTAD DE INFORMÁTICA
UNIVERSIDAD COMPLUTENSE DE MADRID
SEPTIEMBRE DE 2023
DEDICATION
To all s uden s who ha e expe ienced he
us a ion o TLE h oughou hei lea ning
p ocess.
2
ACKNOWLEDGMENTS
To Ped o and Ma co o he ime and pa ience in es ed in his wo k in he easy
momen s and especially in he di icul ones; i would no ha e been possible wi hou
hem.
3
RESUMEN
APRENDIZAJE AUTOMÁTICO PARA CATEGORIZAR LOS VEREDICTOS TIME-LIMIT EN
JUECES EN LÍNEA
El uso de jueces en línea se ha popula izado como una he amien a pa a
mejo a las habilidades de p og amación al medi la e iciencia de las soluciones y
comp oba su cumplimien o de los equisi os del p oblema. Sin emba go, cuando una
solución excede el iempo lími e, el juez p opo ciona poca in o mación sob e la causa
del e o . Con el obje i o de mejo a la in o mación en los e edic os o ecidos po los
jueces, es e es udio p opone ex ende su uncionalidad implemen ando un módulo de
pis as. Es e módulo se á capaz de in o ma a los usua ios sob e la causa de los
e edic os ob enidos, cen ándose exclusi amen e en los e edic os de iempo lími e
excedido o TLE.
Pa a log a es e obje i o se plan ea clasi ica los e edic os TLE en es
ca ego ías: bucles in ini os, plan eamien os e óneos y soluciones poco óp imas. El
módulo clasi ica las soluciones haciendo uso de una pieza capaz de p edeci el o den
de complejidad de una solución en íada al juez, c onome ando su iempo de
ejecución pa a una se ie de casos de p ueba. Pa a es a pieza exis en dos
implemen aciones, una basada en modelos de in eligencia a i icial y o a basada en
unciones de eg esión.
El obje i o de es e abajo consis e en mejo a la expe iencia de usua io al
u iliza jueces en línea, sin eemplaza los, aumen ando la can idad de de alles
in o mación p opo cionada po el sis ema de e edic os en los jueces en línea.
Palab as cla e
Juez en línea, Ve edic o, TLE, Modelo de IA, Funcion de eg esion.
4

ABSTRACT
MACHINE LEARNING FOR CLUSTERING TIME-LIMIT VERDICTS IN ONLINE JUDGES
The use o online judges has become popula as a ool o imp o e p og amming
skills by measu ing he e iciency o solu ions and checking hei compliance wi h
p oblem equi emen s. Howe e , when a solu ion exceeds he ime limi , he judge
p o ides li le in o ma ion abou he cause o he e o . In o de o imp o e he
in o ma ion in he e dic s p o ided by judges, his s udy p oposes o ex end i s
unc ionali y by implemen ing a clue module capable o in o ming use s abou he
cause o he ob ained e dic s, ocusing exclusi ely on ime-limi exceeded o TLE
e dic s.
To achie e his goal, we p opose o classi y TLEs in o h ee ca ego ies: in ini e
loops, w ong app oaches and subop imal solu ions. The module classi ies he solu ions
by making use o a pa capable o p edic ing he o de o complexi y o a solu ion sen
o he judge, iming i s execu ion ime o a se ies o es cases. Fo his pa he e a e
wo implemen a ions, one based on a i icial in elligence models and he o he based
on eg ession unc ions.
This wo k aims o imp o e he use expe ience when in e ac ing wi h online
judges, wi hou eplacing hem, by inc easing he amoun o de ailed in o ma ion
p o ided by he e dic sys em on he online judges.
Key wo ds
Online judge, Ve dic , TLE, AI model, Reg ession unc ion.
5
Con en index
Chap e 1 - In oduc ion........................................................................................................... 1
1.1 Mo i a ion.........................................................................................................................1
1.2 Objec i es.........................................................................................................................2
1.3 Wo k plan..........................................................................................................................3
1.4 P ojec eposi o y............................................................................................................. 4
Chap e 2 - S a e o he a .......................................................................................................5
2.1 In oduc ion...................................................................................................................... 5
2.2 Online judges................................................................................................................... 5
2.3 Execu ion ime measu emen ........................................................................................ 9
2.4 Sequen ial machine lea ning models based on supe ised lea ning.....................10
2.5 Reg ession algo i hms wi h supe ised lea ning......................................................... 14
Chap e 3 - Applica ion a chi ec u e....................................................................................16
3.1 P ojec s uc u e.............................................................................................................16
3.2 Complexi y o de p edic o .......................................................................................... 19
3.3 Execu ion ime measu e .............................................................................................. 20
3.4 Da a model...................................................................................................................... 22
Chap e 4 - Complexi y p edic o based on Neu al Ne wo ks...........................................23
4.1 Pseudo- andom gene a o o aining da a...............................................................24
4.2 Classi ie based on neu al ne wo ks............................................................................ 26
Chap e 5 - Complexi y p edic o based on eg ession unc ions.....................................29
Chap e 6 - Valida ion o he complexi y p edic o module based on eg ession..........31
6.1 Gene ic alida ions....................................................................................................... 31
6.2 Speci ic alida ions........................................................................................................34
Chap e 7 - Conclusions and u u e wo k............................................................................. 37
7.1 Conclusions.....................................................................................................................37
7.2 Fu u e wo k..................................................................................................................... 38
Chap e 8 - Bibliog aphy..........................................................................................................40
6
Figu e index
Figu e 1: Sequen ial model..............................................................................................12
Figu e 2: Recu en sequen ial model..............................................................................12
Figu e 3: Usage o ac i a ion unc ions............................................................................13
Figu e 4: Clue module use case...................................................................................... 16
Figu e 5: Da a low in he clue module.............................................................................18
Figu e 6: Diag am o he inne low o he clue module................................................... 19
Figu e 7: Complexi y p edic o diag am...........................................................................19
7
Table index
Table 1: P oblems e alua ed by he module.............................................................. 33
Table 2: Module p ecision classi ied by complexi ies.................................................33
Table 3: E asmús solu ion measu emen s................................................................. 35
Table 4: Complexi y p edic ions o he solu ions o E asmús.....................................36
8
●[PE] P esen a ion E o : he p o ided solu ion gene a es he co ec ou pu s, bu
he space and ab o ma is no co ec .
●[WA] W ong Answe : he uploaded solu ion is w ong as i does no gene a e he
ou pu de ined by he p oblem s a emen o a leas one o he p o ided inpu s.
●[CE] Compila ion E o : he judge wasn’ able o compile he gi en solu ion.
●[RTE] Run Time E o : he use 's solu ion aises an excep ion du ing execu ion, o
example di iding by ze o.
●[TLE] Time Limi Exceeded: he p o ided solu ion couldn’ gene a e an ou pu in
he ime ame de ined o his p oblem.
●[MLE] Memo y Limi Exceeded: he uploaded solu ion exceeded he maximum
memo y limi allowed du ing execu ion.
●[OLE] Ou pu Limi Exceeded: he use s solu ion exceeded he maximum numbe
o ou pu cha ac e s du ing execu ion.
●[RF] Res ic ed Func ion: he solu ion pe o med an ope a ion ha he judge
conside ed dange ous and abo ed i s execu ion.
●[IE] In e nal E o : he judge su e ed a p oblem du ing execu ion ex e nal o he
solu ion unde e alua ion.
●[IQ] In Queue: he solu ion is in he queue and hasn’ been analyzed ye .
F om a egula use ’s poin o iew, each o his e dic s indica e a di e en
p oblem in he uploaded solu ion and hus should ocus on di e en ideas in o de o
ind and sol e he p oblem, hese being:
●PE: he use should e iew all o he line endings and spacings in he o ma used
o gene a e he ou pu .
●WA: e i y he s a emen in o de o ensu e i has been co ec ly in e p e ed, also
es he limi cases o la ge inpu s in o de o e i y he ou pu .
●RTE: simila ly o he p e ious e dic , e i y he mo e special cases in o de o
ensu e he p og am doesn' b eak while p ocessing hem.
●TLE: e iew he algo i hm checking i i may be u he op imized o implemen ed
in a di e en way educing i s complexi y.
●MLE: analyze how he p og am p ocesses da a and y o ind a way ha s o es
less amoun s o gene a ing he ou pu s.
●OLE: e i y ha he p og am co ec ly de ec s he end o he inpu da a and
wha is being w i en o he ou pu .
When de ining p oblems in an online judge, p oblem se e s usually ha e an
objec i e in mind like limi ing he complexi y o accep ed solu ions o o ce hem o
p ocess da a wi hou s o ing i in a cle e manne . Fo example a p oblem se e may
de ine a p oblem so ha use s can p ac ice so ing algo i hms. The objec i e in mind
may be o accep only e icien solu ions, o cing use s o igu e ou as e so ing
7

algo i hms o sol e he p oblem in e icien complexi ies like O(n*log(n)). This is achie ed
by de ining a small ime ame o solu ions o gene a e hei ou pu and la ge p o ide
es cases o he e alua ion p ocess. I he p oblem is in ended o beginne s, he
p oblem se e may hen aise he maximum ime a ailable in o de o also accep
solu ions o O(n²) and lowe he es case size, conside ing as alid bubble so
algo i hms as well. Ano he example, his ime ega ding memo y usage, is o cing use s
o implemen solu ions ha ead and p ocess da a wi hou s o ing i , by se ing a small
memo y amoun allowed and p o iding la ge es cases.
As shown by he p e ious examples, ime and memo y limi s a e e y impo an ,
and p oblems wi h high TLE o MLE e dic s usually a e designed o use s o ace hem
and imp o e hei solu ions in a speci ic way. This in o ma ion abou a p oblem can gi e
a hin on whe e i s di icul y esides, his is he eason why pa icipan s in compe i i e
p og amming a e only allowed o see hei own e dic s.
P oblem se e s ace a complex ask when de ining hese limi s, as judges usually
suppo mul iple p og amming languages o use s o sol e p oblems and each
language has a di e en p ocessing speed. Fo example compa ing Ja a and C++, a
O(n²) solu ion in C++ may be quicke han a O(n*log(n)) solu ion in Ja a o small
enough es cases. This p esen s a big challenge o p oblem se e s as hey need o
de ine limi s and es cases ha slow languages can achie e, while also limi ing mo e
complex solu ions in quicke languages. To sol e his issue, p oblem se e s usually need
o design a a ie y o solu ions in mul iple languages, some mo e e icien and some
pu posely slow in o de o measu e he ime and memo y usage and accu a ely de ine
hese limi s.
F om a egula use ’s poin o iew, ecei ing TLE as a e dic usually causes a lo
o us a ion as beginne p og amme s usually y o u he op imize hei solu ion ha in
mos cases has he w ong complexi y. This ends up in mul iple uploads o he same
solu ion wi hou any eal imp o emen owa ds he desi ed solu ion and ends o make
use s hink he p oblem se e was oo s ic when de ining he ime limi . On he o he
hand, mo e expe ienced de elope s ha code an algo i hm wi h he igh complexi y
comple ely edo hei solu ion, hinking hey a e su e ing om he p e iously men ioned
case.
In bo h o he cases men ioned abo e he judge gene a es a TLE e dic lacking
u he de ails on he oo cause o he e o , which could be e y help ul owa ds he
use . In ac i could p o ide ex a in o ma ion abou how o sol e he p oblem, his
in o ma ion shouldn’ be speci ic o he cu en p oblem bu ea he issue gene ically.
Fo example when ecei ing a WA e dic , he judge could p o ide he es case ha
ailed o he use so ha i can be alida ed locally and co ec ed. The goal behind his
8
p ojec is o gene a e clues, simila o he one desc ibed o WA e dic s applied o TLEs.
The gene ic clue p oposed is o de e mine in which o he ollowing ca ego ies he TLE
ound in he e alua ed solu ion alls in o:
●Caused by an in ini e loop: he solu ion con ains an in ini e loop ha p e en s
execu ion om e mina ing, esul ing in exceeding he ime limi .
●Caused by w ong complexi y: he uploaded solu ion uses an algo i hm wi h a
complexi y wo se han he one expec ed by he p oblem s a emen .
●Caused by lack o op imiza ion: he gi en solu ion u ilizes an algo i hm ha does
ha e he expec ed complexi y bu he implemen a ion is oo ine icien .
A e his classi ica ion, he judge would be able o p o ide he use wi h a
gene ic clue, complemen ing he TLE e dic , ha u he in o ms him abou he oo
cause o he e o and how o ea i . This should esul in less us a ion o use s while
u ilizing he online judge and a lowe amoun o w ong consecu i e uploads o solu ions
wi h he same unde lying p oblem.
2.3 Execu ion ime measu emen
Time measu emen s a e a undamen al pa o he e alua ion p ocess o a
p og am's pe o mance, bu achie ing accu a e esul s can be e y di icul due o
di e en ac o s. In compu e sys ems he e a e a mul i ude o p ocesses unning in he
backg ound and he execu ion ime o a speci ic p og am may be a ec ed by he
es . Also consecu i e execu ions o he same p og am may esul in di e en
measu emen s due o di e en ac o s such as ha ing he da a on disk o on cache as
hei access speeds a e e y di e en .
The mos common p oblems ound while measu ing execu ion imes a e he
ollowing:
●Va iabili y in esul s: Execu ion imes o he same p og am may a y among
consecu i e execu ions due o ex e nal ac o s like he cu en sys em’s load o
luc ua ions in he sys em’s esou ce.
●Noise: The ope a ing sys em and o he backg ound p ocesses may in e e e wi h
he p ocess being measu ed nega i ely impac ing he accu acy o he
measu emen s.
●Tools: he use o inadequa e ools o measu ing he execu ion imes may also
in oduce e o s on he measu emen s.
●Clock esolu ion: choosing a esolu ion ha i s he kind o p og ams ha will be
execu ed is key as o example, measu ing quick p ocesses in milliseconds may
esul in simila esul s while measu ing di e en size execu ions.
9
When measu ing solu ions, he judge launches a p ocess o he solu ion wi h a
se o es cases, measu ing he du a ion o his p ocess and ob aining he execu ion
ime. This can be a p oblem because i also conside s as execu ion ime he c ea ion
and e mina ion o he p ocess. This ime may con amina e he measu emen s as ha
ime migh no be negligible wi h espec o he es o he p ocessing ime, especially in
languages ha equi e he s a up o a VM such as Ja a.
Th ee o he mos impo an ac o s o conside when acing he p oblem o
un ime measu emen a e he ope a ing sys em, he ha dwa e and he p og am o be
measu ed i sel . In addi ion, i is impo an o ca e ully choose he ools used o bo h
measu e and analyze he da a as hey ha e a g ea impac on he esul s [3].
O he help ul ac ions ha can be aken in o de o u he imp o e he accu acy
o he measu emen s a e ha ing solu ions e alua e mul iple cases pe execu ion and
measu ing each execu ion mul iple imes. The i s mi iga ion measu e consis s o ha ing
he measu ed p oblem e alua e mul iple es cases on each execu ion, his esul s in an
inc eased execu ion ime which mi iga es he clock esolu ion issue. I also educes he
impac o he ime used in he c ea ion and e mina ion o he p ocess bu inc eases
he p obabili y o ex e nal p ocesses in e e ing as execu ion ime is longe . The second
mi iga ion measu e consis s o measu ing each execu ion mul iple imes o he same
se o es cases and hen calcula ing he mean. This ac ion conside ably educes he
noise con ained in he measu emen s, his echnique is no o en used by online judges
bu i will be used in his p ojec as p ecision is key [4].
2.4 Sequen ial machine lea ning models based on supe ised lea ning
As men ioned ea lie in his pape , he objec i e o his p ojec consis s o
p o iding clues o use s ha ob ained TLE e dic s in judges. I is in ended o achie e
his by de e mining he ype o TLE he use is acing and in o ming abou i s oo cause.
To achie e his, i is necessa y o ind ou he complexi y o he solu ion he use
uploaded o he judge, one possible app oach is o use au oma ic lea ning.
Algo i hms based in au oma ic lea ning enable machines o lea n and make
decisions using a se o aining da a, composed o inpu alues and hei expec ed
ou pu s. This enables he algo i hm o alida e i s own p edic ions du ing he aining
p ocess. Algo i hms o his kind a e based on he capaci y machines ha e o de ec
pa e ns and ela ionships ound in da a, enabling hem o classi y and p edic new
cases basing hei decisions on wha hey ha e lea ned du ing aining.
Fo his p ojec i is equi ed o design a sys em capable o ecei ing as an inpu
an use 's solu ion, o a se o da a ob ained om his solu ion and p oduce as an ou pu
10
he complexi y o de i belongs o. The issue is we don' know how o design such a
p og am, o sol e his we in end o sea ch solu ions ha use an au oma ic lea ning
algo i hm o gene a e he p edic ions based on ga he ed da a. The main idea is o use
as inpu da a a se o measu emen s pe o med in he use s solu ion, he measu emen s
con ain execu ion ime and size o he execu ed es case. The ou pu should be he
complexi y o de o he e alua ed solu ion.
The e exis many di e en kinds o models inside he supe ised au oma ic
lea ning algo i hms ca ego y, each wi h hei own ad an ages and disad an ages. Fo
his p ojec we will ocus on neu al ne wo ks, his implemen a ion will be u he
discussed in chap e 4 o his pape , bu in his sec ion we will in oduce he opic.
The e a e mul iple ypes o neu al ne wo ks, a e y common ype a e sequen ial
models. These kinds o ne wo ks a e o med by laye s o neu ons loca ed one a e
ano he , o ming a sequence. The ini ial laye se es as he inpu poin o he model
and con ains one neu on pe inpu alue ha he model will ecei e. Simila ly he las
laye o he sequence se es as he ou pu poin o he ne wo k and con ains one
neu on pe ou pu alue. The in e media e laye s a e in cha ge o ans o ming he
inpu da a in o he expec ed ou pu alues. Each neu on is connec ed o all o he
neu ons in he nex laye on he sequence and each connec ion has a weigh
associa ed wi h i . Using hese connec ions and hei espec i e weigh s, he alue
ecei ed in one neu on is ans o med in o a new alue and ansmi ed in o each o
he neu ons on he nex laye . This p ocess is ca ied ou un il eaching he las laye
whe e he ou pu o he ne wo k is gene a ed o he inpu da a p o ided in his
execu ion. The ollowing igu e shows a gene al diag am o a neu al ne wo k wi h h ee
inpu s, one ou pu and one in e media e laye o med by h ee neu ons.
Figu e 1: Sequen ial model
11
As men ioned abo e, in sequen ial models da a s a s a he inpu laye and
a e ses he ne wo k in a single di ec ion un il eaching he las laye o he sequence.
The e also a e mo e complex ypes o ne wo ks in which he low o in o ma ion is no
only sequen ial. Some neu ons may include a cyclic low o da a eeding da a in o
hemsel es as well as o wa d in he ne wo k, his enhances hei abili y o emembe
and euse in o ma ion om p e ious s eps while p ocessing da a. This is specially use ul
in asks such as language p ocessing, ex gene a ion, ansla ions and sequen ial da a
analysis like ime sequences. The ollowing igu e aims o show how his cyclic da a low
applies in a diag am simila o he one obse ed ea lie .
Figu e 2: Recu en sequen ial model
As we ha e al eady discussed, each laye is o med by a numbe o neu ons which a e
connec ed o each o he neu ons on he nex laye o he sequence wi h he
excep ion o he ou pu laye . As p e iously explained, each o hese connec ions has a
weigh associa ed ha helps de e mine he alue ansmi ed o he neu on a ge ed
by he connec ion. To de e mine he alue ecei ed by a neu on, he ne wo k mus
i e a e h ough all he neu ons o he p e ious laye , mul iplying he alue s o ed in each
neu on by he associa ed weigh alue o each connec ion. Then i pe o ms a sum o
all hese alues and applies a unc ion o he esul o his ope a ion, his unc ion is
known as he ac i a ion unc ion. The ou pu o his unc ion is he alue ha he neu on
on he nex laye ecei es.
We ha e also men ioned ea lie a ecu si e low o da a, ega ding neu ons
connec ed o hemsel es o use da a om p e ious s eps du ing execu ion. These
connec ions also ha e a unc ion associa ed wi h hem ha is u ilized in o de o
gene a e he alue ansmi ed h ough his connec ion. These unc ions a e called
12

ecu en ac i a ion unc ions. The ollowing igu e con ains a diag am showing he
calcula ion p ocess o he alue ed in o a neu on based on he neu ons loca ed on
he p e ious laye o he ne wo k.
Figu e 3: Usage o ac i a ion unc ions
A e building he s uc u e o a neu al ne wo k model, he e a e wo mo e s eps
needed in o de o he model o be used. Fi s i needs o go h ough a aining phase,
du ing which i will adjus he alues associa ed wi h all o i s in e nal pa ame e s, like
he p e iously men ioned weigh s. Fo his p ocess he model needs o be p o ided wi h
a la ge se o in o ma ion, he aining da ase , which needs o con ain a se o samples
o med by inpu alues and hei expec ed ou pu s. This enables he model o p ocess
he da a and compa e he gene a ed ou pu wi h he one in he aining da a and
adjus he pa ame e alues ying o minimize his e o . Du ing his p ocess he e a e
wo o he pa s o a neu al ne wo k model ha come in o play, he loss unc ion and
he op imize . The loss unc ion is used by he ne wo k in o de o de e mine he e o
con ained in he p edic ions i gene a es. The op imize wo ks alongside he loss
unc ion in o de o minimize he e o in o med by his unc ion. The e a e many
a ailable op ions o hese wo pieces and he choice is in luenced by he ype o da a
he model will p ocess bu he op imal alues a e only ound by ial and e o . The
same idea applies o de e mining he inne s uc u e o he ne wo k. The amoun o
laye s, wha ype o neu ons and how many should each laye ha e and he ac i a ion
unc ions hey use can only be de e mined h ough an i e a i e p ocess based on ial
and e o .
13
2.5 Reg ession algo i hms wi h supe ised lea ning
A i icial in elligence models may be classi ied inside wo la ge ca ego ies,
depending on he p oblems hey a e designed o sol e. The e a e classi ica ion models
ha ecei e a se o inpu a iables and de e mine o which g oup hey belong among
a se o p ede ined ca ego ies. Fo example, gi en a se o cha ac e is ics o an animal,
de e mine i i is a dog, a ca o a ish. The o he g oup is eg ession models which
ecei e a se o inpu alues and p oduce as an ou pu a con inuous alue, o
example gi en a se o cha ac e is ics o a house, de e mine he p ice.
Inside he supe ised lea ning ca ego y, he e exis models designed o sol e
p oblems o bo h o he p e iously men ioned ypes. Focusing on eg ession p oblems,
one app oach consis s o using a ma hema ical unc ion in o de o app oxima e he
ou pu alues based on he a ailable inpu s. Depending on he class o he unc ion
used o hese app oxima ions he e exis linea eg ession models, quad a ic,
polynomic e c. Abo e men ioned neu al ne wo k models can sol e eg ession p oblems
as hei ou pu is a numbe . A he same ime hey can also sol e classi ica ion p oblems
by cus omizing i s ou pu , ei he by assigning nume ical alues o each ca ego y o by
de ining he ou pu as he p obabili y o he inpu da a belonging o a ce ain
ca ego y.
Reg ession unc ions as men ioned abo e a e classi ied in o di e en g oups
depending on he class o he unc ion hey use o gene a e hei ou pu . Fo example,
le 's analyze how a linea eg ession model wo ks. Fi s he model de ines a gene ic
unc ion o he class i belongs o, in linea eg ession he unc ion is y = a + b * x, whe e
a and b a e pa ame e s, x is he inpu alue and y is he ou pu . A e his decla a ion,
he model is ained using a da ase ha con ains inpu s and hei expec ed ou pu s.
Du ing his p ocess he model p oduces alues o he pa ame e s ha appea in he
unc ion, ying o minimize he e o p oduced by he unc ion when e alua ing he
aining da ase . Once his p ocess is comple ed, he model subs i u es he calcula ed
alues o each pa ame e and becomes eady o p edic new cases.
O he kinds o eg ession models wo k in a simila ashion bu using a di e en
ma hema ical unc ion as a basis and a di e en amoun o pa ame e s. The kind o
model used o sol e a p oblem depends on he in o ma ion i has a ailable and he
ela ion his da a has wi h he ou pu alues. Algo i hms based on eg ession may use
one o mo e o hese models in o de o ain a sys em capable o gene a ing nume ical
p edic ions gi en some inpu in o ma ion. They a e used in a wide a ie y o scena ios,
o example economic p edic ions, ma ke analysis, inancial isk e alua ion among
o he s.
14
So a we ha e looked a wha eg ession models a e, how hey wo k and some
o hei ypical applica ions, bu he p oblem discussed in his pape is clea ly a
classi ica ion p oblem. As men ioned ea lie , he p oblem consis s in classi ying solu ions
in o a se o complexi y o de s. A eg ession model is no he ypical app oach o sol e
hese kinds o p oblems bu as i is based on complexi y o de s i can be e y use ul. In
chap e 5 o his pape we will discuss how we may apply eg ession o in o de o
p edic he complexi y o a gi en solu ion. Bu he idea behind his implemen a ion is
based on he ac ha complexi y o de s a e based on ma hema ical unc ions. By
e alua ing he measu emen s o a solu ion wi h a se o eg ession unc ions, one o
each conside ed complexi y and compa ing he e o hey p oduce, i is possible o
de e mine o which complexi y he analyzed solu ion belongs.
15
Chap e 3 - Applica ion a chi ec u e
The pu pose o his p ojec is o design a module ha ex ends he unc ionali y o
al eady exis ing online judges. The goal o his sys em is p o iding use s wi h ex a
in o ma ion abou he w ong e dic s ob ained, ocusing on solu ions ha esul in a TLE
e o .
3.1 P ojec s uc u e
This sec ion will discuss a heo e ical s uc u e o he p oposed implemen a ion o
he module in an online judge, analyzing he pa s ha compose i , how each o hem
wo k and he connec ion o he judge i sel .
The i s hing is o de ine he use case o an online judge in which he module
should come in o play in o de o u he de e mine how i should be in eg a ed. As
shown in he igu e below, he case s a s wi h he use submi ing a solu ion o he
judge, hen i ge s e alua ed as a TLE and ed in o he clue module.
Figu e 4: Clue module use case
A his poin , he module should ecei e a solu ion and any o he da a ele an in
o de o e alua e i and de e mine which o hese TLE ypes i con ains:
●In ini e loop: solu ions ha con ain an in ini e loop and hei execu ion ne e
e mina es.
●W ong complexi y: solu ions ha sol e he p oblem wi h a complexi y g ea e
han he one expec ed by he s a emen .
●W ong op imiza ion: solu ions ha ha e he igh complexi y bu hei
implemen a ion is no op imized enough.
16
Chap e 4 - Complexi y p edic o based on Neu al
Ne wo ks
In he p e ious chap e we ha e desc ibed he design o he clue module and
i s needed inne sys em in o de o achie e he desi ed esul s. One o i s key elemen s is
he complexi y o de p edic o , his piece o so wa e ecei es as an inpu a se o
execu ion imes and sizes measu ed om execu ing a solu ion wi h a se ies o es cases.
Wi h his inpu da a he sys em de e mines he complexi y o de in which he e alua ed
solu ion can execu e he es cases p ocessed.
As men ioned ea lie in his pape , his module may be implemen ed in many
di e en ways and du ing his p ojec we will explo e wo di e en app oaches, bo h
based in supe ised au oma ic lea ning. Du ing his kind o lea ning p ocess i s he
model ge s execu ed wi h a se o known cases ha con ain bo h he inpu da a and
he solu ion.
When designing solu ions in his con ex i is e y impo an o choose a da a
model ha con ains enough in o ma ion o he classi ie o p edic he desi ed
a iables. In ou case he model ecei es a se o execu ion ime and size pai s as an
inpu and is expec ed o p oduce as an ou pu he complexi y o de o he da a
p o ided.
In o de o ain a machine lea ning model he i s equi emen is a aining da a
se ha consis s o a la ge numbe o sol ed cases wi h he inpu da a and he desi ed
ou pu o be p oduced. This se mus be la ge enough o he algo i hm o lea n how o
sol e he p oblem and no he indi idual cases in he lis . A he same ime he da ase
mus ha e a good balance o di e ence among cases. Wi h cases oo di e en i won'
be able o p edic hem wi h su icien p ecision o be use ul bu i hey a e e y simila i
won' be able o p edic new cases wi h he expec ed p ecision. I is also impo an o
ha e he ain da a be as simila as possible, i no equal o he eal da a his model will
ace in i s end applica ion. This will ensu e ha he aining p ocess and obse ed
p ecision will apply co ec ly o he eal cases.
The las pa be o e aining is deciding wha model will be used o his p ocess
and designing i s inne implemen a ion, his is pa ly dependen on he inpu and ou pu
da a, as well as he cha ac e is ics o he in o ma ion i will p ocess. Bu i is no a i ial
p ocess and i equi es a lo o oom o ial and e o on he de elope side in o de o
maximize i s po en ial. Du ing his pape he e exis wo di e en p oposals o model
implemen a ions, one based on neu al ne wo ks and he o he based on eg ession. This
chap e and he nex one will desc ibe each o he implemen a ions espec i ely bu
23

be o e di ing in o he i s model implemen a ion he nex sec ion will explain how he
aining da a used o bo h models was ob ained.
4.1 Pseudo- andom gene a o o aining da a
As p e iously men ioned, aining da a is one o he mos impo an pa s o
conside when sol ing a p oblem by using a i icial in elligence algo i hms based on
supe ised au oma ic lea ning. Fo his p ojec he e was no eal da a collec ion
a ailable o use as he aining da a, his could be ga he ed o example om an online
judge du ing a se amoun o ime. Bu gene a ing his eal da a by hand is oo cos ly so
his op ion was comple ely disca ded.
The only iable solu ion le unexplo ed was o gene a e syn he ic da a o he
aining p ocess by implemen ing a p og am wi h hese speci ica ions. Then une he
p og am in o de o p oduce da a as close o eal measu emen s as possible. This can
be achie ed by applying di e en noise pe cen ages, mul iplica i e cons an s o sizes
among o he pa ame e s.
The implemen a ion o his p og am akes as a basis he meaning behind
complexi y o de s, hey a e unc ions ha ep esen he execu ion cos o a p og am
gi en an inpu leng h. The complexi y o de o an algo i hm may be ep esen ed as
O( (n)) whe e (n) is a ma hema ical unc ion ha depends on n, he inpu size. The e
exis an in ini e numbe o complexi ies, as an algo i hm's cos may be ep esen ed by
any unc ion. Bu hey a e g ouped in o complexi y o de s o cla i y how he cos g ows
compa ed o he inpu size o he cases p ocessed by he algo i hm.
Now le 's discuss he ac ual unc ion ha desc ibes he complexi y, (n). These
unc ions a e also in ini e so in o de o analyze hem, we look a he elemen s
depending on n i con ains. Fo example, le 's ake his unc ion (n) = 2*n*log(n) + 3, in
o de o ca ego ize i in o a complexi y o de i s we would iden i y and emo e any
alues ha a e no dependen on he inpu a iable. This simpli ies he unc ion o
(n)=n*log(n), now we can easily ca ego ize his unc ion in o he linea loga i hmic
o de . This is e e ed o as BigO no a ion and i na ows down he amoun o possible
o de s d as ically. Mos o he algo i hms implemen ed o sol e p oblem s a emen s in
online judges all in o one o hese ca ego ies, which will be he ones conside ed by he
classi ie algo i hms implemen a ions p oposed in his pape :
●O(1) - Cons an
●O(log(n) - Loga i hmic
●O(n) - Linea
●O(n*log(n)) - Linea Loga i hmic
24
●O(n2) - Quad a ic
●O(n3) - Cubic
The objec i e o he complexi y o de classi ie , as i s name implies, is o
de e mine in which o hese ca ego ies an e alua ed solu ion alls in o, gi en a se o
samples con aining pai s o execu ion ime and inpu size.
The pseudo andom gene a o hen needs o be able o gene a e hese se s o
execu ion ime and size o each o he complexi y o de s conside ed by he classi ie .
To achie e his i s i is necessa y o ealize wha makes a se o execu ion ime and size
pai s belong o a complexi y o de . When in e p e ed as poin s in a wo dimensional
g id, hey mus d aw a line o cu e ha is based on he one d awn by he unc ion ha
ep esen s he complexi y o de i belongs o.
In o de o p oduce he syn he ic aining da a, he gene a o p og am will i s
calcula e ma hema ical unc ions simila o he o iginal unc ions ha desc ibe each
complexi y o de . Taking hese unc ions, i will calcula e hei alue a a ce ain numbe
o poin s and compose in his manne a se o execu ion ime and size pai s o be
added o he aining da ase , and also add he complexi y o which hey belong. This
p ocess would gene a e a se o aining cases a oo ideal, his is a p oblem because
as p e iously men ioned in sec ion 2, ime measu emen s a e ull o noise and
impe ec ions. So his p og am mus be able o ep oduce hese impe ec ions in he
da a i gene a es, o achie e his beha io he p og am in oduces noise in o he alues
gene a ed.
I is impo an o no e ha a second e sion o his p og am was also
implemen ed, sha ing mos o he ideas desc ibed so a in his sec ion bu wi h a small
di e ence. Ins ead o gene a ing he execu ion ime alue by ma hema ical ope a ions
based on he complexi y o de chosen, he p og am pe o ms a loop o ha complexi y
and inside i makes an a i hme ic ope a ion, all while measu ing he execu ion ime. Fo
example, in o de o gene a e a linea es case, he p og am i s chooses an ope a ion
o pe o m, o example he loga i hm o a h ee digi numbe . Then i pe o ms his
ope a ion n imes, o simula e a linea complexi y and measu es he execu ion ime.
Pe o ming his ope a ion mul iple imes ends up building a aining sample simila o he
ones ob ained by he o he p oposed implemen a ion. This app oach p oduces esul s
a mo e simila o eal da a, bu i akes a lo mo e ime o gene a e hese esul s o
highe complexi ies.
Bo h o he desc ibed implemen a ions p oduce da a ollowing he same o ma ,
i gene a es a ile ha con ains one case pe line, each line con ains a se o execu ion
ime measu emen s and he size used as well as he complexi y o de hey belong o.
25
Du ing he es ing and implemen a ion phase o bo h implemen a ions
desc ibed in his pape , he e ha e been se e al ain da ase gene a ions, anging
om small iles conside ing only one complexi y o de o la ge ones wi h all o hem. The
la ges iles con ained a ound 4 million cases and he smalles a ound 12.000.
4.2 Classi ie based on neu al ne wo ks
A e sol ing he aining da a p oblem desc ibed in he p e ious sec ion, we will
ocus again on he complexi y o de p edic o , speci ically in he i s implemen a ion
ha is based on a neu al ne wo k model. This model will use he gene a ed ain da a in
o de o lea n how o p edic complexi y o de s based on ime measu emen s and sizes,
aiming o achie e he maximum possible accu acy.
As s a ed in he in oduc ion, his sec ion will co e how a neu al ne wo k model
was implemen ed in o de o de e mine a solu ion’s complexi y. In o de o de ine a
model o his kind, you need o de ine he h ee main pa s i is composed o :
●Inpu laye : he shape o his laye de ined by wha da a he model will ecei e in
o de o gene a e p edic ions.
●In e nal laye s: he in e nal s uc u e o he model, his is in cha ge o ans o ming
he inpu da a, h ough di e en kinds o ope a ions, in o he ou pu da a.
●Ou pu laye : his laye ’s s uc u e is de ined by he in o ma ion ha he model
will gene a e as a esul .
As we ha e de ined in he aining da a, he model will ecei e a se o
execu ion ime and size pai s, so he model will ha e wo inpu s pe pai . The numbe o
pai s used in his implemen a ion is h ee, as his is he lowes possible numbe o poin s
needed o di e en ia e a cu e om a s aigh line. Inc easing his numbe would
imp o e he model’s capabili ies o p edic wi h g ea e accu acy, bu i also g ea ly
inc eases he cos , as each pai needs o be execu ed and measu ed. Fo his eason
we will s a by assuming ha h ee measu emen s a e enough, and we will de ine he
inpu laye o ou model wi h six inpu s.
Rega ding he ou pu laye , ou model needs o de e mine o which o he
suppo ed ca ego ies he gi en inpu belongs. Usually neu al ne wo ks ou pu a nume ic
alue, and o his speci ic case, a nume ic alue could be assigned o each possible
complexi y and in e p e hem a e . Bu he e exis s a much be e app oach usually
used o p oduce his kind o ou pu om a neu al ne wo k classi ie , his was he chosen
solu ion. I consis s o ha ing as an ou pu an a ay o numbe s, one o each o he
possible ca ego ies he inpu may belong o, showing he p obabili y o he inpu
belonging o he ca ego y he numbe ep esen s. All he numbe s in he lis ange hei
26
alue be ween ze o and one; also he sum o all his se o numbe s should be one. The
ad an ages o his app oach agains assigning each ca ego y a nume ical alue and
ha ing only one ou pu is ha i p o ides mo e in o ma ion abou he p edic ion. In he
case o one nume ical alue i can be ha d o co ec ly in e p e a decimal alue, no
knowing among which ca ego ies he p edic o is doub ing. On he a ay app oach,
you can easily see wha chance each possible ou come had and ea his in o ma ion
as you see i . Fo hese easons, he ou pu laye o he model con ains six laye s, one
o each o he complexi ies conside ed in his p ojec .
Finally le s discuss he inne laye s uc u e o he model, his is whe e mos o he
choices lay and wha will mos ly de e mine he pe o mance o he algo i hm. As he e
a e many a ailable op ions and he e is no way o know which sui s his p oblem bes ,
he chosen app oach was o es di e en kinds o laye s and s uc u es. Is du ing his
p ocess whe e he p e iously ob ained aining da a s a s o come in o play, i s he
da ase ge s spli ed in o wo g oups, a aining se and a es ing se , usually a a 70-30
a io. Then he model is ained wi h he aining se , composed o mos o he da a;
and e alua ed wi h he es ing se , ha is unknown o he model a his poin . This
p ocess in ends o show he accu acy o he model du ing aining bu also when
p esen ing i wi h new es cases ha ha e ne e been e alua ed be o e.
Fo his ial p ocess he gene a ed da ase s anged om 400.000 es cases o
4.000.000, wi h noise ange alues om 5 - 25 %. Du ing his p ocess i was also aken in o
conside a ion emo ing some o he mo e a ely seen complexi y o de s such as cubic
o cons an complexi ies o y o imp o e he obse ed esul s. Bu accu acy sco es
anged be ween 50 - 80% a bes .
Also di e en laye ypes and amoun s we e conside ed, as well as he amoun
o neu ons pe laye . Rega ding laye ypes, LSTM and GRU we e he bes pe o ming
ones, as hey shine he mos when add essing p oblems ela ed o sequen ial da a, as
a e ime se ies used in his classi ica ion p oblem. S acked laye s o hese ypes a e
capable o ex ac ing complex pa e ns in he p ocessed da a, as may be he
complexi y in which ime inc eases in espec o size. LSTM laye s a e a mo e complex
e sion o GRU laye s, hey can ex ac mo e complex in o ma ion om he inpu da a
a a highe esou ce cos . Bu ha ing conside ed models wi h bo h o hese laye ypes
as well as simple Dense laye s, he inc ease in accu acy was no enough in o de o ind
hese models iable. Rega ding he amoun o neu ons pe laye , es s ha e anged
om small laye s wi h 8-12 neu ons o la ge ones up o 200. Again he esul s ha e no
been e y p omising, wi h 64 neu ons pe laye ob aining close o he bes accu acy
while keeping he esou ce cos much lowe . Finally s acking laye s is ano he impo an
pa o de ining he inne s uc u e o a neu al ne wo k, es s ha e anged om one e y
la ge laye , e en conside ing 1000 neu ons in his case, o s acking i e o en smalle
27
laye s wi h he neu on amoun s p e iously discussed. In his ma e , he bes
comp omise be ween esou ce cos and accu acy was ou laye s wi h 64 neu ons
each.
All o he p e iously men ioned models we e implemen ed and es ed using
no ebooks in Py hon, as i p o ides easy access o neu al ne wo k lib a ies wi h a wide
a ie y o high le el choices a disposal. The chosen lib a y was Ke as o ease o use
and documen a ion a ailable.
As a conclusion o his sec ion, he analysis pe o med we e e y disappoin ing
and i was comple ely disca ded as a new app oach was disco e ed. This new solu ion
had a mo e p omising esul s, e en in he ea ly s ages and i will be discussed in he
ollowing chap e .
28

Chap e 5 - Complexi y p edic o based on
eg ession unc ions
As p e iously discussed in his pape , eg ession p oblems aim o es ima e alues
based on p e iously eco ded da a. In au oma ic lea ning, hey ecei e an inpu
da ase and hei goal is o p edic eal alues no included in he inpu in o ma ion.
One app oach o sol e hese kinds o p oblems is o design a solu ion using
eg ession unc ions. The idea behind hese unc ions is o assume ha he da a he
p oblem is ying o p edic ollows a ma hema ical unc ion, hen by inding his
unc ion and sol ing i o any inpu da a i will ou pu he desi ed p edic ion as a esul .
In o de o ind he ma hema ical unc ion, i s you need o igu e ou he class o he
ma hema ical unc ion you wan o use o gene a ing he p edic ions, hese classes
a e o example linea , polynomial o exponen ial among o he s. Once chosen a class,
he idea is o ind a cu e equa ion inside his ca ego y o unc ions ha bes i s he
inpu da ase , also known as he aining da a. This may be done in mul iple ways, one
o he mos common app oaches is o minimize he mean o he squa ed e o s ha he
unc ion p oduces on each o he inpu s con ained in he aining da ase . The main
idea is o de ine a gene ic unc ion o he chosen ca ego y and ine une he
pa ame e s i con ains in o de o minimize he p e iously men ioned e o . Fo example,
when ea ing eg ession p oblems and choosing he linea unc ion class you would
decla e a gene ic linea equa ion cu e as y = ax + b. Then he linea eg ession
unc ion would p ocess he da ase o he pa icula p oblem and igu e ou he bes
alue o he pa ame e s aand b. Now o gene a e p edic ions o new alues you
need o sol e he p e ious unc ion subs i u ing xwi h he new inpu da a, aand bwi h
he alues ou pu ed by he ained linea eg ession unc ion and he esul ywould be
he p edic ion.
I is impo an o no e ha he p oblem unde e alua ion in his sec ion is a
classi ica ion p oblem, as we need o de e mine he complexi y o de a gi en solu ion
belongs o. A i s sigh eg ession is no he bes app oach o sol e his p oblem bu in
eali y complexi y o de s a e closely ela ed o ma hema ical unc ions, as hey a e
exp essed as cu es. The idea behind his implemen a ion is o ake he measu emen s
ob ained om execu ing an use 's solu ion as poin s in a g id and ind he cu e ha
desc ibes hem bes . This is done by de ining a se o complexi y o de s suppo ed by
he module, hen aining a eg ession unc ion o each o hem and selec ing he one
wi h he leas e o s gene a ed while p edic ing he inpu da a. We won' use eg ession
unc ions in o de o p edic new da a, as hey usually a e u ilized bu ins ead we will use
29
hem o i a cu e o he cu en da a and ex ac he o de o he unc ion ha
desc ibes his cu e.
The implemen a ion o he p oposed sys em ha is based in eg ession unc ions
s a s by de ining a se o suppo ed complexi ies, which will be he possible esul s o
each ca ego iza ion pe o med. The ollowing lis desc ibes he conside ed o de s in he
code implemen a ion as well as he unc ions used o each o hem:
●Cons an : y = a
●Loga i hmic: y = a + b * log(x)
●Linea : y = a + b * x
●Linea Loga i hmic: y = a + b * x * log(x)
●Squa e: y = a + b * x^2
●Cubic: y = a + b * x^3
The implemen a ion de ines as he X a iable he size ha will se e as he inpu ,
and he Y a iable as he execu ion ime ha will se e as he ou pu alue. The
e alua ion p ocess hen begins by i ing each o he p e iously desc ibed unc ions
using eg ession, his ou pu s he unknown pa ame e s as a esul . Then using he new
unc ion ob ained by subs i u ing he pa ame e s o hei calcula ed alues, he inpu
a iable X is ed again and he p edic ed esul s a e s o ed. A e ob aining his
in o ma ion he eal Y da a and he p edic ed Y da a a e used in o de o calcula e he
esidual sum o squa es. This esul is used o compa e all he conside ed unc ions,
choose he one wi h he leas e o as he bes op ion and use i s unc ion class as he
p edic ed complexi y o de o he e alua ed solu ion.
The only excep ion du ing his p ocess is he cons an complexi y, in his conc e e
case he p og am i s a linea eg ession unc ion using he inpu da a and calcula es
he equa ion o he cu e. Then i analyzes he slope o his cu e, i i is lowe han a
p ede ined alue, 0.1 o he cu en implemen a ion, i e alua es he solu ion as
cons an . This check is pe o med be o e ca ying ou he p e iously desc ibed
e alua ion p ocess, which ge s skipped i he unc ion is classi ied as cons an .
To inalize his sec ion i is in e es ing o men ion ha smoo hing he da a be o e
p ocessing i was aken in o conside a ion, like o example using he sa gol_ il e ()
as an ini ial ans o ma ion. The esul s obse ed using his kind o ans o ma ions we e
wo se and p ecision was los du ing he smoo hing p ocess so i was comple ely
disca ded du ing de elopmen .
30
Chap e 6 - Valida ion o he complexi y p edic o
module based on eg ession
The alida ion p ocess o he clue module desc ibed in his pape has been
ca ied ou in wo phases, an ini ial alida ion o he complexi y p edic ion sys em and a
second alida ion aking in o accoun he whole execu ion low o he clue module. In
he i s phase, he goal is o e i y how p ecisely he p edic o can gene a e he co ec
o de o complexi y o a eal solu ion p og ammed by a use . In he second s age, he
ocus changes o he classi ica ion o he solu ion among he di e en ypes o TLE
e dic s desc ibed a he beginning o his pape .
Fo all o he alida ion p ocess we will use eal wo ld solu ions designed and
implemen ed by use s ga he ed om he in e ne in public domains. These solu ions a e
de eloped o sol e p oblems in he online judge ¡Acep a el e o! Also he da ase s used
o es hese solu ions a e gene a ed based on he p oblem s a emen s in he same
judge’s collec ion.
E o s a e calcula ed by s ic ly compa ing i he p edic ed complexi y o de
equals he expec ed one, bu in some cases his may no be he only pa h o a
success ul classi ica ion. Fo example, gi en a solu ion o quad a ic complexi y o a
p oblem whose wo s accep ed complexi y is linea , le 's suppose ha he p edic o
p og am ob ains a cubic complexi y on he e alua ion. The ca ego y ob ained by he
complexi y o de p edic o is w ong bu he ob ained esul om he clue module as a
whole would be co ec . Taking hese esul s in o accoun , he clue module would
classi y he solu ion as a w ong complexi y TLE and gi e he igh clue o he use . This is
impo an as e o s calcula ed du ing he alida ion p ocess desc ibed in his chap e
a e s ic , bu calcula ing he use ul e o in his manne may be e desc ibe he ac ual
p ecision o he module.
6.1 Gene ic alida ions
In o de o alida e any complexi y p edic ion sys em i is i al o pe o m he es s
wi h da a ob ained om eal wo ld scena ios. Da a ga he ed in his manne gi es a
be e image o i s pe o mance when used in a eal judge online as i is no pe ec
and con ains noise al e a ions.
The i s s ep in his p ocess is choosing a numbe o p oblems om an online
judge, in his case we will use ¡Acep a el e o! I 's also necessa y o ind mul iple solu ions
o each o he chosen p oblems in o de o alida e he module wi h a a ie y o
31
algo i hms wi h di e en execu ion cos s inside he same complexi y o de s. To ob ain
he solu ions i s an exhaus i e sea ch is ca ied ou online in gi hub, his way i is
possible o ind a mul i ude o public solu ions o p oblems o he chosen judge. A e
ga he ing enough p oblems, each wi h a ound se en di e en solu ions and in di e en
languages, a es case gene a o is needed o each o he p oblems. This p og am
mus be capable o gene a ing alid inpu da a o a chosen p oblem s a emen gi en
a desi ed size as an inpu . To inalize his ga he s ep, each solu ion mus be compiled
and execu ed wi h he gene a ed es cases measu ing hei execu ion ime, all hese
esul s a e hen s o ed in a ex documen o la e use.
A e ga he ing all he eal da a necessa y o he alida ion he es o he
p ocess is ai ly simple, i consis s o p ocessing all he collec ed da a wi h he p edic o
module and measu ing i s pe o mance. This is also a good momen o ine une he
classi ica ion algo i hm aking in o accoun he ob ained esul s in o de o maximize i s
p ecision.
This i s able below shows he p oblem ex ac ed om he judge ¡Acep a el
e o! I con ains he p oblem id in he judge, i s complexi y o de in bigO no a ion, he
numbe o solu ions ob ained in Ja a and C++ and he hi pe cen in he p edic ions
ob ained by he classi ica ion algo i hm. The e o s ob ained ega ding he p oblem
wi h id 140 should ha e e u ned a linea complexi y bu we e p edic ed as cons an .
This is jus i iable because he p oblem is in ac linea in espec o he numbe o digi s
o he inpu da a bu he maximum leng h de ined by he p oblem is e y small, his
being nine digi s. Wha his means is ha he di e ence be ween execu ions o di e en
inpu da a sizes is oo small o he complexi y p edic o o ealize.
#
Nomb e
Complexi y
Nº Solu ions
Hi %
C++
Ja a
140
Suma de Digi os
O(N)
5
2
42%
151
¿Es ma iz
iden idad?
O(N2)
3
3
100%
368
Cociendo
hue os
O(1)
5
1
100%
369
Con ando en la
a ena
O(N)
4
2
100%
32
o hei judge. This way hey would be able o ob ain a la ge enough sample o eal
wo ld da a and use i in o de o ain an AI classi ie model capable o su passing he
implemen a ion explo ed in chap e 4.
To inish his sec ion and coming back o he in e nal complexi y o de p edic o
i could be in e es ing o inc ease he amoun o single a iable complexi ies
conside ed in o de o ma ch all he complexi ies exis ing in mos o he cu en ly
a ailable online judges.
39

Chap e 8 - Bibliog aphy
1. Buglione, L., Palomba, F., & Panichella, S. (2019, May). How Accu a e A e Online
Judges in De ec ing De ec s in Code Submissions?. In 2019 IEEE/ACM 41s
In e na ional Con e ence on So wa e Enginee ing: So wa e Enginee ing
Educa ion and T aining (ICSE-SEET) (pp. 153-162). IEEE.
2. “Web-Based Online Judge Sys em o Online P og amming Educa ion" by E.
Co ea, L. Fuen es, D. Flo escu, and L. Popa.”
3. "A S udy o he Measu emen o Execu ion Time in P og am Benchma king" de
Gaius Mulley y Jon Shapi o, publicado en la e is a ACM SIGARCH Compu e
A chi ec u e News
4. "Bes P ac ices o Scien i ic Compu ing" de Wilson e al., publicado en la e is a
PLOS Biology.
5. Gómez Ma ín, Ma co An onio; Gómez Ma ín, Ped o Pablo. “Uso de so wa e de
ges ión de concu sos de p og amación pa a e aluación con inua”. En: Ma qués
And és, Me cedes; Badía Con elles, José Manuel; Ba achina Mi , Se gio (eds.).
JENUI 2013. Ac as de las XIX Jo nadas sob e la Enseñanza Uni e si a ia de la
In o má ica, Cas ellón, del 10 al 12 de julio de 2013. Cas elló de la Plana:
Publicacions de la Uni e si a Jaume I, 2013. ISBN 978-84-695-8051-6, pp. 293-300.
6. Tu ing, A. M. (1937). On Compu able Numbe s, wi h an Applica ion o he
En scheidungsp oblem. P oceedings o he London Ma hema ical Socie y Se ies
2, 42, 230-265.
40