wil93's blog

Italian Olympiad in Informatics (OII) 2017 — Online Contest

By wil93, history, 7 years ago, In English

OII logo

For the second time, the Italian national contest (valid for the selection of the Italian IOI team) will be mirrored into an online contest. The contest is primarily intended for high school contestants, but everyone is welcome to participate!

The contest timing will be USACO-like: it will be open for 24 hours but you will be able to compete for up to 5 hours (you can decide when to "start" your time window, after the login). Participation will be available upon registration to the Italian trainings website (localized also in english).

1. The problem statements will be available in both English and Italian.

2. The time window will start on 2017 September 15th, 10:00 CEST and will end on 2017 September 16th, 10:00 CEST.

3. Tasks will be IOI-like (with graders) and you will have 5 hours to solve them.

4. The languages allowed are: C, C++.

Note: you can decide when to start your 5 hour time window, but remember that the contest will end at 10:00 CEST regardless of your time window!

If you want to participate, you must:

  1. Visit the training website: https://training.olinfo.it (note that the URL was updated since last year)
  2. Click "Sign up" (if you haven't already done it last year!)
  3. Fill out the form and then confirm
  4. Visit the contest list: https://training.olinfo.it/contests
  5. Click on the OII 2017 National contest list entry
  6. Log in with the same username and password you used to sign up
  7. If the login is successful you will be ready to participate, just wait for the contest to start! (And maybe save the page in your bookmarks, so that you can quickly get back to it when the contest begins)
  8. When the contest starts, you will see a red button. Click it when you want to start your 5 hour time window!
  9. Good luck and have fun!

Ranking

The ranking for the national contest will be available here when the contest ends (now it just shows a 404).

Full text and comments »

  • Vote: I like it
  • +77
  • Vote: I do not like it

Italian Olympiad in Informatics (OII) 2016 — Online Contest

By wil93, 8 years ago, In English

OII logo

For the first time, the Italian national contest (valid for the selection of the Italian IOI team) will be mirrored into an online contest. The contest is primarily intended for high school contestants, but everyone is welcome to participate!

The contest timing will be USACO-like: it will be open for 14 hours but you will be able to compete for up to 5 hours (you can decide when to "start" your time window, after the login). Participation will be available upon registration to the Italian trainings website (localized also in english).

1. The problems will be available in both English and Italian.

2. The time window will start at 2016 September 16th, 10:00 CEST and will end at 23:59:59 CEST.

3. Tasks will be IOI-like (with graders) and you will have 5 hours to solve them.

4. The languages allowed are: C, C++, Pascal.

Note: you can decide when to start your 5 hour time window, but remember that the contest will end at 23:59:59 CEST regardless of your time window.

If you want to participate, you must:

  1. Visit the training website: https://cms.di.unipi.it
  2. Click "Sign up"
  3. Fill out the form and then confirm
  4. Visit the contest list: https://cms.di.unipi.it/contests
  5. Click on the OII 2016 National contest list entry
  6. Log in with the same username and password you used to sign up
  7. If the login is successful you are now ready to participate, just wait for the contest time window to start! (And maybe save the page in your bookmarks, so that you can quickly get back to it when the contest begins)
  8. When the contest starts, you will see a red button. Click it when you want to start your 5 hour time window!
  9. Good luck and have fun!

Can't wait??

This is your lucky day! You can participate right now to the OII 2016 Practice round (which sports very nice problems, authored by Delfad0r, mark03, cip999 and filippoqua) available until September 14th, 23:59 CEST (click here to see the countdown!). You just need to choose "OII 2016 Practice round" from the aforementioned contest list.

For this contest:

  • You will have a 5 hour time window as well.
  • The languages allowed are: C, C++, Haskell (sadly no Pascal!).

Ranking

  • The real-time ranking for the practice round can be found here.
  • The ranking for the national contest will be available here when the contest ends (now it just shows a 404).

Full text and comments »

  • Vote: I like it
  • +56
  • Vote: I do not like it

Strange bug on codeforces status page
By wil93, 11 years ago, In English

I was refreshing the status page waiting for the contest to finish. When final tests finished I found out that I wasn't logged in, but in the top right corner of the page there was written another's user name:

Screenshot

Screenshot after refreshing the page

Screenshot after refreshing again

At this point, I went to the homepage (I wasn't logged in there) and I logged with my username. After logging the status page was correctly showing my username in the top corner. Maybe it is a security issue.

Full text and comments »

  • Vote: I like it
  • +14
  • Vote: I do not like it

C++ complex class: issues with abs() and norm()
By wil93, 12 years ago, In English

Hi, I'm facing issues using the standard complex class from C++, in this task: The angle between the vectors.

I need to compute the length of vectors, okay: If I use the abs() function or sqrt(norm()) (same thing) I get 3 WAs out of 64 tests. If I compute it manually, I get AC.

This code gets AC, because I compute manually the lengths. This code gets 3 WAs, because I use abs().

Since I can't see input files I don't understand what is the problem.

Any idea?

Full text and comments »

  • Vote: I like it
  • +7
  • Vote: I do not like it

Help with a problem (hard implementation)
By wil93, 13 years ago, In English

Let's define an "expression" as a set composed only by number and brackets () [].

This is an expression: ( 18 4 [ 6 7 ( 4 ) 2 ] 6 8 )
Every expression starts with "(" and ends with ")".

There are N espressions in the input file, each is codified by M integers (N and M both aren't greater than 1000). Brackets are codified by negative integers. See this table:

( -1
) -2
[ -3
] -4

You can apply 2 basic operations to an expression to transform it into another:
1) You can permute the elements inside ()
2) You can reverse the elements inside []
By "element" we mean: a single number, or, an internal expression (see definition of expression, above).

For example, the above expression could be transformed into ( 8 [ 2 ( 4 ) 7 6 ] 18 6 4 ).
Two expressions A and B are equivalent only if you can obtain B starting from A, and vice-versa.

Your job is to classify the given N expression in K groups of equivalent expressions (K <= N).

INPUT:
First line contains N and M
N expressions follows (each is formed by M integers)

OUTPUT:
First line contains K (number of groups)
Follows K lines, each composed by Q+1 integers (where Q is the size of that group). These integers are respectively: Q, and the components of the group. See the sample output for clarity.

SAMPLE INPUT:
3 14
-1 18 4 -3 6 7 -1 4 -2 2 -4 6 8 -2
-1 8 -3 2 -1 4 -2 7 6 -4 18 6 3 -2
-1 8 -3 2 -1 4 -2 7 6 -4 18 6 4 -2

SAMPLE OUTPUT:
2
2 1 3
1 2

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

CF #85 Div.2 - Problems A, B, C, D
By wil93, 13 years ago, In English

Task A (link):


You can simply turn all characters to lowercase (to make a case insensitive comparison), then you should check the 3 conditions: A is greater than B, B is greater than A, A equals B. Time and space complexity is O(L) where L is the max length of the strings.

Task B (link):

Here the main observation is that in any square of length 2N there are exactly 4 "bad" cells: if you chose one of these bad cells then you will not be able to divide the square. We're talking about the 4 "center" cells.
Example with 2N = 4


Orange cells are bad cells

So, given 2N, X, Y, you should check that point (X,Y) is not equal to one of these 4 points: (N,N), (N,N+1), (N+1,N), (N+1,N+1).
Time and space complexity is O(1).

Task C (link):

We have to chose the biggest (a1 + a2 + ... + an) possible, but less than or equal to Y. We will choose Y, because this is the best way to maximize the sum of squares.
Now, we understood we have to split Y in N little numbers. We are free to choose the numbers that compose this sum.
The key observation here is that if we want to maximize (a12 + a22 + ... + an2) then we should maximize ONE number inside this list. Why? Well if you have two numbers A, B. If A2+B2 > (A+B)2 then we're wrong! because it's not good to maximize one term, but it's better to split this term and then take the square of each "piece". But this is always false! At least for positive A and B... Take a look at this plot.
So, how do we maximize one term? If we have N places for N numbers, and the sum must be equal to Y, then we start filling the first N-1 places with ones (1) and, in the last place, we write Y-(N-1), that is: the remaining part after summing N-1 times "1".

Example: N=5, X=15, Y=15
A solution is {4, 4, 1, 1, 2}, in fact its sum (12) is less than Y and the sum of squares (38) is greater than X.
Now let's try constructing our "greedy" solution... We fill with ones the first 4 places, and then we insert Y-(N-1). The result is {1,1,1,1,11}. Its sum (15) is ok, and its square sum (11x11 + 4 = 125) is the absolutely best we can achieve (and in this case it is okay for given X).
The conclusion is: given N and Y, we can obtain a solution iff X ≤ (Y-N+1)2+N-1
A special case is when N > Y. Obviously, in that case we will not be able to fill all the N "places".
Time complexity is O(N), space complexity is O(1).

Task D (link):

The main idea is to iterate over the list of numbers while keeping an array "pos", with pos[x]=y meaning that the last time we have seen divisor x we were on the y-th iteration. For each iteration (so for each query A, B), we search all divisors of the given number A, but we pay attention (using the "pos" array) to not count a divisor if we have seen less than B iterations ago. Now it's simple to code an algorithm that initializes to "-1" the array "pos" (alternatively, to a very low value, so the condition fails and you can count that divisor) and then iterates over the query list, updating pos[x] with the current iteration index each time we encounter divisor x. Time complexity is O(N * X) where N is the number of queries and X is the max value of A. This is about 1010, too slow! We should do an optimization to have the algorithm running in O(N*sqrt(X)).

We can check for divisors in a few ways, the simpler is O(A) where we iterate over all possible divisors of A. We can do better by thinking this way: if D is a divisor of A, then A/D is also a divisor of A. So we iterate over all possible divisors D less than or equal to sqrt(A), and then we consider 2 divisors instead of 1 (D and A/D).
Time complexity O(N*sqrt(X)), space O(N)

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

SPOJ: ABCDEF task - slowness of STL map
By wil93, 13 years ago, In English

Is relatively easy to see the equivalent form ab+c=d(e+f) so you can store all possibilities for the left side of the equation and for the right side.
I thought a O(N3logN) algoritmh which exceeds the time limit, and another (same complexity) which passes using 11 seconds (the best solutions are around 2 seconds).
My first algo used STL maps, and the code is very elegant:

1st part:
for each (i,j,k)
...map_1[i*j+k]++
...map_2[i*(j+k)]++ (only if i is non-zero)

2nd part:
For each element "X" in map_1 I check if exists an element "Y" in map_2 such that X.first == Y.first, if I find it, then I increase "Answer" (initially 0) by X.second * Y.second

Analisys: 1st part's "for each i,j,k" is O(N3) and the body of the inner loop requires O(2 * logN3) = O(6*logN) = O(logN). The first part requires a total of O(N3logN). The 2nd part's "for each X" requires O(N3) while its body requires O(logN3) = O(logN). The second part requires a total of O(N3logN).
2 * O(N3logN) = O(N3logN).
Now: N is not more than 100, so the amount of operations performed won't be more than 7*1003 = 7.000.000 (definitely runnable in 2s time limit) and if we want to count the costant factor (which is x2 x3 x2 = x12) the amount of operations is 84.000.000 still far from the "edge" of 200.000.000 (2 seconds time limit).

SO why is this STL container so slow?

I switched to vectors "abc" and "def" ("def" will be sorted after precomputation) and then for each element in abc I search for the amount of "copies" in "def" via lower and upper bound functions. This runs in time (anyway on my pc is slower than the "map" version). But the complexity is the same! The reduction is only by a constant.

Full text and comments »

  • Vote: I like it
  • +5
  • Vote: I do not like it

Lights (simple problem)
By wil93, 13 years ago, In English

This is intended to be simple, but I still have not understood how to solve it.

You have a building. Its windows are disposed like a grid with N rows and M columns.
Each window has a light (on / off). Here's an example of such a building:

1 0 1 1 0
0 1 0 0 1
1 0 1 1 0
0 1 0 0 1
0 1 0 0 1

with N = M = 5.

You have N+M special buttons: N buttons to toggle the state of ALL the lights of the i-th row, and M buttons to toggle the state of ALL the lights of the j-th column.

Toggle(x):
   if (x = 1) then x = 0
   else x = 1

You want to turn off all the lights using these N+M buttons, however this isn't always possibile. Determine if it's possible to turn off all the lights and, in that case, wich buttons has to be pressed (see examples).

SAMPLE INPUT:
5 5
1 0 1 1 0
0 1 0 0 1
1 0 1 1 0
0 1 0 0 1
0 1 0 0 1

OUTPUT:
Rows: 1 0 1 0 0
Columns: 0 1 0 0 1

- - -

SAMPLE INPUT:
5 5
1 0 1 1 0
0 1 1 0 1
1 0 1 1 0
0 1 0 0 1
0 0 1 0 1

OUTPUT:
Impossible

- - -

UPDATE: I forgot this...

Constraints:
  • 1 < N < 500
  • 1 < M < 500
  • The building has at least one lighted window.

Full text and comments »

  • Vote: I like it
  • +1
  • Vote: I do not like it

How to compute this in 10s ?
By wil93, 13 years ago, In English

An automatic machine has N coins inside, each one with a value. You should compute the smallest amount of money that the machine wouldn't be able to give.


In other words, given a set S of N positive integers, find the smallest integer wich cannot be expressed as a sum of one or more elements of S.

Example:

S: 10 2 14 1 13 2 3
Answer: 9

S: 1 16 2 1 23 18 1 4 3
Answer: 13

For N coins with maximum value MAX it's easy to find the answer in O(N2), for each new coin, I set its value as "avaible", then for all the older coins I set avaible the value coin[i] + new_coin

This would require an array of MAX booleans.

Now, I have 10 seconds for computing this answer for P machines.

Here's the hard part:
  • 1 ≤ P ≤ 1000
  • 1 ≤ Ni ≤ 10 000 (amount of coins per machine)
  • 1 ≤ Mj < 220 (value of a single coin)
  • For each machine, the sum of all coins is always smaller than 231

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

Need help with some tasks
By wil93, 13 years ago, In English
Can you help me with these two problems from italian olympiad?
- - -

Given a sequence S of N (2 ≤ N ≤ 500) integers (for example 11 -4 52 -7 -2 -20) we want to compute the sum of all numbers in S with a robot having limited capabilities: in fact, he can only compute the intermediate sum Y of two adjacent numbers A and B and replace A,B with Y, obtaining a shorter sequence (without one number). To compute this intermediate sum Y, the robot consumes exactly |Y| energy units (where |Y| stays for the absolute value of Y). So, to compute the sum of N numbers N-1 operations are needed. The robot always have enough energy to compute these N-1 intermediate sums, but he has some problem with energy peaks. In other words, we want the maximum energetic waste for an intermediate sum to be minimized.

In the sample above, an optimal sequence is:

11 -4 52 -7 -2 -20

11 -4 52 -7 -22

11 -4 52 -29

11 -4 23

7 23

30

The values of Y are:  -22, -29, 23, 7, 30. The maximum |Y| is 30. We can't do better as the sum of elements in S is 30.

Another sample:

7 -1 -8

6 -8

-2

The values of Y are: 6, -2. The answer is 6.

The time limit is 3s.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

In a strange planet the inhabitants speak a strange language, the alphabet is formed by binary digits. The dictionary is formed only by words not containing a sequence S of length M. Each word has length N (N ≥ M).

For example, if S = 01, then the binary words of lenght N = 4 not containing S are: 0000, 1000, 1100, 1110, 1111. If S = 11, the words are: 0000, 1000, 0100, 0010, 1010, 0001, 1001, 0101.

We know that 1 ≤ N, M ≤ 1000. Ouput the number of words in the dictionary, modulo 2011.

How the input is formed: first line (M, N), second line: sequence S.

Time limit: 1s.

Sample input:
2 4
01
Sample output:
5
Sample input:
2 15
11
Sample output:
1597
- - - - - - - - - - - -

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

A graph problem
By wil93, 13 years ago, In English
I'm solving a problem from Italian Olympiad in Informatics, the statament says:

There is a secret organization. If you want to enter the organization you must find two members of the organization who will guarantee for you. You got N guys, and M relationships (i,j) between them. A relationship means that guy[i] guaranted for guy[j] (or vice-versa).

A "triad" is a triple (i,j,k) of guys such the relationships (i,j) (j,k) (k,i) exist.

You want to count how many triads are in the input file, that is formed as follows:

First line, M (relationships) and N (guys)
From 2 to M+1 each line has 2 integers (i,j) representing a relationship between i and j (or viceversa)

Output: the number of triads.

  •  1 ≤ N ≤ 100000.
  • N-1 ≤ M ≤ 2N-3.
  • 1 ≤ I, J ≤ N.

    • Sample input:
    13 8
4 2
8 3
1 2
8 5 
6 8
4 8
7 2
6 7
2 8
7 4
8 1
5 6
3 2
    Output:
    5

    Note: the order in which you consider a triad is irrelevant. In the sample we have the triad 2,4,7 that is the same as saying 4,7,2 ...

    - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

    Full text and comments »

    • Vote: I like it
    • +8
    • Vote: I do not like it