Wow, time does fly when you're having fun. I'd swear it was just a few years ago when... but well, the numbers don't lie. This year it's the 20th edition of the IPSC, a programming contest with a twist (or two, or five, depending on the year). If you haven't yet had the pleasure to take part in the contest, click through to our website and check out the section "What makes IPSC different?". And if you already did, this is your reminder to register :)

The contest itself starts on October 6th at 15:00 UTC.

If you already did take part in some of the past years, which was your favorite problem, one that you still remember?

So, what's up with pow()?

Here at Codeforces it is quite common to see solutions that use pow() fail. Most recently this was the case in round #333 problem div2A. Whose fault is it?

Level 1 answer is that it is obviously the contestant's fault. The contestant should have been aware that pow operates on floating-point numbers and that there can be precision errors. If you expect that a floating-point variable contains an integer, you cannot just cast it to an int. The small precision errors mean that your nice round 100 can actually be stored as 100.00000001 (in which case the typecast to an int still works), but it can also be stored as 99.99999999 (in which case the typecast will produce a 99).

You cannot even expect any kinds of deterministic behavior. For example, consider the following short program:

#include <bits/stdc++.h>
using namespace std;
int main () {
    printf("%d\n", (int)pow(10,2));
    for (int j=0; j<3; ++j) printf("%d\n", (int)pow(10,j));
}

This code computes 10^2, 10^0, 10^1, and again 10^2. What is its output when using the current g++ version at Codeforces? 100, 1, 10, 99. Fun fun fun :)

For extra fun, change the initialization in the cycle to int j=2. The new output: 100, 100 :)

So, what should you do? Be scared and avoid pow() completely? Nah. Just be aware that precision errors may occur. Instead of truncating the value inside the variable, round it to the nearest integer. See "man llround", for instance.

That being said, it's time for the...

Level 2 answer. Wait a moment. Why the f*#& should there be a precision error when I'm computing something as simple as 10^2? Ten squared is clearly 100. Shouldn't the value returned by pow() be as precise as possible? In this case, 100 can be represented exactly in a double. Why isn't the return value 100? Isn't the compiler violating any standards if my program computes 99.99999999 instead?

Well, kind of.

The standard that actually matters is the C++ standard. Regardless of which one you look into (be it the old one, C++11, or C++14), you will find that it actually never states anything about the required precision of operations such as exp(), log(), pow(), and many others. Nothing at all. (At least to the best of my knowledge.) So, technically, the compiler is still "correct", we cannot claim that it violates the C++ standard here.

However, there is another standard that should apply here: the international standard ISO/IEC/IEEE 60559:2011, previously known as the standard IEEE 754-2008. This is the standard for the floating point arithmetic. What does it say about the situation at hand?

The function pow() is one of about 50 functions that are recommended to be implemented in programming languages. Doing so is optional -- i.e., it is not required to conform to the standard.

However, if a language decides to implement these functions, the standard requires the following: A conforming function shall return results correctly rounded for the applicable rounding direction for all operands in its domain. The preferred quantum is language-defined.

In this particular case, this is violated. Thus, we can claim that the Codeforces g++ compiler's pow() implementation does not conform to the IEEE floating-point number standard.

Hence, if you failed a problem because of this issue, do blame the compiler a little. But regardless of that, in the future take precautions and don't trust anyone.

Sometimes I want to rate a post by clicking the upvote / downvote button. And sometimes, especially when on my cellphone, I misclick and it registers the other one. Why oh why is there absolutely no way of undoing a misclick? This could be done either by clicking the same button again (returning the post to the state where you didn't vote), or by clicking the opposite button (switching your vote to the opposite one).

Here are the authors of tasks used at IOI 2015.

Day 1:

• boxes: Monika Steinová (SUI)
• scales: Eryk Kopczynski (POL)
• teams: Adam Karczmarz (POL)

Day 2:

• horses: Mansur Kutybayev (KAZ)
• sorting: Weidong Hu (CHN)
• towns: Bang Ye Wu (TWN)

Backups (not public):

• Ulugbek Adilbekov (KAZ)
• Vytautas Gruslys (LTU)
• Michal Forišek (SVK)

Which task did you like the most?

Hello :)

I was the writer for the Round 2. I'm very sad that the contest platform failed and you couldn't do your best solving them -- for me it's also sad as my work on the problems is now wasted. Hopefully you liked the problems themselves.

Here are the problem statements:

• A http://pastebin.com/raw.php?i=U8SfbSL8
• B http://pastebin.com/raw.php?i=bAi07eMm
• C http://pastebin.com/raw.php?i=R72vqKkk
• D http://pastebin.com/raw.php?i=Ar5CmJ8j
• E http://pastebin.com/raw.php?i=wiCtb0ab
• F http://pastebin.com/raw.php?i=iaMnb9cs

And below are brief solution ideas. Ask if anything is unclear.

A (ascending the stairs)

Dynamic programming in O(n).

Let W[x] be the number of ways to climb the first x steps of the stairs. (We will call that "state x".)

W[n] is the answer we want.

For each x, let y be the lowest state that we can go directly from state y to state x -- i.e., the sum H[y]+...+H[x-1] is still <= m. Then W[x] is simply the sum of W[y] through W[x-1].

Using two pointers, we can find the right y for each x in linear time. We can also maintain the sum of the Ws that corresponds to the current y and x.

B (back to the start)

Compress the coordinates. Then, realize that the optimal curve never has to pass through a corner of the unit square grid (we can always go around it on either side -- if the corner is available, so are the four sides that meet there). Thus we can turn this continuous problem into a discrete one and solve it using BFS. Consider the unit squares around the curve. Build a graph where two unit squares are adjacent iff they share a side and the curve doesn't use that side. Then, start the BFS from all four unit squares adjacent to the start and check whether you can reach at least one of the four squares adjacent to the end.

Generating good test data for this is a lot of fun :)

C (candy game)

This is known as misère NIM. Each color represents a pile in the game of NIM, and the number of candies of that color is the size of the pile.

The optimal strategy is the same as in the classical NIM: the losing positions are precisely those where the xor of pile sizes is zero. But there is one exception: if all pile sizes are 0 or 1, it is reversed: the ones with an odd number of 1s are losing.

Here is a proof: For situations where the largest pile is 1 it is obvious. In all situations where the largest pile has more than 1 token, the player who has the winning strategy in classical NIM can follow the same strategy in this NIM. This player must be the one who will eventually make the move that will lead into a situation with all pile sizes 0 or 1. And at this moment, the player may choose the opposite: if the winning move in classical NIM was to decrease the current pile to 0 she will decrease it to 1 and vice versa.

D (divisibility from last digits)

Obviously, we have to look at the k-th digit (zero-based index from the right) if and only if 10^k is not a multiple of d. Hence, we are looking for the smallest k such that d divides 10^k. This is only possible if d is of the form 2^a * 5^b, and the answer is max(a,b). Note that a can be at most 59. (Some solutions probably failed because they tried too few values for a, instead of simply dividing d by 2 while it still goes.)

E (exactly divisible by sum of largest digits)

The standard first trick is to write the answer as solve(b+1)-solve(a) where solve(x) counts all solutions in [100,x).

To implement solve(x), use three cycles to run through all possibilities for the three largest digits, and then count all numbers with those three largest digits. (I used two cases: I separately count those with fewer than x digits and then for each prefix of x I count those that are smaller than x in the last digit of the prefix. For example, if x is "1234567", one of the subproblems will be to count all numbers of the form "12341..".)

The core of the solution is a memoized recursive function go(a,b,c,found,rem,left) that generates the number from the left to the right. It has the following arguments:

• a,b,c are the three largest digits, with a>=b>=c. E.g., a,b,c = 9,7,7
• found is a bitmask stating which of them I've already used. E.g., found=5 means that a,c already appeared but b didn't.
• the number I have generated so far gives the remainder rem when divided by a+b+c
• left is the number of digits I still have to generate

Note that once I fixed a,b,c I can maintain the remainder modulo a+b+c while generating the number, and I also know that all digits other than a,b,c must be less than or equal to c.

F (fractions)

The simplest O(n log^2 n) algorithm by Patrascu and Patrascu, described in this paper, should be sufficient. (There are faster known algorithms but I didn't want to make the problem too hard.)

Today, there will be three official Algorithm rounds at the TCO finals: both semifinal rounds and the wildcard round in the evening. The precise times when these rounds take place can be found in the schedule. (Coding actually begins 30 minutes after the indicated starting time.) For all three rounds there will be live coverage done by me (misof).

What is the best way to follow the action?

1. Grab some snacks.

2. Join us in the TopCoder arena and enter the room for the contest. Talk to me there if you have some questions or requests!

3. Open the live coverage page for the live coverage.

See you there!

(P.S.: I will check the discussion here, but probably not during the rounds. If you have any quick questions, please msg me in the TC arena instead!)

Update: use the same link for finals!

Привет!

Это моя попытка писать по русски :)

Регистрация для IPSC 2014 открыта.

время начала: June 15, 2014 at 11:00 UTC

длина: 5 часов

здесь архив задача и IPSC Training Area

подробнее в английской версии :)

[ Hopefully I didn't make too many mistakes :) I only speak a little bit Russian :) ]