text:
## 2019 IOI Team

We are happy to present the Philippine team to this year’s International Olympiad in Informatics, to be held in Baku, Azerbaijan from August 4 to 11. They will represent the country in the world’s most prestigious computing competition for high school students.

Dan Alden Baterisna
grade 11, De La Salle University Senior High School

Dan likes playing with all things tech. Between school and practice, he is busy learning the intricacies of the bottom lane and watching speedrun videos online. He plans on studying computer science in college and hopes to give back to the competitive programming community, especially in the Philippines. He won a silver medal at the IOI in Tsukuba, Japan in 2018.

Dion Stephan Ong
grade 11, Ateneo de Manila Senior High School

Dion has dabbled in math for a while. In elementary and high school, he was the national winner of the Metrobank Math Challenge. This year, he will compete in the International Mathematical Olympiad. Lately, he discovered informatics and found the shift to algorithms instinctive. In college, he plans to pursue computer science to develop smart cities.

Steven Reyes
grade 10, Saint Jude Catholic School

Steven first discovered programming around 5 years ago when he created circuits and logic gates in Minecraft. Creating these contraptions are like solving computational problems, both of which he enjoys indulging in. The joy he finds in problem-solving extends to the different math, science, and programming competitions he participates in, and even to teaching fellow schoolmates how to approach various kinds of puzzles.

Ron Mikhael Surara
grade 11, Philippine Science High School – Bicol Region Campus

Miko initially joined NOI for the freebies but continued to pursue it as he grew to love solving algorithmic problems. He has been joining the NOI for four years, always shortlisted for the IOI team in every attempt. Formerly, he was President of the Advanced Programming Club (APC) in his school. Although not a member of this club anymore, he still teaches younger aspiring students. When he’s not solving algorithmic problems, he plays games such as LoL and Osu with his friends and reads manga and books. He also likes to watch anime, series, and movies. He also has interests in drawing and calligraphy, as well as in sports, especially table tennis and lawn tennis. He plans to take computer science in college and use his programming skills to help improve other fields in science and technology.

## 2019 National Finals

The NOI.PH 2019 National Finals was held in Ateneo De Manila University’s Faura Hall last 6 – 7 April 2019. The 28 official finalists competed over two five-hour rounds, each of which consisted of five problems.

Invited to participate in the finals were the top 30 at the NOI.PH 2019 National Eliminations, a 222-hour online competition held last 18 – 27 January 2019, where 141 students from all over the country solved fourteen problems of varying difficulty.

Students who almost made it to the top 30 also made it as observers. Philippine Science High School Bicol Region Campus (PSHS BRC), coached by Mr. John Rainer Joaquin, had more than six students who scored high enough in the national eliminations. Thus, the top six students from the school attended as official participants.

This year’s observers were Adalbert Apuya, Lance Benedict Cabrera, Jose Enrique Ramirez and Ralph Richard Yanto. All are incoming Grade 10 students of PSHS BRC, and they have set themselves up for success in the next few years by gaining experience on what the national finals feels like.

In the NOI.PH, finalists tested their endurance by solving five challenging programming tasks during each day’s five-hour session. Contestants used their programming and analytical skills to create data structures and algorithms to solve each task using a program.

## Events

The first day of the contest started with the opening ceremonies. NOI.PH President Vernon Gutierrez began with a speech, and said “We’re here because we love solving problems. Let’s all have some fun this weekend!”

He also discussed the rules to the competition and some notes on using the compiler before the Practice Round of the competition. In the Practice Round, students spent 90 minutes familiarizing themselves with the computers through solving some problems.

After lunch, the first round of the finals began. A mirror of the problems began shortly after. During Round 1, the NOI.PH Organizing Team held a short meeting with the coaches to discuss the state of competitive programming in their respective high schools.

Round 2 began in the morning of the second day, with a mirror contest being held again. Lunch was served after the end of the round, and NOI.PH Head Judge Kevin Atienza discussed the solutions to the problems after lunch.

Finally, the awarding was held, and the top three students won the surprise prize of a free shirt, containing source code overlaid on an NOI logo.

## NOI.PH Finals Round 1

Round 1’s friendly rivalry began with Magkaribal sa Arnibal. Vincent Dela Cruz made the first submission within twelve minutes, getting 40 points. The first full solution was from Steven Chua two minutes later. By the end of the contest, twenty-five of the finalists solved the problem completely.

The Room was not a problem that teared contestants apart. In fact, of the twenty-one contestants who attempted the problem, ten solved the first subtask to get 30 points. Steven Reyes and Dion Ong solved the second substask as well to get 69 points, while Ron Surara and Dan Baterisna managed to solve the problem completely. Good thinking!

Sixteen competitors submitted code for Baby Come Bak, with five of them getting nonzero scores. Vash Ancheta and Clyde Borrega solved the second subtask to get 6 points, while Ron solved the third subtask to get 22 points. After several submissions scoring less points, Dan and Steven C. came back to Baby Come Bak to solve both the second and third subtasks to get 28 points.

Tower Bloxx was not only a popular game, but a popular problem for contestants to try with twenty-three submissions. It’s the first partial scoring task to appear in the NOI.PH Finals. Twenty submissions managed to get a nonzero score. Eight of these scored at least 20 points, with AC Mabute scoring the highest at 48.94 points. AC not only topped the towers, but he also topped the problem.

Two contestants submitted submitted code for Sumbong Centers, but unfortunately, no one managed to solve for the number of solb sets and get a nonzero score.

## NOI.PH Finals Round 2

When it comes to programming, contestants are logging prepared! Illegal Logging saw quick full solves from Ryan Shao, Raphael Dalida, and Rae Samonte within the first seven minutes. Twenty-six of the finalists got a nonzero score, with twenty-three of them solving the problem fully.

Among the twenty-one participants who played the role of Mr. Kupido, sixteen got a nonzero score. Of these, eight got 6 points and four got 12 points. Frederick Tan and Ryan got 21 points, while Vincent and Steven C. were the best matchmakers, both getting 27 points.

Fifteen participants submitted code to BATIBots. Rae, Steven C., and Vincent Dela Cruz solved the first subtask to get 17 points, while Dion, Ryan, Ron, and Steven R. solved the first two subtasks to get 32 points. Dan demonstrated his Brainy Augmented Transcendental Intelligence by solving enough subtasks to get 62 points.

Sorting the Planets saw fifteen students submitting code. Only three participants got nonzero scores: Dion solved the first two subtasks to get 29 points, while Ron and Dan solved the first three subtasks to get 40 points. Hopefully these students will continue to follow Kevin’s example.

Finally, only four students attempted to draw their own Cartogram to a better place. Vincent did not take a fall on the road, and followed the cartogram that lead to a nonzero score of 19 points.

## Photo Gallery

Special thanks to Joan Francisco for contributing pictures.

## Scoreboard for the NOI.PH 2019 National Finals

RankNameScoreGradeSchoolCoachRegionUsernameMagkaribal sa ArnibalBaby Come BakTower BloxxThe RoomSumbong CentersIllegal LoggingBATIBotsMr. KupidoSorting the PlanetsCartogram
1Dan Alden Baterisna480.5411De La Salle University - TaftNCRDBaterisnaPH191002844.54100100626400
2Ron Mikhael Surara429.3211Philippine Science High School - Bicol Region CampusJohn Rainer JoaquinVRSuraraPH191002229.3210010032640
3Dion Stephan Ong360.4411Ateneo de Manila Senior High SchoolNCRDOngPH1910018.4469100321229
4Steven Reyes357.310Saint Jude Catholic SchoolNCRSReyesPH1910044.36910032120
5Steven Chua32211British School ManilaNCRSChuaPH191002820301001727
6Vincent Dela Cruz309.6610Valenzuela City School of Mathematics and ScienceNCRVDelaCruzPH19100046.66001001727019
7Ryan Mark Shao30312Xavier School San JuanNCRRShaoPH19100203010032210
8Gregory William Joseph Liu283.8412Philippine Science High School - Central Visayas CampusFelix CalvoVIIGLiuPH19100047.8430100060
9Al Christian Mabute278.9411Philippine Science High School - Bicol Region CampusJohn Rainer JoaquinVAMabutePH19100048.943010000
10Frederick Ivan Michael Tan269.69Philippine Science High School - Main CampusNCRFTanPH1910018.6301000210
11Rae Gabriel Samonte266.7411Philippine Science High School - Bicol Region CampusJohn Rainer JoaquinVRSamontePH19100019.74301001700
12John Eric Estrada261.099Philippine Science High School - Bicol Region CampusJohn Rainer JoaquinVJEstradaPH19100019.09301000120
13Marc Joshua Ayalde255.4111Philippine Science High School - SOCCSKSARGEN Region CampusSheena Dawn FerrarenXIIMAyaldePH1910019.413010006
14Raphael Dylan Dalida2368Philippine Science High School - Main CampusNCRRDalidaPH19100030100060
15Daniella Joan Francisco23010Philippine Science High School - SOCCSKSARGEN Region CampusSheena Dawn FerrarenXIIDFranciscoPH191000301000
16Kirby Chua225.2512Xavier School San JuanNCRKChuaPH19100019.25010006
17Clyde Lawrence Borrega221.669Philippine Science High School - Bicol Region CampusJohn Rainer JoaquinVCBorregaPH1910069.6600100060
18Philmon Sedrick Wee219.5711Xavier School San JuanNCRPWeePH1910019.5701000
19Sheen Santos Capadngan219.079Philippine Science High School - Central Visayas CampusFelix CalvoVIISCapadnganPH1910019.071000
20Allen Adrian Solis217.8511Philippine Science High School - SOCCSKSARGEN Region CampusSheena Dawn FerrarenXIIASolisPH19100017.8501000
21John Angelo Oringo2129Philippine Science High School - Bicol Region CampusJohn Rainer JoaquinVJOringoPH191000010012
22Clyde Courtney Jallorina201.4612Philippine Science High School - Main CampusNCRCJallorinaPH1910001.461000
23Mark Angelo Landingin20011Philippine Science High School - CAR CampusPablo Viloria, Jr.CARMLandinginPH1910001000
24Justin Tan17612Ateneo de Manila Senior High SchoolNCRJTanPH19100076
25Vaughn Matthew Valle1049Philippine Science High School - Central Visayas CampusFelix CalvoVIIVVallePH191004
26Michael Jay Zamoras4410Philippine Science High School - Eastern Visayas CampusCary Von AlanoVIIIMZamorasPH1940040
27Vash Patrick Ancheta25.0711Philippine Science High School - CAR CampusPablo Viloria, Jr.CARVAnchetaPH190613.07006
28Mark Nicholas Cagas010Manila Science High SchoolRomer AbellaNCRMCagasPH1900

## Final Message

Congratulations to all the winners of the National Olympiad in Informatics – Philippines 2019 Finals!

The organizing committee would like to thank our host, the Ateneo de Manila University, for their generous support in providing the venue and infrastructure to hold the event. Special thanks to the ADMU DISCS technical staff for providing logistical support.

We would also like to thank our volunteers from ADMU ProgVar and UP ACM, as well as our testers and illustrators for helping out.

Lastly, we thank all the coaches, parents, and students for their participation and hard work and for making this event a success. We hope for your continued support as we move to the selection of our delegation to the International Olympiad in Informatics 2019, to be held in Baku, Azerbaijan, this August.

## 2019 Singapore NOI

Six Filipino students bagged medals in Singapore’s 22nd National Olympiad in Informatics held last March 23, 2019 at the National University of Singapore.

Dan Alden Baterisna won a gold medal, making this his second year in a row of winning gold after last year’s performance. Ron Mikhael Surara, Dion Stephan Ong, and Steven Chua won silver, while Clyde Lawrence Borrega and Raphael Dylan Dalida won bronze.

Dan’s win is the country’s third gold medal from the Singapore tilt; with Robin Christopher Yu being the country’s first gold medalist. The haul marks Ron’s and Dion’s second silver medals. Among the delegation, Steven, Clyde, and Raphael ranked well despite being first-timers to the competition.

Students from Singapore joined with participants from other foreign countries, including the Philippines, Indonesia, Malaysia, Thailand, and Vietnam. The Philippines has been joining the Singapore National Olympiad (NOI.SG) ever since they opened the contest to foreign participants back in 2016.

The six students were chosen based on their scores in the Singapore NOI Preliminary Round, where they ranked the best among all Filipino participants. The students were accompanied by NOI.PH trainers Vernon Gutierrez and Robin Yu, along with several other coaches and parents.

The contest consisted of a five-hour session consisting of five problems, held in the I³ Building of the campus. Each contestant must write a program that outputs an answer to the problem given a set of inputs, following the constraints given in the problem’s statement.

A practice round was held the previous day, on March 22, 2019. Other events were also held, such as Capture the Flag, a computer security competition where participants apply their programming skills to challenges in web, networking, reverse engineering, cryptography, and related fields. Dan placed within the top ten in this event and won a power bank.

## Photos

Photos from Vernon Gutierrez.

## 2019 National Eliminations

The NOI.PH 2019 National Eliminations started on 6:00 PM of 18 January 2019 and finished on 11:59 PM of 27 January 2019. It consisted of fourteen problems of varying difficulty.

## The Participants

Among the 209 registrants, 141 participated in the 222-hour online competition. The participants came from 23 different schools from all over the country. Moreover, each of the main island groups of the Philippines were represented.

Luzon, except NCR (47) | Visayas (33) | Mindanao (17) | NCR (44)

Broken down by region, we have the following chart:

CAR (5) | I (5) | II (1) | III (10) | V (26) | VI (8) | VII (5) | VIII (20) | XI (4) | XII (13) | NCR (44)

Broken down by grade level, we have the following chart:

Grade 8 (20) | Grade 9 (21) | Grade 10 (53) | Grade 11 (32) | Grade 12 (15)

## The Problems

The contest problems are accessible at https://www.hackerrank.com/noi-ph-2019. Each individual problem page also contains the solution (“Editorial”) for that problem. The problems remain accessible for practice after the contest.

## NOI.PH 2019 Onsite Final Round Official Contestants

In no particular order, here is the list of students who qualify for the NOI.PH 2019 Onsite Final Round as official contestants. Participants who may be invited as observers are not shown in this list.

• Al Christian Mabute (Grade 11)
Philippine Science High School – Bicol Region Campus
Coach: John Rainer Joaquin
Philippine Science High School – SOCCSKSARGEN Region Campus
Coach: Sheena Dawn Ferraren
• Clyde Courtney Jallorina (Grade 12)
Philippine Science High School – Main Campus
• Clyde Lawrence Borrega (Grade 9)
Philippine Science High School – Bicol Region Campus
Coach: John Rainer Joaquin
• Dan Alden Baterisna (Grade 11)
De La Salle University – Taft
• Daniella Joan Francisco (Grade 10)
Philippine Science High School – SOCCSKSARGEN Region Campus
Coach: Sheena Dawn Ferraren
• Dion Stephan Ong (Grade 11)
Ateneo de Manila Senior High School
• Frederick Ivan Michael Tan (Grade 9)
Philippine Science High School – Main Campus
• Gregory William Joseph Liu (Grade 12)
Philippine Science High School – Central Visayas Campus
Coach: Felix Calvo
• Immanuel Josiah Balete (Grade 10)
St. Stephen’s High School
Coach: Agnes Panes
• John Angelo Oringo (Grade 9)
Philippine Science High School – Bicol Region Campus
Coach: John Rainer Joaquin
Philippine Science High School – Bicol Region Campus
Coach: John Rainer Joaquin
• Justin Tan (Grade 12)
Ateneo de Manila Senior High School
• Kirby Chua (Grade 12)
Xavier School San Juan
• Marc Joshua Ayalde (Grade 11)
Philippine Science High School – SOCCSKSARGEN Region Campus
Coach: Sheena Dawn Ferraren
• Mark Angelo Landingin (Grade 11)
Philippine Science High School – CAR Campus
Coach: Pablo Viloria, Jr.
• Mark Nicholas Cagas (Grade 10)
Manila Science High School
Coach: Romer Abella
• Michael Jay Zamoras (Grade 10)
Philippine Science High School – Eastern Visayas Campus
Coach: Cary Von Alano
• Philmon Sedrick Wee (Grade 11)
Xavier School San Juan
• Rae Gabriel Samonte (Grade 11)
Philippine Science High School – Bicol Region Campus
Coach: John Rainer Joaquin
• Raphael Dylan Dalida (Grade 8)
Philippine Science High School – Main Campus
• Richwynn Cedric Ong (Grade 10)
Xavier School San Juan
• Ron Mikhael Surara (Grade 11)
Philippine Science High School – Bicol Region Campus
Coach: John Rainer Joaquin
• Ryan Mark Shao (Grade 12)
Xavier School San Juan
Philippine Science High School – Central Visayas Campus
Coach: Felix Calvo
• Steven Chua (Grade 11)
British School Manila
• Steven Reyes (Grade 10)
Saint Jude Catholic School
• Vash Patrick Ancheta (Grade 11)
Philippine Science High School – CAR Campus
Coach: Pablo Viloria, Jr.
• Vaughn Matthew Valle (Grade 9)
Philippine Science High School – Central Visayas Campus
Coach: Felix Calvo
• Vincent Dela Cruz (Grade 10)
Valenzuela City School of Mathematics and Science

They will all advance to the Final Round in April, one step closer to the International Olympiad in Informatics 2019 (IOI 2019) in Baku, Azerbaijan!

All codes/submissions have been audited, and all scores/rankings are final.

## 2018 IOI Team

We are happy to announce the Philippine team to this year’s International Olympiad in Informatics. They will represent the country in the most prestigious informatics olympiad. The contest consists of two five-hour sessions of solving algorithmic problems and coding up solutions.

Dan Baterisna
grade 10, Colegio San Agustin Makati

Dan Baterisna is one who enjoys the social aspects of academic contests. He participates in a lot of team contests, providing his science and technology expertise in general knowledge competitions. When he’s not busy pwning algorithmic challenges, you will most likely see him pwning his friends in online games such as Rules of Survival. In the future, he plans to take up computer science with the goal of eventually working with local tech startups.

Franz Cesista
grade 12, Philippine Science High School – Eastern Visayas Campus
coach: Cary Von Alano

Franz Cesista is not content with just learning, he also enjoys sharing it to his interested peers. He shares what he learns in the countless contests and seminars by lecturing, for example, in his school’s programming club. His pursuit of knowledge manifests as well when he unwinds as he often plays complex simulation games such as Factorio. For college, he plans to study mathematics and eventually focus on artificial intelligence.

CJ Quines
grade 12, Valenzuela City School of Mathematics and Science
coach: Ruel Dogma

CJ Quines is the artsy type of scientist. His hobbies include calligraphy, ukelele, and the art of proving mathematical theorems. In fact he recently placed second in a science fair sponsored by Intel. There, he tackled a special case of an NP-complete problem related to planar graphs. He also maintains a blog where he writes about his experiences in various competitions and conferences. After college, he plans on becoming a data scientist.

Andrew Ting
grade 12, Xavier School San Juan

Andrew Ting has been drumming in his school’s pep rallies since grade school. He found his interest in programming through the game LittleBigPlanet. When he’s not beating the drums, he is likely drumming up interest in algorithms as an officer of his school’s programming club. As a student who’s into game dev, Andrew plans to transition from playing rhythm games to developing them by taking up computer science in college.

The team will be accompanied by Team Leaders Kevin Atienza and Vernon Gutierrez.

## 2018 Singapore NOI

Six Filipino students traveled to Singapore to compete in their national informatics olympiad. The delegation consisted of three Grade 12 students and three Grade 10 students. They were chosen among the top ten participants in the recently concluded NOI.PH 2018 OnSite Finals.

NOI.PH trainers Kevin Atienza and Robin Yu attended the event as the team leaders. Several coaches and supportive parents attended as well. In particular, Coach Cary Von Alano of PSHS Eastern Visayas accompanied Franz Cesista. Meanwhile, Coach John Rainer Joaquin of PSHS Bicol Region accompanied Miko Surara. In addition, Coach Edlen Sanchez of PSHS Main accompanied Kyle Dulay. The parents of the other half of the delegation attended to support their children as well.

## Results

Dan Baterisna brought home the country’s second Singapore Olympiad gold medal. He scored in all five tasks and got a perfect score for the CollectingMushrooms and Journey tasks. Dan is the first Filipino Grade 10 student to accomplish such a feat. The first Filipino gold medalist to the Singapore olympiad was Robin Yu.

The rest of the delegation all won silver medals. Andrew Ting managed is on a medal streak as he grabs his second silver medal. Second-timers Franz Cesista and Miko Surara went up the ranks. This time, both of them took home silver – a great improvement from last year‘s bronze. Despite it being their first time in the Singapore NOI, Dion Ong and Kyle Dulay perfomed quite well. They both garnered enough points to get a silver medal as well. Among the six Philippine delegates, Dion was the only one to completely solve the LightningRod task.

The medals are awarded to the invited participants are determined based on their performance in relation to the local delegation. These results are posted on Singapore’s olympiad website.

## About The Contest

The contest itself consisted of a five-hour session consisting of five tasks. Each contestant must write a program that outputs an answer to the task given any set of input values within the constraints of the problem. The program must be correct and efficient. That is, the program must output the correct answers and produce them within the allotted time limit.

The Philippines has been joining the Singapore National Olympiad (NOI.SG) ever since they opened the contest to foreign participants back in 2016. More information on the contest can be found here.

## Conclusion

All six participants got at least a silver medal. This is a first in Philippine programming. None of this would have been possible without the diligence of our students, the support provided by their coaches and parents, the training provided by the volunteers, and the help extended by our sponsors.

With everyone working together towards the growth of science education in the country, we hope to see a generation of critical thinkers especially in a time where misinformation is prevalent in society.

## Photos

Special thanks to Mr. Alex Ting and Coach John Rainer Joaquin for the photos!

## 2018 National Finals

The NOI.PH 2018 National Finals was held in Pointwest Innovations Corporation in Quezon City last 17 – 18 February 2018. It consisted of two rounds on-site, each of which consisted of five problems. It was attended by 28 official participants, 8 coaches, and 19 guests.

Students who almost made it to the top 30 also made it as observers. Philippine Science High School Bicol Region Campus (PSHS BRC), coached by Mr. John Rainer Joaquin, had more than six students who scored high enough in the national eliminations. Thus, the top six students from the school attended as official participants.

Among those invited, only Clyde Lawrence Borrega and John Eric Estrada (both from PSHS BRC) came as observers as they scored almost enough to get in the top 30. As they are currently Grade 8 students going on Grade 9, they have set themselves up for success in the next few years by gaining experience on what the national finals feels like.

## NOI.PH Finals Round 1

For the first time, there are five problems in each round instead of the usual four.

Global Warming was the hottest problem as it received the most attention from the participants. In particular, twenty-three submitted code to this problem. Dan Baterisna, Kyle Dulay and Franz Cesista managed to make their program work for all four subtasks. Ron Surara notably passed the first three subtasks, netting him 51 points for the problem.

Fourteen official participants threw in their code for Boomerang Gadget, eagerly waiting what would come back. Dan managed to finish all but the last subtask, giving him 73 points. However, the award for being the only one to complete all subtasks goes to CJ Quines. Now that the scores are official, no one can take that award away from him now.

Thrust Trials was interesting in that you either got it, or you didn’t, just like the Mayon reference located in the problem. Out of the thirteen people who submitted, only four got nonzero scores. Dion Ong and Steven Reyes managed to submit code that correctly treated all the subtasks, as well as Dan and CJ. Sister Spaceships, one of the problems in day two, rightfully congratulates Steven Reyes for being the first to submit a working solution.

A similar situation happened looking at the scores of Voltes Group. Among the six participants who submitted, Kyle and Franz managed to get full points. Interestingly, CJ managed all but the second subtask.

Finally, among the thirteen attempts at Lean on Me, only Dan, Dion, Ron, and Red Ligot managed to get a nonzero score, and all four of them managed to finish the first subtask.

## NOI.PH Finals Round 2

Problems in the second round was filled with amusing alliterations. Everyone submitted code for People Power but only Dan, Kyle, and Dion managed to make them work for all subtasks. Nine others managed until the fourth out of the six subtasks. In addition, our two observers both scored 10 points in this problem as well.

Of the twenty-one official participants who submitted code for Sister Spaceships, only Dan, CJ, and Kyle managed to get all subtasks. There were several ways to gain points for this problem. Some managed to get 23 by focusing on the third subtask, which asks to solve a special case of a problem. More notably, Alexander Go managed to score 54 points for doing the first two subtasks instead.

Among the thirteen participants who submitted code to Merging and Missiles, only four managed to obtain nonzero scores. CJ and Kyle both managed all subtasks while Ron and Dion managed to solve enough subtasks to respectively get 55 and 25 points.

One can see a similar pattern in Late-Night Littering. Only half of the eight finalists who submitted got nonzero scores and only half of that, namely Dan and CJ, managed to get all of the subtasks correctly. Ron managed to do all but the last subtask while Andrew Ting managed to do all but the last two.

Backbreaking Breakout proved to be the most backbreaking problem for all the participants as only four got a nonzero score. However, none of the finalists managed to help complete the break out. Dan was the highest scorer in this problem and managed to solve all but the last two subtasks. Ron and Zachary Lopez finished subtask 1 and got 15 points for it. Franz was the only one who finished subtask 4 and got 5 points.

## Photo Gallery

Special thanks to Justin Castro for the photos!

## Scoreboard for NOI.PH 2018 National Finals

ranknamescoretimegrade levelschoolcoachregionusernameVoltes GroupGlobal WarmingThrust TrialsLean on MeBoomerang GadgetMerging and MissilesSister SpaceshipsLate-Night LitteringBackbreaking BreakoutPeople Power
1Dan Alden Baterisna640567.1Grade 10Colegio San Agustin - Makati NCR: National Capital RegionDBaterisnaPH181001001073010010057100
2Carl Joshua Quines638527.63Grade 12Valenzuela City School of Mathematics and ScienceRuel DogmaNCR: National Capital RegionCQuinesPH1882100010010010010056
3Kyle Patrick Dulay500510.87Grade 12Philippine Science High School - Main CampusEdge AngelesNCR: National Capital RegionKDulayPH181001000100100100
4Franz Louis Cesista266516.18Grade 12Philippine Science High School - Eastern Visayas CampusCary Von AlanoRegion VIII: Eastern VisayasFCesistaPH181001000120230526
5Dion Stephan Ong258570.95Grade 10Ateneo de Manila Junior High School NCR: National Capital RegionDOngPH180100102523100
6Ron Mikhael Surara257548.35Grade 10Philippine Science High School - Bicol Region CampusJohn Rainer JoaquinRegion V: Bicol RegionRSuraraPH18051101255581556
7Andrew Ting154410.57Grade 12Xavier School San Juan NCR: National Capital RegionATingPH18230122340056
8Steven Reyes148423.23Grade 9Saint Jude Catholic School NCR: National Capital RegionSReyesPH181002325
9Alexander Go145584.92Grade 12Xavier School San Juan NCR: National Capital RegionAGoPH18231254056
10Zachary Lopez98567.32Grade 11International School of ManilaNCR: National Capital RegionZLopezPH182312231525
11Ian Vincent Palabasan91538.68Grade 12Rizal National Science High School Region IV-A: CALABARZONIPalabasanPH1823001200056
12Ryan Mark Shao79139.15Grade 11Xavier School San Juan NCR: National Capital RegionRShaoPH18000023056
13Rae Gabriel Samonte79320.88Grade 10Philippine Science High School - Bicol Region CampusJohn Rainer JoaquinRegion V: Bicol RegionRSamontePH1823056
14Steven Gabriel Chua64333.2Grade 10Xavier School San Juan NCR: National Capital RegionSChuaPH188056
15Ian Angelo Aragoza56358.63Grade 12Philippine Science High School - Central Luzon CampusJan Michael IbanezRegion III: Central LuzonIAragozaPH18232310
16Ian Red Ligot55349.4Grade 12CIIT College of Arts and Technology NCR: National Capital RegionILigotPH1823101200010
17Jed Arcilla41248.05Grade 10Philippine Science High School - Bicol Region CampusJohn Rainer JoaquinRegion V: Bicol RegionJArcillaPH18041
18Daniella Joan Francisco33483.4Grade 9Philippine Science High School - SOCCSKSARGEN Region CampusSheena Dawn FerrarenRegion XII: SOCCSKSARGENDFranciscoPH1823010
19Steven Gabriel Chua26116.35Grade 10Xavier School San Juan NCR: National Capital RegionKChuaPH180026
20Al Christian Mabute26118.9Grade 10Philippine Science High School - Bicol Region CampusJohn Rainer JoaquinRegion V: Bicol RegionAMabutePH180000026
21Lance Benedict Cabrera26131.32Grade 8Philippine Science High School - Bicol Region CampusJohn Rainer JoaquinRegion V: Bicol RegionLCabreraPH18000026
22Francis Benedict Martinez26240.22Grade 9Philippine Science High School - Eastern Visayas CampusCary Von AlanoRegion VIII: Eastern VisayasFMartinezPH18000026
23Johnbell De Leon1076.17Grade 9Philippine Science High School - Bicol Region CampusJohn Rainer JoaquinRegion V: Bicol RegionJDeLeonPH180010
24Frederick Ivan Tan10127.47Grade 8Philippine Science High School - Main Campus NCR: National Capital RegionFTanPH180010
25Kim Bryann Tuico10192.8Grade 11Manila Science High SchoolRomer AbellaNCR: National Capital RegionKTuicoPH180000010
26Gregory William Joseph Liu10219.98Grade 11Philippine Science High School - Central Visayas CampusFelix CalvoRegion VII: Central VisayasGLiuPH180010
27Rapharl Justin Portuguez10231.57Grade 11Philippine Science High School - Central Luzon CampusJan Michael IbanezRegion III: Central LuzonRPortuguezPH180010
28Philmon Wee00Grade 10Xavier School San Juan NCR: National Capital RegionPWeePH18000000

## Final Message

Congratulations to all the winners of the National Olympiad in Informatics – Philippines 2018 Finals!

The organizing committee would like to thank our host, Pointwest Innovations Corporation, for their generous support in providing the venue and infrastructure to hold the event. Special thanks to Ms. Beng Coronel, Ms. Veck Basinang, Mr. Sherwin Pelayo, and the infrastructure and IT security teams of Pointwest for accommodating us and helping us throughout the event. We also express our gratitude to Uber for giving the option for our guests to travel with them at a discounted rate. We would also like to express our deepest gratitude to Mr. and Mrs. Ryan and Dorene Uy for helping out.

We would also like to thank our volunteers from the Institute of Electrical and Electronics Engineers (IEEE UPD-SB), ADMU ProgVar, UP ACM, and CompSAt, as well as our testers, and ushers for helping out.

Lastly, we thank all the coaches, parents, and students for their participation and hard work and for making this event a success. We hope for your continued support as we move to the selection of our delegation to the International Olympiad in Informatics in September.

## Introduction

Is it going to be your first time to go to the final round? Has it been one of your hashtag life goals to officially participate in the onsite round but haven’t gotten around to preparing yet? Here is a first-hand account of what happened during NOI.PH Onsite Round last year to let you know what you’re going in for. This is being posted with permission from CJ Quines, one of last year’s finalists, and the writer of this article. The article has been edited accordingly to be on a website. The full PDF in all its glory is on his website.

[latexpage]

## NOI 2017 Reflections

The following is a narration of the events that occurred in the NOI 2017 finals. It’s very likely that the order I did the problems is inaccurate, because I’m writing this quite some time after the actual event. Abbreviated versions of the problem statements are in the appendix.

## Practice round

Reminders for the participants were projected in front of everyone. It contained instructions on compiling using the terminal, which was pretty helpful. The computers were running in Ubuntu and I didn’t know how to compile in Ubuntu.

This was the first time I’ll be using Ubuntu, and I really wasn’t familiar with any Linux distro. But well, that was the purpose of the practice round, to get used to the environment.

Apparently we’re allowed to use Zeal, a program that provides offline documentation. Which was a big help, considering I don’t know much of the standard library and the language, even though I should. I could look up how wide an int is, or how to use printf to truncate decimals.

I took a few minutes acclimating to the system. I tried to build a file in C++. I checked which version of Python was on the system, and there was Python 2.7. There was Sublime Text 3, which was good since that’s the editor I used. I tried the build system, which worked, so no problems.

The practice round started a bit after that. It would be for two hours, and I spent the first few minutes looking through all the problems, and they all looked doable except the last. I read the first problem and I am puzzled after finding a simple solution: repeat the string ABC up to $n$ letters. I wondered if there was more to it. It worked, so I moved to the next problems.

The second problem invovled $\oplus$, bitwise addition. After thirty minutes of false starts and forgetting the size of $n$, I managed to get a wrong answer. Then I managed to find a simple solution: n i i, where i is an integer. At this point I realize that the two previous problems were math problems — was this a sign?

Problem three was a math problem involving pigeonhole. Thus, for the record, there were three math problems in the practice round. The closed-form is well-known among the math community: it is stars-and-bars. The problem was computing a bunch of binomial coefficients quickly. I’ve seen a trick in doing that before, using the magic of DP: store Pascal’s triangle in memory and call.

That was not that straightforward to implement, and I had a few false starts due to wrong indices. I did manage to do so, after roughly another thirty minutes since I solved the second problem. This leaves me with a round $300$ points, eighty minutes in the round.

There were forty minutes left and one problem to solve, and the remaining problem was so complicated that even the abbreviated version in this report took two paragraphs. After trying a few cases on paper, I quickly realize that solving it completely would be impossible in the remaining time, and focused on the first subtask. The first subtask was restricted enough that it was only the matter of finding the shortest path from left to right.

I did know that would involve a pathfinding algorithm. I thought of using a BFS. The trouble was, I did not like working with grids and graphs. I spent the last few minutes of the practice round working on reading the data, which I struggled with, because I kept messing up scanf. I gave up at about three minutes left. We counted down the last ten seconds and ended with applause.

## Round 1

After the practice round was lunch, and after lunch was the start of the first round. It would be for five hours, starting from 1:30 PM and ending at 6:30 PM.

The first thing I did was read all the problems and try to summarize what each one was asking for. The first problem involved $\oplus$ once again, which probably explains why one of the practice round problems involved $\oplus$, as setup for this problem. The second problem was probably a math problem, counting the number of increasing sequences. I try a few cases by hand and get nothing.

The third problem was an algorithmic problem, involving ranged sums-of-maximums queries. Of course, after working out on paper, the maximum part isn’t as important — it’s a ranged query of $2^{n-1}a_n + 2^{n-2}a_{n-1} + \cdots + a_1$, once you sort it to get $a_n > a_{n-1} > \cdots > a_1$. Sorting was $O(n\lg n)$, and then $q$ queries made it $O(nq\lg n)$, which isn’t nearly fast enough for the last subtasks.

The fourth problem invovled a binary grid, which makes use of a very interesting property. Suppose we have an $(m-1) \times (n-1)$ binary grid. We add a column to the right of the grid, as the sum modulo two of each row, and add a row to the bottom of the grid, as the sum modulo two of each column. Then if we take the sum modulo two of the last column, and take the sum modulo two of the last row, they’re the same. It’s an interesting combinatorics exercise in invariants.

Without any intuition for which problems would be easier, I decided to work on the first problem first. Since the inputs become really large, there is probably an $O(1)$ or an $O(\lg n)$ solution, and since it looked like a math problem, I erred on the side of an $O(1)$ solution. After working out a few small cases on paper, I fail to see a pattern. Then I realized, I had a computer! I can use a program to bash small cases.

I wrote a short Python program to bash the first few cases. At first the program was only limited to spitting the answer for certain $M$ and $N$, but this was too slow. So I wrote a function that tried all $N \leq M$. But this was also too slow, so I wrote another function that tried all $M$ up to a certain limit, and stored the results in a triangle.

There were a few observations to be made. The $N = 1$ case is easy, and so is the $N = 2$ case. The $M$ is a power of two and one more than a power of two had a pattern. Usually, for a certain row, after a certain point, everything is just the same power of two over and over. And this power of two was the smallest one larger than $M$, let’s call it $2^k$. Besides that though, there didn’t seem to be any pattern I could exploit for an $O(1)$ solution. My biggest lead was figuring out when it became a power of two over and over, which could be a potential optimization.

After writing out a few cases, I make a conjecture that this happens when $M + N – 1 \geq 2^k$. At this point, I’ve spent an hour in the competition, so I decided to fold for the moment by writing a program for what I had. It would do the optimizations for the special cases and the $M + N – 1 \geq 2^k$ case, and otherwise bash.

While writing the program, I spend a lot of time figuring out how to compute $2^k$ given $M$. I first tried to do some clever stuff using bit manipulations, but after failing for five minutes to find something suitable I decided to just hardcode the powers of two, which would also be helpful later on for the $M$ as a power of two case. At first, I thought of trying a bunch of conditional statements, but then I realized that it would be easier to do a binary search. I mess up the binary search a few times, spending another ten minutes at something that should have been routine.

I finshed the program, and it got a wrong answer. Not even the first subtask, which was $M, N \leq 20$. This was roughly ninety minutes in the competition. I had to make a decision whether to debug or to proceed, and I made a decision to debug instead, because I was more likely to score points repairing a solution rather than making a new one. (This is something I learned from math contests. When running out of time and faced with the decision to review answers or to proceed, it is often better to review answers, because that holds more potential points.)

After racking my brain looking for typos, I still couldn’t spot the error. I decided to do a brief check and use the triangle I generated from my Python code to make the first twenty rows and submit that. It got the first subtask, so there wasn’t anything wrong with the judge, and the problem had to be my code. (I have good faith in the problem-setter. But I was debugging and under stress, so I had to make sure.)

If my Python code produced the correct answers for the first subtask, and the program failed to, then there must be a discrepancy with the answers that both produced. This was kind of expected: I never proved any of my observations, I just made guesses based on data. I decided to get my program again and print the first twenty rows to compare it with the Python output.

After printing, I noticed something: the conjecture that $M + N – 1 \geq 2^k$ implied the answer was $2^k$ is wrong, and this was the cause of almost all of the discrepancies. The conjecture that worked was $M+N \geq 2^k$. There was another discrepancy however, the case $M = N = 2$, and I could not understand how that was produced, so I decided to just hardcode the answer to that case.

I also noticed I could make an optimization for the bashing. Instead of checking all $MN$ cases, you only need to check the cases between $M$ and $2^k$ if they could be produced with a number between $1$ and $N$. In other words, you can already produce all the numbers $1 \leq x \leq M$ by doing $x \oplus 1 = x$, so you only need to check which numbers $M+1 \leq x \leq 2^k$ can be produced.

This can be done with a cool property of $\oplus$: $a \oplus b = c \iff a \oplus c = b$. If we were looking for $m \oplus n = x$, where $x$ is the value we want to check is possible, we only need to do $m \oplus x = n$, and check if $1 \leq n \leq N$. Although both algorithms are $O(MN)$, the second one is faster by a constant, and the first subtasks were clustered enough together that optimizations counted. I submit and it gets 37 points, not a lot, but fine.

I moved on to the second problem, and after trying out a few small cases I quickly realize that this is a combinatorics task. I try to list out the small cases, wasting a few minutes, especially since a lot of my listing was wrong. I managed to produce the first few values.

I fail to see a pattern, so I decided to try a different approach: treat it as a math problem that I would see in a contest. Let’s say there are $n$ numbers we have to permute. I make a few initial observations from my failed listings, the most important one being that $1$ is pretty restricted. It could only appear in the first or second slot in the permutation. If $1$ appeared in a later slot, then it had to be larger than either of the two previous slots, which is impossible.

Let’s call the number of permutations where $1$ goes first as $a_n$ and where $1$ goes second as $b_n$. If $1$ was in the first slot, how can we fill in the rest of the slots? The condition for the third slot is already fulfilled: it’s already larger than the first slot, $1$. So the second slot can be anything, and the third slot can be anything, provided that the fourth slot’s conditions were fulfilled, and so on. This was precisely the case for $n-1$! So $a_n = a_{n-1} + b_{n-1}$.

Now, if $1$ appeared in the second slot, then we can just ignore the first slot. We have a permutation of $n-1$ where $1$ is the first. There are $b_{n-1}$ ways to do this. And then there are $n-1$ ways to pick the number in the first slot. Thus you had $b_n = (n-1)b_{n-1}$. I worked out a few cases by hand and it matched my small cases from earlier.

That was great — with both recursions, we could compute for any $a_n + b_n$. I decided to code up this solution, using two arrays, and it got all the subtasks, hooray. After coding this solution I then realize that you could make it one recursion instead. The $(b_n)$ were basically the factorials, and you could do it with only one array. But the point was that the problem was solved, so I moved to the next problem.

As an aside, my write-up for this might make it look like solving the second problem was a straightforward process. It wasn’t — it took another hour. At this point, I spent the first two hours at the first task and another hour at the second task, putting me three hours in the competition.

With roughly two hours left, I had several choices of things to do, and it was hard to decide which to do next. Optimize task 1, try task 3, try task 4.

The advice I heard was maximize points in the remaining time”, which was easier said than done. I felt I couldn’t get any more potential points for task 1 without spending a lot of time, but tasks 3 and 4 seemed easier to get at least a few points. I tried task 3 first, because it was before task 4.

I already worked out earlier on paper that the answer was just the powers of two times the sorted list, and that this was $O(nq\lg n)$. I try to think of a more clever solution. Since it involved ranged queries, the first thought was to try a segtree, and figure out how to propagate.

This was not easy, and I failed to do so. The problem was that segtrees should have parts that build up from smaller cases, but the power of two times the sorted subarray did not build up easily. I couldn’t think of a good way to solve the problem. The $O(nq \lg n)$ was enough to grab about a third of the points, I think, so I tried coding that first.

That was also problematic. I had to repeatedly look up how to use sort, since I wasn’t familiar with that. I needed the powers of two, and computing them each time was slow. I realized that I already had the powers of two hardcoded from my solution to task 1, so I just grabbed that. After that, I think I managed to get $53$ points, and I had an hour left.

I did not manage to do a lot in the last hour. The tasks I could do included: optimize task 1, optimize task 3, try task 4. After trying task 4, I then quickly realized that it was not easy.

I managed to come up with a way to count the minimum number of entries that need to be changed, which is a complicated thing involving counting the number of ones in each row and column. This happened after trying lots and lots of small cases, which took up thirty minutes of my time.

The hard part was computing the number of ways to obtain a good grid. After doing a lot of combinatorial stuff, there was an $O(1)$ solution that was very very long and used a lot of factorials and was, to be brief, hard to compute.

I tried to code brute force instead for task 4, but after failing to read the input after fifteen minutes, I decided to give up. I spent the remaining time trying the first task.

As the time was about to close, I used up another ten minutes or so trying out the first task by looking for patterns in the binary expansion. I did not manage to find a usable pattern. I ended up with 190 points, placing me at third place for round 1.

## Round 2

The numbering will be as in the appendix, so the problems in round 2 are tasks five through eight.

Again, I first read all the problems to get a general sense of the round today. It was lucky for me that the problems in the previous day were largely mathematical in nature, in contrast to algorithmic problems that are usual in competitive programming. (This was not good for other contestants, however. Robin was particularly against this. He makes the case in his blog that this should not happen in programming contests, and it is a thought-provoking read.) The second day, however, seemed to be all algorithmic problems.

The fifth task would’ve been easier, if it was considering subsequences instead of subarrays. Indeed, this was the mistake I made in my first reading. The sum of the second smallest terms in each subsequence can be found simply by sorting and multiplying each term by the appropriate factor, $O(n \lg n)$. But this was subarrays, not subsequences.

The sixth task seemed relatively straightfoward and it seemed like it can be done in $O(n)$ for reading the input. The seventh task seemed like a straight MST (Minimum spanning tree, a classic algorithmic problem.) at first, though I had to read it twice. I found it hard to believe that a classical problem would be given out, so I decided to take a closer look later.

The eighth task was a tiling problem, and it would make a good combinatorics problem. However, the programming version is significantly harder, because you have to read the input and output the tiling correctly, which was quite complicated. I decided I probably wouldn’t solve it.

Once again, I tried the tasks in order. I knew early on that the sixth task was the easiest, but I would be leaving it for the middle of the competition when my concentration is least. I did the fifth task first. I spent a good amount of time trying to figure out how to do it quickly.

I spent a good deal of time trying out the problem on paper, and lots of small cases. It felt like a DP problem, and if it was a DP problem, then it should be able to be done with a processing from left to right. Adding a new element on the end of a list with $n-1$ elements gives you $n$ new subarrays, all of them ending with the newly added element. If you sort them one-by-one, that’s $O(n \lg n)$. You have $n$ new subarrays, and you do this $n$ times, so that’s $O(n^3 \lg n)$, quite slow.

I somehow had the strong urge that sweeping from left-to-right would be best. I tried more and more small cases on paper, looking for a pattern. I briefly thought of using something like a divide-and-conquer, a segtree-style solution. Once you have the segtree set up in $O(n \lg n)$, you have $O(n^2)$ queries and $O(\lg n)$ time for each query, making $O(n^2 \lg n)$. But I was not good with segtrees.

I went back to my previous solution — there was a lot of redundancy in sorting the subarrays, because there was a huge overlap between them. Right, overlap! You only need the second smallest term for each subarray, but each new subarray is the same as a previous one, with a new element on the end.

Thus you didn’t need to sort the whole array over again. You just need to keep in memory the two smallest elements in the subarray starting from each element. Then you’d only compare this new term to the two previous smallest elements, which is $O(1)$, because it’s two comparisons worst-case.

Why is it two comparisons worst-case? Say the two previous smallest elements in the subarray were $x \leq y$, and you’re adding $z$ to the subarray. If $z \leq x$, then the new smallest elements are $(z, x)$. If $z \geq y$, then you retain the smallest elements: $(x, y)$. Finally, if neither, then it’s $(x, z)$. Two comparisons, instead of sorting the whole subarray, which cut $O(n \lg n)$ to $O(1)$.

That bought the time down to $O(n^2)$: $n$ subarrays for each added element, and you add an element $n$ times. I couldn’t reduce it any further, so I typed up my solution. That got me 45 points, after some debugging, and the next subtask seemed too difficult, so I moved on to the next problem.

Even though the next problem was the easiest one throughout the whole competition, I spent nearly an hour and a half trying to solve it. The sixth task was a reference that I got: it was referring to Breaking Bad, and it was rather witty.

My solution, basically, involved keeping track of the previous coordinate and the current coordinate, as well as the current mode”. It could be in horizontal mode, or vertical mode, or neither. Basically, if it was in horizontal mode and the next vertex did not lie in the same horizontal line, you have to make a turn, ditto for vertical mode.

After coding my solution, and debugging it, it still got a wrong answer. Not even the first subtask. At this point I’ve spent nearly forty minutes coding and debugging, and trying to find what was wrong, so I made the mistake of hanging on to my code and creating test case after test case.

I tried to remember some advice I heard about debugging. Create tricky test cases, with small inputs. After writing several of these, I managed to find the error, but I didn’t know how to fix it. I simply decided that my solution was rubbish and that there was a simpler way to proceed.

Instead of keeping track of modes, you keep track of directions. This was a far simpler idea, and simpler ideas tend to work better. You kept the direction undecided for the first few points, until you hit a horizontal or vertical point. Then after that you had to alternate direction, and you simply incremented each time you had to alter.

That solution worked, and got all the points. I’ve used roughly three hours at this point.

Two hours left, and there were several things I could do: solve task seven, optimize task five, solve task eight, in order of ease. Task eight was placed last because I had bad experience with two-dimensional input and output. Optimizing task five would be hard, because the next subtask was such a big leap.

That left me with trying task seven, the MST variant. At first, I thought it was a straight MST — to minimize the average, you needed to minimize the sum, right? That was what it seemed like based on the sample case. So I tried to implement an MST algorithm, and build from there.

However, I’ve never implemented an MST algorithm before. I knew Kruskal’s, but I’ve never tried programming it. The idea was to keep all the edges sorted by weight from lightest to heaviest, and put in the edges one-by-one. If any new edge connected two vertices that were already in the tree, then discard.

Easier said than done, however. I ended up taking a lot of time for the edge routine, because I couldn’t figure out how to use priority_queue. I also got tired typing edge.second.first and edge.second.second over and over again. After a few iterations however, I got a seemingly working Kruskal algorithm.

I did not get any subtasks however. Then I realized that the way I was printing the floats was inaccurate, and it took me a few mintues of looking up printf before I could figure out what was wrong. Then I still got no points, and that was when I decided to take a break and think about the problem in the break room.

I was pacing around in the break room, trying to figure out what was wrong. Why wouldn’t the MST contain the smallest average edge weight? What wouldn’t make a minimal average spanning graph contain the MST?

After thinking it through and going through a few examples in my head, I realized what was wrong: you can add lighter edges to the MST to make the average smaller. It took me a few minutes before making that realization, but once I got that, I went back to the contest room and started working on paper.

Were there cases with a smaller average edge weight than the MST? That was impossible — either it contains the MST or it’s not the smallest average, by contradiction. I work out a few test cases on paper, and try to work it out.

For Kruskal’s, instead of throwing away an edge that would connect two vertices in the tree, you put it in another queue. And then when you make your MST, you push edges from that queue as long as it makes the average smaller.

Once again, easier said than done. The rest of the time was spent working on this problem, trying to fix my routines. I was implementing the graph using vectors, and I wasn’t well-versed with vectors at all.

Eventually there were two minutes left and I was still debugging my program. I couldn’t figure out what was wrong. I tried all the sample cases and the test cases I could think of and I still couldn’t spot the error. Eventually, I do see it: there’s a mistake with one of my subroutines, but there was not enough time.

I ended up with 145 points, which was just fine. That gave me a total of 335 points, making me sixth place, though I would only find that out later that evening. I had to leave early as I had class the next day.

## Reflections

I had problems of inefficiency during the contest. Excluding the fact that I didn’t notice the bitonicity for task 3, which few people did anyway, there was a lot of room for improvement, and much of that could be done relatively quickly.

For example, the fact that I didn’t know how to implement Kruskal’s made me lose a hundred points in the second round. I also had to refer to the documentation a lot, and I was only then figuring out how to do several things. It would be better to come to a programming competition more prepared, so I could focus on solving the problems.

Poor debugging skills were also something I needed to work on. I spent a lot of time debugging, which I could’ve spent figuring out algorithms and implementing them. This was something I’ve noticed before but didn’t give much attention to.

I did enjoy the competition a lot, and it was a wonderful learning experience to program for five hours straight for two days. It was very exciting, and I made a lot of new friends. I had a really fun time and I want to join again next year.

## Acknowledgements

Thanks firstly to the organizers and volunteers who made the NOI possible. It’s a huge effort, and I really appreciate the time they spend working on the NOI, without getting anything in return. Thanks to Pointwest for providing the venue which was really nice. Thanks to VCSMS as always for being supportive. And finally, thanks to the other competitors who were good company throughout the contest.

## 2018 National Eliminations

The NOI.PH 2018 National Eliminations started on 6PM of 5 January 2018 and finished on 11:59PM of 14 January 2018. It consisted of fifteen problems of varying difficulty.

## The Participants

Among the 261 registrants, 156 participated in the 222-hour online competition. The participants came from 30 different schools from all over the country. Moreover, each of the main regions of the Philippines were represented.

Luzon (60) | Visayas (34) | Mindanao (16) | NCR (46) | abroad (0)

Broken down by region, we have the following chart:

CAR (9) | I (19) | II (1) | III (5) | IV-A (6) | V (20) | VI (14) | VII (8) | VIII (12) | X (5) | XI (1) | XII (10) | NCR (46)

With regards to the distribution of grade levels, the likeliness to join was directly proprtional to the number of years spent in school. A lot of participants from senior high school have only spent one year studying but ended up with spectacular results. What more would at least three years of training? Younger participants are encouraged to join.

Grade 7 (2) | Grade 8 (11) | Grade 9 (19) | Grade 10 (31) | Grade 11 (43) | Grade 12 (50)

## The Problems

Here is the list of problems for the elimination round.

## Scoreboard for NOI.PH 2018 National Eliminations

This year, only registered participants are included in the final scoreboard.

## Final Round Qualifiers of NOI.PH 2018

In no particular order, here is the list of students who qualify for the NOI.PH 2018 Final Round. This list is subject to change depending on whether the students confirm or not.

• Al Christian Mabute (Grade 10)
Philippine Science High School – Bicol Region Campus
Coach: John Rainer Joaquin
• Alexander Go (Grade 12)
Xavier School San Juan
• Andrew Ting (Grade 12)
Xavier School San Juan
• Carl Joshua Quines (Grade 12)
Valenzuela City School of Mathematics and Science
Coach: Ruel Dogma
• Dan Alden Baterisna (Grade 10)
Colegio San Agustin – Makati
• Daniella Joan Francisco (Grade 9)
Philippine Science High School – SOCCSKSARGEN Region Campus
Coach: Sheena Dawn Ferraren
• Dion Stephan Ong (Grade 10)
Ateneo de Manila Junior High School
• Francis Benedict Martinez (Grade 9)
Philippine Science High School – Eastern Visayas Campus
Coach: Cary Von Alano
• Franz Louis Cesista (Grade 12)
Philippine Science High School – Eastern Visayas Campus
Coach: Cary Von Alano
• Frederick Ivan Tan (Grade 8)
Philippine Science High School – Main Campus
• Gregory William Joseph Liu (Grade 11)
Philippine Science High School – Central Visayas Campus
Coach: Felix Calvo
• Ian Angelo Aragoza (Grade 12)
Philippine Science High School – Central Luzon Campus
Coach: Jan Michael Ibanez
• Ian Red Ligot (Grade 12)
CIIT College of Arts and Technology
• Ian Vincent Palabasan (Grade 12)
Rizal National Science High School
• Jed Arcilla (Grade 10)
Philippine Science High School – Bicol Region Campus
Coach: John Rainer Joaquin
• Joaquin Jose Lopez (Grade 12)
Philippine Science High School – Main Campus
Coach: Edge Angeles
• Johnbell De Leon (Grade 9)
Philippine Science High School – Bicol Region Campus
Coach: John Rainer Joaquin
• Kim Bryann Tuico (Grade 11)
Manila Science High School
Coach: Romer Abella
• Kirby Ezra Chua (Grade 11)
Xavier School San Juan
• Kyle Patrick Dulay (Grade 12)
Philippine Science High School – Main Campus
Coach: Edge Angeles
• Lance Benedict Cabrera (Grade 8)
Philippine Science High School – Bicol Region Campus
Coach: John Rainer Joaquin
• Nyle Aldrin Maliwat (Grade 12)
Philippine Science High School – Central Luzon Campus
Coach: Jan Michael Ibanez
• Philmon Wee (Grade 10)
Xavier School San Juan
• Rae Gabriel Samonte (Grade 10)
Philippine Science High School – Bicol Region Campus
Coach: John Rainer Joaquin
• Rapharl Justin Portuguez (Grade 11)
Philippine Science High School – Central Luzon Campus
Coach: Jan Michael Ibanez
• Ron Mikhael Surara (Grade 10)
Philippine Science High School – Bicol Region Campus
Coach: John Rainer Joaquin
• Ryan Mark Shao (Grade 11)
Xavier School San Juan
• Steven Gabriel Chua (Grade 10)
Xavier School San Juan
• Steven Reyes (Grade 9)
Saint Jude Catholic School
• Zachary Lopez (Grade 11)
International School of Manila

They will all advance to the Finals round in February, a step to qualify them for the Philippine team to the International Olympiad in Informatics 2018 (IOI 2018) in Ibaraki, Japan!

For the finalists, please regularly check this website, your email and the Facebook like page for announcements.

All codes/submissions have been audited, and all scores/rankings are final.

## NOI.PH 2018 Fun-Filled Christmas Practice Contest Extravaganza Results

In preparation for the NOI.PH 2018 Online Round, we held the month-long NOI.PH 2018 Fun-Filled Christmas Practice Contest Extravaganza on HackerRank last December 2017.

Here are the results.

First, the general rankings, where all officially-registered contestants are eligible to win prizes:

## 2018 Practice Round Official Leaderboard - General Leaderboard

RankHackerRankFirst NameLast NameGrade LevelSchoolScore
1DanIsTheManDan AldenBaterisna10Colegio San Agustin - Makati4416
2_LELOY_Franz LouisCesista12Philippine Science High School - Eastern Visayas Campus3693
3redligot2009Ian RedLigot12CIIT College of Arts and Technology3280
4dsjong2002Dion StephanOng10Ateneo de Manila Junior High School3021
5andrewtingAndrewTing12Xavier School San Juan2457.33
6Something_HackerRon MikhaelSurara10Philippine Science High School - Bicol Region Campus2317
7H3XoRuSHRae GabrielSamonte10Philippine Science High School - Bicol Region Campus1698
8cjquinesCarl JoshuaQuines12Valenzuela City School of Mathematics and Science1634
9rogue8200Royce RogerYan12Philippine Science High School - Eastern Visayas Campus1414
10rmlshao19Ryan MarkShao11Xavier School San Juan1375
11nitrateatomAlexanderGo12Xavier School San Juan1354.33
12jedjetplaneJedArcilla10Philippine Science High School - Bicol Region Campus1268
13TheLostCookieKyle PatrickDulay12Philippine Science High School - Main Campus1200
14franciellajoanDaniella JoanFrancisco9Philippine Science High School - SOCCSKSARGEN Region Campus1156
15NemurinoFrancis BenedictMartinez9Philippine Science High School - Eastern Visayas Campus1114
16mjzamorasMichaelZamoras9Philippine Science High School - Eastern Visayas Campus1071
17Steve120StevenReyes9Saint Jude Catholic School924
18IntegJose RafaelMatienzo9Philippine Science High School - Eastern Visayas Campus893
19LittleHacker12JohnbellDe Leon9Philippine Science High School - Bicol Region Campus890
20fourcodingMiguel AngeloDelos Santos11Philippine Science High School - Ilocos Region Campus873
21clydejallorinaClyde CourtneyJallorina11Philippine Science High School - Main Campus816
22kelc210Kirby EzraChua11Xavier School San Juan800
22KatAttack01Jayson LenoiArollado12Xavier School San Juan800
24shannaurellegShann AurelleRipalda10Philippine Science High School - Eastern Visayas Campus642
25chosen_one12John AngeloOringo8Philippine Science High School - Bicol Region Campus628
26AudentesMarc DominicEnriquez12Philippine Science High School - Eastern Visayas Campus600
27stsorupiaSvenSorupia12Philippine Science High School - Main Campus578
28ariiicJose EnriqueRamirez8Philippine Science High School - Bicol Region Campus457
29acmabuteAl ChristianMabute10Philippine Science High School - Bicol Region Campus453
30Chou_Tzuyu1015SimwelPante9Philippine Science High School - Bicol Region Campus416
31BoogySaluteAllen AdrianSolis10Philippine Science High School - SOCCSKSARGEN Region Campus414.33
32AnagramicCoderJohn DavidVidad11Philippine Science High School - Ilocos Region Campus300
33F_Boi_69AdalbertApuya8Philippine Science High School - Bicol Region Campus286
34StrikeofsonarKristoferSano10Philippine Science High School - SOCCSKSARGEN Region Campus242
35HackskillShaquille WyanQue12Grace Christian College200
35regiszehnharold1Zehn HaroldRegis9Philippine Science High School - Eastern Visayas Campus200
35eryllaErylla BeatrishOamil11Philippine Science High School - Ilocos Region Campus200
35TG_GuruGabrielGeraldo9Philippine Science High School - Eastern Visayas Campus200
35calapsssCharles JavierCalapini11Philippine Science High School - Ilocos Region Campus200
35IllumeeSeanSta Maria12Philippine Science High School - Eastern Visayas Campus200
35CodeCodeCodeCodeVictor EdwinReyes9Philippine Science High School - Bicol Region Campus200
35ZachLoZacharyLopez11International School of Manila200
35CoderX_412ClarenceCombinido9Philippine Science High School - Eastern Visayas Campus200
44Blackheart_2003Gerrymie FlorelBajaro8Philippine Science High School - Bicol Region Campus116.67
45flameicicle27AmosVillanueva11Philippine Science High School - Ilocos Region Campus100
45booandroGarlu VictorNepomuceno10Manila Science High School100
45norielleeco76NorielleEco7Philippine Science High School - Eastern Visayas Campus100
45Rhayne213Maxene RhaynePaler7Philippine Science High School - Eastern Visayas Campus100
45HansA4HansAndales7Philippine Science High School - Eastern Visayas Campus100
45CyTPMJaymund CyrusFloranza8Philippine Science High School - Bicol Region Campus100
51SnarglePopJoel AndrewMallari9Philippine Science High School - Central Luzon Campus56

Second, the special rankings, limited to only those who have not ranked within the Top 10 of previous NOI.PH Final Rounds and have not been invited to NOI.PH In-House Training Camps:

## 2018 Practice Round Official Leaderboard - Special Leaderboard

RankHackerRankFirst NameLast NameGrade LevelSchoolScore
1redligot2009Ian RedLigot12CIIT College of Arts and Technology3280
2dsjong2002Dion StephanOng10Ateneo de Manila Junior High School3021
3H3XoRuSHRae GabrielSamonte10Philippine Science High School - Bicol Region Campus1698
4rogue8200Royce RogerYan12Philippine Science High School - Eastern Visayas Campus1414
5rmlshao19Ryan MarkShao11Xavier School San Juan1375
6jedjetplaneJedArcilla10Philippine Science High School - Bicol Region Campus1268
7franciellajoanDaniella JoanFrancisco9Philippine Science High School - SOCCSKSARGEN Region Campus1156
8NemurinoFrancis BenedictMartinez9Philippine Science High School - Eastern Visayas Campus1114
9mjzamorasMichaelZamoras9Philippine Science High School - Eastern Visayas Campus1071
10Steve120StevenReyes9Saint Jude Catholic School924
11IntegJose RafaelMatienzo9Philippine Science High School - Eastern Visayas Campus893
12LittleHacker12JohnbellDe Leon9Philippine Science High School - Bicol Region Campus890
13fourcodingMiguel AngeloDelos Santos11Philippine Science High School - Ilocos Region Campus873
14clydejallorinaClyde CourtneyJallorina11Philippine Science High School - Main Campus816
15kelc210Kirby EzraChua11Xavier School San Juan800
15KatAttack01Jayson LenoiArollado12Xavier School San Juan800
17shannaurellegShann AurelleRipalda10Philippine Science High School - Eastern Visayas Campus642
18chosen_one12John AngeloOringo8Philippine Science High School - Bicol Region Campus628
19AudentesMarc DominicEnriquez12Philippine Science High School - Eastern Visayas Campus600
20stsorupiaSvenSorupia12Philippine Science High School - Main Campus578
21ariiicJose EnriqueRamirez8Philippine Science High School - Bicol Region Campus457
22acmabuteAl ChristianMabute10Philippine Science High School - Bicol Region Campus453
23Chou_Tzuyu1015SimwelPante9Philippine Science High School - Bicol Region Campus416
24BoogySaluteAllen AdrianSolis10Philippine Science High School - SOCCSKSARGEN Region Campus414.33
25AnagramicCoderJohn DavidVidad11Philippine Science High School - Ilocos Region Campus300
26F_Boi_69AdalbertApuya8Philippine Science High School - Bicol Region Campus286
27StrikeofsonarKristoferSano10Philippine Science High School - SOCCSKSARGEN Region Campus242
28HackskillShaquille WyanQue12Grace Christian College200
28regiszehnharold1Zehn HaroldRegis9Philippine Science High School - Eastern Visayas Campus200
28eryllaErylla BeatrishOamil11Philippine Science High School - Ilocos Region Campus200
28TG_GuruGabrielGeraldo9Philippine Science High School - Eastern Visayas Campus200
28calapsssCharles JavierCalapini11Philippine Science High School - Ilocos Region Campus200
28IllumeeSeanSta Maria12Philippine Science High School - Eastern Visayas Campus200
28CodeCodeCodeCodeVictor EdwinReyes9Philippine Science High School - Bicol Region Campus200
28ZachLoZacharyLopez11International School of Manila200
28CoderX_412ClarenceCombinido9Philippine Science High School - Eastern Visayas Campus200
37Blackheart_2003Gerrymie FlorelBajaro8Philippine Science High School - Bicol Region Campus116.67
38flameicicle27AmosVillanueva11Philippine Science High School - Ilocos Region Campus100
38booandroGarlu VictorNepomuceno10Manila Science High School100
38norielleeco76NorielleEco7Philippine Science High School - Eastern Visayas Campus100
38Rhayne213Maxene RhaynePaler7Philippine Science High School - Eastern Visayas Campus100
38HansA4HansAndales7Philippine Science High School - Eastern Visayas Campus100
38CyTPMJaymund CyrusFloranza8Philippine Science High School - Bicol Region Campus100
44SnarglePopJoel AndrewMallari9Philippine Science High School - Central Luzon Campus56

All codes/submissions have been audited, and all scores/rankings are final.

Each contestant has the chance to win Steam credits, in proportion to their score on both leaderboards. We will notify contestants by email regarding their prizes. Congratulations to all!


text:
Apparent Magnitude / Apparent Brightness relationship help

I'm a high-school student that is currently working on a project that describes, using mathematical notation and explanation, how scientists can find the values of each of the properties of stars, such as Luminosity, Temperature and Mass. Currently, I'm struggling with finding the equation for the apparent brightness and apparent magnitude of a star. I have stumbled across something called the "Pogson relation", but need help it a couple of things.

I found the description of how to use it in another post:

The easiest way to determine the magnitude of a given star is probably to use the Pogson relation. The idea is to determine the magnitude of a star knowing the magnitude of a reference star; it is thus quite easy, using a well-known reference as Vega or Sirius.

The Pogson relation is given by:

$$m_1-m_2=-2.5\ log\ \left({\frac{E_1}{E_2}}\right)$$

where $$m_1$$ and $$m_2$$ are the magnitudes of star 1 and star 2 (your reference star), and $$E_1$$ and $$E_2$$ brightness

Firstly, is there any version of this equation which doesn't have a comparison between two stars, but rather a direct relation so that given $$M_{\text{Apparent}}$$, I can find $$E$$ of the star?

Secondly, if not, then what I had trouble with was the 'well-known reference' part of the explanation. It said that I use a value for $$E_2$$ that is known. However, after researching for the value of the apparent brightness, or its other name flux, for both Sirius and Vega, I have come up empty-handed. Is there a place that I can find this? I've looked at Wikipedia, even consulted the Gaia database, but in the field, there was nothing, just the apparent magnitude.

Lastly, is there any way to directly measure the apparent magnitude of a star with a scientific instrument, like how a CCD camera is used to measure the apparent brightness?

Thank you.

format: plain


text:
# Homework Help: Tension in a string in circular motion

Tags:
1. Jun 12, 2017

1. The problem statement, all variables and given/known data
A string prq which is fixed at p and where q is vertically below p. r is a smooth ring threaded on the string which is made to rotate at an angular velocity ω rad/s in a horizontal circle centre q, the string being taut.

If |pq| = 0.12 m, |pr| + |rq| = 0.18 m,
show that ω = 294^(1/2) rad/s.

2. Relevant equations
m(ω^2)r

3. The attempt at a solution
I was able to solve this and get the correct answer, by setting the sum of the horizontal tension equal to the cent. force, but I had to assume that the tension in the qr part of the string is the same as the tension in the pr part. What I don't understand is how we know that the tension in both parts of the string are the same considering they are at different angles.
I was thinking that because the string is massless, it must be the same everywhere. But then I encountered another question:

For this question a ball is connected by one string (it's massless) and I had to find the tension in the lower and upper part of the string. I was able to solve this, but what's confusing me is when to know when the tension is the same everywhere in the string, and when it's different.

#### Attached Files:

File size:
1.8 KB
Views:
101
2. Jun 12, 2017

### zwierz

is there gravity?

3. Jun 12, 2017

Yes for both.

4. Jun 12, 2017

### zwierz

As I understand the string is massless.
Then you have

Now break into the frame OXY the second Newton law: $m\boldsymbol a=\boldsymbol T_1+\boldsymbol T_2+m\boldsymbol g$

5. Jun 12, 2017

I was able to solve both questions and get the correct answer. What I'm wondering is why the tension was the same for the entire string in the first question and why for the second question the tension is different in the upper and lower part.

6. Jun 12, 2017

### zwierz

$|\boldsymbol T_1|$ can not be equal to $|\boldsymbol T_2|$ it is incompatible with Newton second law or with the configuration presented at the picture

7. Jun 12, 2017

### scottdave

How is the ball connected? It appears that the ball physically fixed to the rope at a position on the rope. Consider an extreme case: Ask yourself, if it stops spinning so that the ball is hanging straight down, what would be the tension in the upper string? and what would be the tension in the lower string? With the ball attached at a certain point on the string, you should be able to see that the bottom string would be hanging slack, while the upper string has m*g as it's tension.
Now look at the bead which can slide around on the string. Can you see how the tension in each string would be the same when it is hanging straight down? The same works when you consider strings over pulleys.

8. Jun 12, 2017

### zwierz

I guess that in case of entire string and when the bead can slide along the string freely then the triangle will not have the both sides equal

9. Jun 12, 2017

I was able to follow you up to the last two lines. In the original question, the ring is travelling in a horizontal circle. qr is parallel with the ground and pr is at an angle. I'm still unsure as to how the tension is the same and how the ring is "hanging straight down".

10. Jun 12, 2017

I posted two separate questions in my post. That picture applies only to the second question. The first question is a right angled triangle with a ring travelling in a horizontal circle. The only way I could get the answer 294^(1/2) was assuming that the tensions were the same.

11. Jun 12, 2017

### scottdave

Actually, I was referring to "if the pole stops spinning, what will happen to the bead?" Will it stay in the same place on the line, or will it slide down? The problem statement indicates that it can slide. With the pole stopped, it will hang straight down. What is the tension in the "two" strings (actually the same string). Now if the pole is spinning, you can expect the bead to slide up, and the tension on either side of the bead will be equal magnitude.

12. Jun 12, 2017

### scottdave

With the sliding bead, you should expect the tensions to be equal magnitude. If the bead were tied off, unable to slide, then the tensions will under most circumstances not be the same. I was demonstrating an extreme case of the pole stopping, to show how in the sliding bead, the tension remains the same on either side, while in the fixed ball, they are not.

13. Jun 12, 2017

How are the tensions equal in magnitude when the bead is sliding, shouldn't the upper string have more tension because of the gravity on the bead?

14. Jun 12, 2017

### scottdave

Let's say the pole is not moving. So the bead hangs straight down, and each side of the string has a tension of (m*g)/2. As it starts spinning, you will have a horizontal component (m*a). This will increase as the pole spins faster. Each side of the string has the same magnitude of tension, but in different directions: each one carries a different portion of the horizontal and vertical components.

15. Jun 12, 2017

Yes I kind of understand it better now. Thanks!

16. Jun 12, 2017


text:
# waRSAw - InCTF Internationals 2019

Intended solution of waRSAw challenge from InCTF Internationals 2019

tl;dr variant of LSB Oracle Attack on unpadded RSA

Challenge Points: 711
Challenge Solves: 18
Challenge Author: s0rc3r3r

Prerequisites:

## Introduction

This variant of LSB Oracle Attacks is different as compared to the binary search LSB algorithm for recovering plaintext, in terms of time complexity and ability to recover data on session renewal.

This attacks works due to leaking of the Least Significant Bit by an unpadded RSA encryption/decryption oracle that enables the adversary to decrypt the ciphertext in len(plaintext) requests to the oracle, where len(plaintext) is the length of plaintext to be decrypted in bits.

In this article, we will try to understand the logic and details behind the variant of LSB oracle attack on unpadded RSA and hence solve the challenge waRSAw using the intended solution.

## Variant of LSB Oracle attack

Consider the following scenario:
We have access to a service that allows us to encrypt/decrypt text using unpadded RSA. The service encrypts/decrypts using it’s public key and private key respectively. But after decryption, the server only returns the last bit of the plaintext obtained. How can such a service be vulnerable?

We have seen in LSBit Oracle Attack that such a service can be exploited and the plaintext can be recovered in $log_2{N}$ requests, provided that the modulus remains the same in all the iterations.

We know that the service returns the last bit of decrypted ciphertext ie.
$(ct^d\mod n)\mod 2\equiv m\mod 2$,
where ct is the ciphertext and m is the plaintext.

How can we exploit this?

One idea is to somehow do some computation on the ciphertext to shift plaintext right by one bit in each iteration, this way we can obtain one bit of plaintext, starting from the from rightmost bit, in each iteration.

Next step is to implement this idea:
We know that any k-bit plaintext m can be written as:
$m = (a_{k-1}*2^{k-1}) + (a_{k-2}*2^{k-2}) + (a_{k-3}*2^{k-3}) + … + (a_{2}*2^{2}) + (a_{1}*2^{1}) + (a_{0}*2^{0}); \forall a_i \in { 0,1 }$

1. Get the ciphertext you want to decrypt, let us assume that it to be ct and it’s corresponding plaintext to be m
2. Send the same ciphertext to the oracle for decryption and the oracle will return the last bit of plaintext i.e. $a_0$
3. We will now craft our chosen-ciphertext attack to recover all plaintext bits

### Chosen-Ciphertext Attack

Calculate
$(ct*(2^{-e} \mod n) \mod n)^d\mod 2 \equiv m*(2^{-1}\mod n)\mod 2$

Note that the inverse of 2 is calculated over mod n and not over mod 2

From the above equation we can write:
$m*(2^{-1}\mod n)\mod 2$
$= [(a_{k-1}*2^{k-1}) + (a_{k-2}*2^{k-2}) + (a_{k-3}*2^{k-3}) + … + (a_{2}*2^{2}) + (a_{1}*2^{1}) + (a_{0}*2^{0})]*2^{-1}\mod 2$
$= [a_1 + (2^1*a_2) + … + (2^{k-2})*a_{k-1}] + (a_0*2^0)*2^{-1}$
$\equiv a_1 + (a_0*2^0)*2^{-1} \equiv y \mod 2$
$\implies y - (a_0*2^{-1})\equiv a_1\mod 2$

Now that we have the value of 2nd last bit of plaintext i.e. a1, we can adopt a similar approach to recover a2

Calculate
$(ct*(2^{-2*e} \mod n) \mod n)^d\mod 2 \equiv m*(2^{-2}\mod n)\mod 2$

From the above equation, we can write:
$m*(2^{-2}\mod n)\mod 2$
$= [(a_{k-1}*2^{k-1}) + (a_{k-2}*2^{k-2}) + (a_{k-3}*2^{k-3}) + … + (a_{2}*2^{2}) + (a_{1}*2^{1}) + (a_{0}*2^{0})]*2^{-2}\mod 2$
$= [a_2 + (2^1*a_3) + … + (2^{k-3})*a_{k-1}] + (a_1*2^1 + a_0*2^0)*2^{-2}$
$\equiv a_2 + (a_1*2^1 + a_0*2^0)*2^{-2} \equiv y \mod 2$
$\implies y - (a_1*2^1 + a_0*2^0)*2^{-2}\equiv a_2\mod 2$

We can generalise this to compute and recover ith bit of plaintext from the end

Calculate
$(ct*(2^{-i*e} \mod n) \mod n)^d\mod 2 \equiv m*(2^{-i}\mod n)\mod 2$

From the above equation, we can recover ai as:
$[(m*(2^{-i}\mod n)\mod 2) - (a_{i-1}*2^{i-1}+…+a_1*2^1 + a_0*2^0)*2^{-i}] \equiv a_i\mod 2$

What if modulus changes during plaintext recovery (Due to service reconnection etc.)? The attacker can still recover the remaining plaintext bits. He/She won’t have to start over again in case of a service restart, since some bits of plaintext would have already been covered and the next iteration to recover ai can be done directly (See the above equation).

## Solving waRSAw using variant of LSB Oracle Attack

We implement the above method to solve the challenge:

from Crypto.Util.number import *
from Crypto.PublicKey import RSA
from pwn import *

def _encrypt(message):
r.recvuntil("choice: ")
r.sendline("1")
r.recvuntil("to encrypt (in hex): ")
r.sendline(message.encode("hex"))
ct = r.recvline("ciphertext (in hex): ").strip()[37:]
r.recvline()
r.recvline()
return ct.decode("hex")

def _decrypt(ciphertext):
r.recvuntil("choice: ")
r.sendline("2")
r.recvuntil("to decrypt (in hex): ")
r.sendline(ciphertext.encode("hex"))
pt = r.recvline("plaintext (in hex): ").strip()[36:]
r.recvline()
r.recvline()
return pt.decode("hex")

# r = process("./run.sh")
r = remote("18.217.237.201","3197")
r.recvline()
flag_enc = r.recvline().strip()[31:].decode("hex")
N = int(r.recvline().strip()[20:])
r.close()

print "Flag_enc: ", flag_enc.encode("hex")
print "N: ", N

# Public exponent
e = 65537

"""
1. The least significant bit of the flag is 1
2. Can be known by simply sending the ciphertext of the flag to the decryption
oracle
"""
flag = "1"
for i in range(1, 400):
# r = process("./run.sh")
r = remote("18.217.237.201","3197")
r.recvline()
flag_enc = r.recvline().strip()[31:].decode("hex")
N = int(r.recvline().strip()[20:])

# Actual Attack
inv = inverse(2**i, N)
chosen_ct = long_to_bytes((bytes_to_long(flag_enc)*pow(inv, e, N)) % N)
output = _decrypt(chosen_ct)
assert output == "\x01" or output == "\x00"
flag_char = (ord(output) - (int(flag, 2)*inv) % N) % 2

print "Here: ", flag_char
flag = str(flag_char) + flag
if len(flag) % 8 == 0:
print long_to_bytes(int(flag, 2))

r.close()

Running the above script gives us the flag: inctf{w0w_\$0_coOl_LSbit_|3r0}

In case of any query, feedback or suggestion, feel free to comment or reach me out on Twitter!


text:
# Finding Arbitrage in two Puts

A European Put Option on a non-dividend paying stock with strike price 80 is currently priced at 8 and a put option on the same stock with strike price 90 is priced at 9. Is there an arbitrage opportunity existing in these two Options?

I know we have to used the fact that Put Options values are convex with respect to their Strike Prices and could use the equation $P(\lambda K) < \lambda P(K)$? But, in the solution book that I have, they take $\lambda$ to be 8/9 and I don't know why this is.

Let $K_1=0$, $K_2=80$, and $K_3=90$. Then \begin{align*} K_2 = 1/9 \, K_1 + 8/9 \, K_3. \end{align*} Moreover, \begin{align*} Put(K_2) &= Put(1/9 \, K_1 + 8/9 \, K_3)\\ &< 1/9 \, Put (K_1) + 8/9\, Put(K_3)\\ &= 8/9 \, Put(K_3). \end{align*} Taking $K=K_3$ and $\lambda = 8/9$, we have that $$Put(\lambda K) < \lambda Put(K).$$
• @Gordon: Did you mean $K_1=10?$, how do you get $1/9K_1?$ If so, why do you pick that value of $K_1?$ Also, how do you go from $< RHS$ to $=8/9 Put(K_3)?$ Oct 29 '16 at 18:26
• @user12348: No, $K_1=0$ so that the put with strike $K_1$ has a value $0$. The inequality is based on convexity. Oct 29 '16 at 18:57


text:
## July 13, 2005

### Wednesday at the Streetfest IV

#### Posted by Guest

Well, I’m going to have dinner with Marnie and David and some other people, but I have a little time to kill, so maybe I’ll talk about Bouwknegt’s talk even though they’re also covering this one. After all, this talk was about string theory, and this is the string theory coffee table, not the “general abstract nonsense” coffee table!

John Baez

Well, I’m going to have dinner with Marnie and David and some other people, but I have a little time to kill, so maybe I’ll talk about Bouwknegt’s talk even though they’re also covering this one. After all, this talk was about string theory, and this is the string theory coffee table, not the “general abstract nonsense” coffee table!

The talk began with a lightning review of mirror symmetry, a subject I understand far too little off. There’s a kind of analogy that goes like this:

The A model is a topological quantum field theory that can be constructed by starting with strings propagating in a Kaehler manifold X and “twisting” theory using the complex structure. The algebra of observables in the A model is the Doulbeault cohomology of X. The category of D-branes is the bounded derived category of coherent sheaves on X.

The B model is a topological quantum field theory that can be constructed by starting with strings propagating in a Kaehler manifold X and twisting the theory using the symplectic structure. The algebra of observables in the A model is the quantum cohomology of X. The category of D-branes is the Fukaya category of X.

Mirror symmetry is supposed to relate these: the A-model on a Kaehler manifold X should be isomorphic to the B-model on some other Kaehler manifold Y…

… and vice versa, I believe!

As James Dolan pointed out, this “vice versa” would make the situation like “rot13” - that method of encoding where you go 13 places down the alphabet, so encoding something twice gets you back where you started. Is this “vice versa” really true???

Anyway, Hitchin’s “generalized geometries” are an attempt to understand this situation by finding a kind of geometrical structure on a manifold that includes both complex structures and symplectic structures as special cases, and which allows one to continuously interpolate between a complex structure and a symplectic structure.

The idea is to put complex structures not on the tangent bundle of X but on the direct sum of the tangent bundle and the cotangent bundle. There’s a way to do this starting with a complex structure on X. But, there’s also a way to do it starting with a symplectic structure on X!

One weird and interesting thing is that there’s a natural bracket operation on sections of $\mathrm{TX}\oplus {T}^{*}X$, called the Courant bracket. It’s skew symmetric but does not satisfy the Jacobi identity… it satisfies it up to d of some function. This reminds me of a paper by Weinstein on Courant algebroids, which made little sense to me when I first tried to read it.

Right around then Bouwknegt gave the definition of a Lie algebroid… and at this point my notes on the talk disintegrate, because I started pondering the definition and wondering if I could define a Lie 2-algebroid! Sorry. I hope Urs at least will forgive me for this, because he’s interested in this sort of thing. (Later I had a great talk with Danny Stevenson where we made a lot of progress on understanding the tangent bundle of a 2-space: it’s a category in the category of vector bundles!!! Understanding the tangent bundle of a 2-space and how its sections might form a Lie 2-algebra is probably a prerequisite for understanding Lie 2-algebroids.)

Anyway, for more on the subject of Bowknegt’s talk try these:

Hitchin’s paper

Gualteri’s thesis

John Baez

Posted at July 13, 2005 9:07 AM UTC

TrackBack URL for this Entry:   http://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/601

### 2-(vector bundles)

Later I had a great talk with Danny Stevenson where we made a lot of progress on understanding the tangent bundle of a 2-space: it’s a category in the category of vector bundles!!!

That’s interesting.

Let’s see. Such a 2-(tangent bundle) of a 2-space would have a vector bundle of objects. This should be the ordinary tangent bundle to the space of objects of the 2-space.

Then it should have a vector bundle of morphism. This is presumeably just the tangent bundle to the space of morphisms of our 2-space.

Hm, then probably source, target and composition maps are just the vector bundle morphisms between these vector bundles that come from the differentials of the source, target and composition map of our original 2-space.

Understanding the tangent bundle of a 2-space and how its sections might form a Lie 2-algebra is probably a prerequisite for understanding Lie 2-algebroids.)

One way to understand semistrict Lie 2-algebroids is in terms of the dg-algebra duals of ${L}_{\infty }$-algebras. This way one can see in particular that what is called the Courant algebroid really is a 2-algebroid.

But of course it would be nice to have direct construction.

It seems easy to categorify the definition of an ordinary algebroid, once we know what a 2-(tangent bundle) and a 2-(vector bundle) is supposed to be.

So there should be a 2-space $M$ and a 2-(vector bundle) ‘$E\to M$’ over it, which is apparently a category internalized in the category of vector bundles such that the base of the vector bundle of objects is the object space of $M$ and the base of the vector bundle of morphisms is the morphism space of $M$.

Then there should be the 2-(tangent bundle) $\mathrm{TM}$ of $M$ that you mentioned and an anchor functor $Estackto\rho \mathrm{TM}$, and so on.

On the other hand, what still seems to be missing is a nicer category-theoretic description of a mere algebroid. If that were available it might lead to a nicer 2-algebroid definition, too.

(BTW, it’s the A-model which gives rise to the Fukaya theory and the B-model which gives rise to the derived category of coherent sheaves.)

Posted by: Urs Schreiber on July 13, 2005 12:14 PM | Permalink | Reply to this

### p-path p-algebroids

One missing link in my thesis is this: I want to differentiate local $p$-holonomy $p$-functors

(1)${\mathrm{hol}}_{i}:{𝒫}_{p}\left({U}_{i}\right)\to {G}_{p}$

that go from the $p$-path $p$-groupoid ${𝒫}_{p}\left({U}_{i}\right)$ to the structure $p$-group ${G}_{p}$. The result should be a $p$-connection $p$-functor

(2)${con}_{i}:{𝔭}_{p}\left({U}_{i}\right)\to {𝔤}_{p}$

from the $p$-path $p$-algebroid ${𝔤}_{p}\left({U}_{i}\right)$ to the Lie $p$-algebra ${𝔤}_{p}$ of ${G}_{p}$.

Since I didn’t know (and possibly nobody knew) what the direct description of the $p$-path $p$-algebroid should look like, I switched to the dual description of algebroids in terms of dg-algebras, guessed the dg-algebra which should correspond to ${𝔭}_{p}\left({U}_{i}\right)$ and then showed that this (obvious) guess makes sense by demonstrating that it leads to the correct linearized cocycle relations. (That’s the content of section 13 of my thesis.)

Now that you opened my eyes, I should try to substantiate this guess by seeing if I can construct a 2-path 2-algebroid as a category internalized in the category of vector bundles.

Actually, the 1-path 1-algebroid should be nothing but the tangent bundle of base space. If true, the 2-path 2-algebroid should be nothing bu the 2-(tangent bundle) of base space, regarded as a 2-space.

Hm, maybe not. I don’t see how any 2-forms would get into the game this way. Maybe I would have to use the 2-(vector bundle) of the path space of base space.

Hm…

Posted by: Urs Schreiber on July 13, 2005 12:36 PM | Permalink | Reply to this

Post a New Comment


text:
# Taking the manual steps and creating automation

### Taking the manual steps and create automation

Creating a virtual environment in Anaconda is a straight forward task using the conda create -n env-namme command. By default, the new environment will be created in the folder of the anaconda/miniconda installation. For example in a Linux machine the environments are under the directory of ~/miniconda3/envs. Now, if we are working in projects that involve creating multiple conda environments, it might become tedious to always creating this environments with the manual way, installing each and every package by sequentially type the commands on the terminal. Of course we can add the most used packages to the ~/.condarc file and save some time. But, the other day I had to create, again, a virtual environment and I thought that it might be useful to automate as much as possible I can the procedure of crating virtual environments.

Prerequisites

• Linux
• For the script to work need the anaconda or miniconda to be installed (see my previous posts on how to install miniconda)
• If other than the bash shell is used (for example zsh), need to make sure the script will be properly executed. The easiest way is to just add #!/usr/bin/env bash at the top of the script so we can run it even if we use other shells

## Designing the conda-env-automation

1. To create a virt env we use the conda create -n test-env command. Since the script would be asking the user for the name of the env, need to have a user input for the name of env.
echo env_name

1. Since, we use anaconda environments to work with different python versions and packages, need to have a input that determines the version of Python as well as the packages will be install during the environment creation.
conda create -n test-env python=3.x package1 package2

1. Also can ask to activate the newly created environment
conda activate test-env

### Optional operations

1. Create an export (backup file) of the environment. This is helpful if someone else want to reproduce our work using the same environment.
conda test_env export > environment_backup.yml

#### Code Implementation

Initially will set a variable name for the location of the environments directory in the miniconda location. Also, will give the list of any existing environments.

ENV_PATH="$HOME/miniconda3/envs" echo "The folowing environments are installed:$(ls $ENV_PATH)"  Then, will check if the environment we like to crate exists and if so the process will exit the script dir_path="$ENV_PATH/$env_name" if [ -d "$dir_path" ];

then

echo "$env_name environment exists." slee 1 exit 0 else echo "$env_name environment does not exist."

sleep 1

echo "Will create the $env_name conda environment" fi  The dir_path variable gives the location of the environment, if that exists in the envs folder, The if statement looks for the particular environment, and if that exists will exit the script, if not the will continue to create the environment. The conda environments are used in the most of the cases to have a specific python version. So, the next part will ask for what python version of python we want. read -rp "Enter the Python version(only number): " py_ver  Also, most of the times we install particular packages will we create the environment. This can be done with following read -rp "Enter additional packages to install: " packages  Now that we have the python version and the packages we can create the environment conda create -n$env_name python=$py_ver$packages -y

The environment now has been crated and can use it by activating it with the conda activate test-env for example. We can further automate the process and prompt a question if we want to use the env after the creation. The script will ask if we want to activate the environment, if yes specified then will enter to it and if no will continue to the next step, witch is to create an export of the environment.

read -rp "Do you like to activate $env_name environemnt?" ask && if [ "$ask" = "y" ]; then

printf "Activating the environment...\\n"

conda activate $env_name else continue fi  Sometimes we might need to use a specific environment to another computer, or to send it to colleagues in our team for example to replicate the work we've done. This can be done if we export the .yml of the environment. So, the process can be automated to export the basic environment created initially. The script will ask if we want a backup file, if no the script will exit. If we do want to create a backup file of the environment then need to activate it and export the environment. Last, will deactivate the environment and exit the script. read -rp "Do you want to create a backup for the$env_name?" ask &&

if [ "$ask" = "y" ]; then printf "Creating the backup.yml\n" conda activate$env_name && conda env export > "\$env_name.yml"

conda deactivate

echo "The backup file crated."

else

exit 0

fi