Informatics


Tasks [Balkan Olympiad in Informatics 2016]

Day 1

Day 2

Advertisements

Reasons I got involved in Computer Science and Informatics

  • From a young age, I found it very interesting
  • I have a good friend that supported me all the way
  • It is fun and challenging!
  • There are so many different topics, once you get bored of one you can skip to the next
  • There are new topics and challenges almost every day
  • It is something that you can teach yourself (especially nowadays that there is so much free material online)

Blackgate Penitentiary

Vangelis the Batbear trapped all the members of Joker’s Streetgang in a basement.
Your job as a police officer is to transport all gang members to Blackgate Penitentiary.

To facilitate the transport, you should form a row such that the heights of the gang members are in non-decreasing order. For each gang member you should find the min and the max position where they can be in a valid sorted row and produce a roster with this information.

Input data

Input will start with a line that contains only one integer M, the number of crew members that were arrested. On each of the following M lines there will be a single word N and an integer H separated by a space character, where N is the name and H is the height of the crew member.

Output data

On the output, there will be G lines. Each line will contain in alphabetical order and space separated the names of the crew members that have the same height, followed by the min and the max position where any member of the specific group can be placed.

Limitations and notes

1 ≤ M ≤ 1000
1 ≤ length(N) ≤ 10
120 ≤ H ≤ 250

Names are only composed of characters of the Latin alphabet.


Batman and the Bubbles challenge

Good evening master Wayne.

Joker and his gang attended Black Hat USA 2017 where they learned of a new way on how to damage our city!
Specifically, tomorrow night they will try to damage the water pumps of Gotham using bubbles!
The bubbles cause corrosion to the pumps and in a few hours they will damage them with catastrophic results!
To dash Joker’s plan, besides stopping him, you need to make sure that the city network does not contain loops.
If Joker manages to inject bubbles to the network and they enter a loop, they will still cause damage to that area even though you would have already arrested Joker and his gang.

Given the map of the water distribution system, you need to make sure that the map does not contain loops.

Input data

On the first line there will be an integer T, the number of test cases to follow.
For each test case, there will be 2 input lines:

  1. On the first line of the test case, there will be 2 integers V and E, where V is the number of vertices and E is the number of edges.
  2. On the second line, there will be E pairs of integers separated by a space character. Each pair shows a two way connection between vector A with vector B.

Output data

For each test case you will have to write one line that contains an integer, in the case where there is a loop you will write the number 1 or else you will write the number 0.

Limitations and notes

1 ≤ T ≤ 1000
1 ≤ V ≤ 1000
1 ≤ E ≤ 10000
0 ≤ A,B ≤ V-1

Vangelis the bear is Batman! (or Batbear to be more precise).

Vangelis the bear is Batman! (or Batbear to be more precise).

Reading material

Supplementary material


Installing Task Translation System for IOI competitions (Linguist) on Ubuntu Server 14.04LTS

First, install any missing (also for font) related dependencies:

sudo apt-get update;
sudo apt-get install git unzip build-essential chrpath libssl-dev libxft-dev libfreetype6 libfreetype6-dev libfontconfig1 libfontconfig1-dev fontconfig fontconfig-config fonts-dejavu-core fonts-droid fonts-freefont-ttf fonts-kacst fonts-kacst-one fonts-khmeros-core fonts-lao fonts-liberation fonts-lklug-sinhala fonts-nanum fonts-opensymbol fonts-sil-abyssinica fonts-sil-padauk fonts-takao-pgothic fonts-thai-tlwg fonts-tibetan-machine fonts-tlwg-garuda fonts-tlwg-kinnari fonts-tlwg-loma fonts-tlwg-mono fonts-tlwg-norasi fonts-tlwg-purisa fonts-tlwg-sawasdee fonts-tlwg-typewriter fonts-tlwg-typist fonts-tlwg-typo fonts-tlwg-umpush fonts-tlwg-waree -y;

Then, get a copy of the repository:

git clone https://github.com/ioi/translation.git

Switch to the newly created directory:

cd translation/

And, add the gpg keys needed to make the setup.
The gpg command in the setup will contact a public key server (hkp://keys.gnupg.net) and request the key associated with the RVM project key which is used to sign each RVM release. To get the key, we need to provide the ID that is related to the key, in this case the ID is 409B6B1796C275462A1703113804BB82D39DC0E3. Having the RVM project’s public key allows us to verify the legitimacy of the RVM release we will be downloading, which is signed with the matching private key.

gpg --keyserver hkp://keys.gnupg.net --recv-keys 409B6B1796C275462A1703113804BB82D39DC0E3

If the above command fails with the following error

$ gpg --keyserver hkp://keys.gnupg.net --recv-keys 409B6B1796C275462A1703113804BB82D39DC0E3
gpg: requesting key D39DC0E3 from hkp server keys.gnupg.net
?: [fd 4]: read error: Connection reset by peer
gpgkeys: HTTP fetch error 7: couldn't connect: eof
gpg: no valid OpenPGP data found.
gpg: Total number processed: 0

Try using the following alternative:

command curl -sSL https://rvm.io/mpapis.asc | gpg --import -

Afterwards, perform the installation (this might take some time, depending on your connection to the server where it will download the necessary packages and your CPU performance as it will perform some compilation locally):

./deploy.sh

While installing codemirror we got the following prompt:

replace public/codemirror-3.22/doc/upgrade_v3.html? [y]es, [n]o, [A]ll, [N]one, [r]ename:

We typed A and pressed Enter. We are not sure if this is what we are supposed to do but it worked later on properly.

Edit the ./config.yml file and set new values for the api_token and cookie_secret.

api_token: "4c0a6fe55f3d4aa9c5dbb9a59db7b20e"
cookie_secret: "SDfadadsf90u84oh23jnrwf"
  • api_token is a 32 characters long random key. It can contain only character a-f and numbers 0-9.
  • cookie_secret is a 23 characters long value. This example contains any character from a-z and A-Z and the numbers 0-9.

You can generate random passwords from here http://bytefreaks.net/random-password-generator

Then start the redis service using the following:

redis-server

 

In an new terminal, go to DbInit folder:

cd translation/DbInit/

and update the files users.json and tasks.json to prepare the initial data to be imported in redis:

  • users.json Be sure to update the passwords of the users.
  • tasks.json Set the names of your tasks and the .md filenames of the original content.

The original content of tasks.json is:

[
    { "id": "1",    "title": "notice",     "filename": "notice.md" },
    { "id": "2",    "title": "gondola",    "filename": "gondola.md" },
    { "id": "3",    "title": "friends",    "filename": "friends.md" },
    { "id": "4",    "title": "holiday",    "filename": "holiday.md" }
]

Place the original .md files in this folder. And then initialize redis using the following command:

ruby dbinit.rb

Finally, go to the previous folder and start the translation system:

cd ..;
shotgun -o 0.0.0.0 -p 8080;

Visit http://SERVER_NAME_OR_IP:8080 to view the translation system.

You can use the admin account to make changes to users, to send notifications (if you omit the to field, then the notification will be send to all users) and to check out all task with their translations.

Staff accounts allow you to check out all task with their translations.

Note on the architecture

The deploy.sh script assumes your architecture and OS is 64bit. To find what type of architecture you are using execute uname -i. If the result is not x86_64, then phantomjs will not work for you and you will not be able to generate the PDFs. To fix this issue you need to download the correct version from https://bitbucket.org/ariya/phantomjs/downloads. At the time this tutorial was written deploy.sh was installing version https://bitbucket.org/ariya/phantomjs/downloads/phantomjs-1.9.7-linux-x86_64.tar.bz2, so we installed https://bitbucket.org/ariya/phantomjs/downloads/phantomjs-1.9.7-linux-i686.tar.bz2 using the following commands:

wget https://bitbucket.org/ariya/phantomjs/downloads/phantomjs-1.9.7-linux-i686.tar.bz2;
tar xf phantomjs-1.9.7-linux-i686.tar.bz2;
sudo cp phantomjs-1.9.7-linux-i686/bin/phantomjs /usr/local/bin;
rm -rf phantomjs-1.9.7-linux-i686*;

The above commands follow the example in deploy.sh.

Updating logos and website look

To update the views of the website you can do the by editing the .erb files that are in the translation/views folder.

Examples:

  • login.erb You need to modify this file to change the login screen
  • tasks_index.erb This file holds the structure of the main index the user sees after login (/tasks)
  • _navbar.erb Modify this file to change the navigation bar on top of each page
  • .. and more