yeputons's blog

By yeputons, 10 years ago, translation, In English
Problem A. Chat room
Solution is greedy algorithm. The first thing we do is find in our string the first letter 'h'. Then we find letter 'e' which is righter that found 'h'. If we find the whole word 'hello' in such way, obliviously, answer is YES.
Now let's prove that if answer exists, we find it. Let see on position of the 'h' in right answer. If we move it to the first 'h' in our string, nothing changes. But now we can say that our greedy algorithm correctly Now let's do such with the second letter, and so on.
We have greedy algorithm with work time O(n), where n - length of the input.

Problem B. Coins
This problem also have greedy solution: we run down all number from 2 and greater and while denomination of the last added to answer coin is divisible by current number, we divide and increase answer.
You can prove correctness, if you take a look at prime factorizations of coins' denominations. In each next denomination each prime have less or equal power than the current one (it's equivalent to 'a divide b'). Obliviously, if summary degree of primes decreases at least two (for example, we had numbera = x· y· z (where y, z > 1, and the current number is b = x), then we can add one more coin with demonitaion a > c = x· y > b. So, in the optimal answer sum of degrees decreasing at exactly one. Our greedy algorithm do exactly what it need.

Problem C. Trees.
The first thing we notice - beautiful sequence is can be determined with any member. The next thing - at least one tree will remain the same height. Prove: let's fix height of the first tree, and correct heights of all other ones. Obliviously, they all remain positive.
Solution with work time O(n2): we run down which tree we will fix, determine required height of the first tree and then relax answer.
This solution can be optimized to linear solution: if we don't touch some tree, we know the first element of sequence. Let's count for each possible element amount of trees, which have required height. It can be done with linear loop and the 'increment' operation on array. After that we just find value of the first element, for which amount of 'good' trees is maximal and output n - x, where x is this amount.

Problem D. Calendar

We know, that all lines of calendar should have equal length, so we can find this length. It's just , where suml - summary length of all strings. Now let take a look at string, which will be the first one in our calendar. Obliviously, it's profitably to take string with maximal s + d (where s is our string and d - is character from input). Such string is unique otherwise we have two equal strings in input (as d is not contained in any string); Of cause, you should remember that if you fix the first string in a line, you fix length of the second one - it's required to have at least one such. Great, now we know the first string in our calendar. Now let's determine the second one. We know it's length, so we need just to take minimal string with such length.
We know one line, let's do similary with the second line and so on.

Problem E. Expression
Under construction. The main idea is 3D dynamic with O(102) transition.

Read more »

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

By yeputons, 10 years ago, translation, In English
Let's go.

A. Autocomplete

In this problem you should read the statement and solve in any way. One of the most simple solutions is read string and last visited pages, sort (even bubble source - 1003 isn't a lot, 3rd power because we need 100 operations to compare two strings), and rundown pages. When we find good string, we should write it and exit.
If there are no such one, write source string. 'Goodness' of string is checking with one if (to check lengths and avoid RTE) and for.

Read more »

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

By yeputons, 10 years ago, translation, In English
Test code that I've created on contest:
http://pastebin.com/jvkUcZx3
I think that function should return the same results if it calles with byte-to-byte equas parameters.
But in this case they are distinct.
There is one more test program from MaxBuzz:
#include <cstring>
#include <cstdio>

int f(int x) { return 1 << x; }

int main() {
for (int i = 0, j = 42; i < 1000000; ++i)
if (!memcmp(&i, &j, sizeof(int))) 
printf("%d == %d\n", f(i), f(j));
return 0;
}
In this case f(j) is calculated on optimization phase, but f(i) and memcpy are calculated at run time. Optimizer thinks that 1 << 42 = 0, but CPU thinks that 1 << 42 = 1024.
This isn't a bug, because 1 << 42 is undefined.

Compiling with MSVC++ fixes this bug.

COLLECT_GCC=C:\Soft\MinGW\bin\gcc.EXE
COLLECT_LTO_WRAPPER=c:/soft/mingw/bin/../libexec/gcc/mingw32/4.5.0/lto-wrapper.exe
Target: mingw32
Configured with: ../gcc-4.5.0/configure --enable-languages=c,c++,ada,fortran,objc,obj-c++ --disable-sjlj-exceptions --with-dwarf2 --enable-shared --enable-libgomp --disable-win32-registry --enable-libstdcxx-debug --enable-version-specific-runtime-libs --disable-werror --build=mingw32 --prefix=/mingw
Thread model: win32
gcc version 4.5.0 (GCC)

Intel Core i3 M350 (x86)

UPD. I've tried it on CF servers. Bug is alive
UPD2. There is additional requirement: use optimizer (-O1/-O2)
UPD3. Two absolutely same submits got different outcomes: GCC - WA14 (240112), MSVC++ - OK (240115). Problem B from CF#49.

I'll be glad if you tell me my mistakes in English.

Read more »

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