Oh, come on, leave a space for a joke in this post!

Otherwise I should probably remove 'on this site', I bet he solved WAY MORE than this number of problems.

I think, marat.snowbear talked about the coder like those, who has just started their competitive programming life. If you tell about tourist, he started his journey in codeforces in 2009. But before it, he achieved gold medal in 2007, 2008 and silver medal in 2006 in IOI.
One of his famous remarks, made in an interview after the IOI 2009, was "I am no genius. I am simply good at it." (I have known it from wiki). So actually he was simply good even before he started in this site. :)

But my question to marat.snowbear is, why it is 1513 exactly ?? :P
What is about 1512 ??? :P

At first, I thought reading full blog will be boring... :P
But after reading full blog, it has given me some pleasure. :)
You have made me known about Saint Petersburg zoo. And nice to see you as a good husband. :)

Please Ignore.

But it's one of the most interesting posts I have ever seen. I even tried to remember the heroes of this contest :D

I think that the author took the contest very seriously, let's wait for the problems :)

There is a mem in Russian saying that "while you're sleeping your opponents are levelling up" (originally it was about some online game where you need to spend a lot of time to level up further). Same saying works for watching movies ;-)

So, how was the movie?

If you really understand it from that line, then wait until 1513 rounds in codeforces. :O
It has taken 5 years to complete 268 rounds. From normal mathematics, you have to wait more than (28-5)=23 years more !!! Hope you will be RED after that time !!!

Same here

Well, I think the answer here might be unclear a bit but here it goes. Yes, I think this experience changed me as a programmer, there is no way it won't affect me taking into account the total time I spent on this site solving problems and learning new algorithms and data structures. But the practical outcome of this change is not that huge, might be not even noticeable to other people. In result if you look from practical point of view only then all I got is 5-10 T-shirts and some better chances on Google interview. I have never had a job which require algorithms/data structures skills, at least not of orange/violet level. I also became a bit better in some other programming areas, like debugging things in mind for example, this is helpful when doing code review. But all of these in total is not that much taking the time into account again.

So I would say it's a bit different, my only point of doing this was always the fun. I was always a fan of similar problem-solving sites since my high-school years. I started on sql-ex where you can solve similar problems in SQL, then I moved to project euler with its focus on maths, now I'm here. I would say that I'm here because I am already the way I am, so this site cannot change me much, neither as a person nor as a programmer.

My opinion is that this site for me is for fun only, if you want to learn data structures or algorithms or become better in any other programming area then there other more effective ways of doing that, at least unless you're looking for some red-level skills.

Oh, and I have just remembered one more thing where this site changed me as a programmer. After spending an year on this site I became completely bored on my job, so now I'm unemployed for the third month so far. Even though I receive around 15-20 propositions on LinkedIn per month, I'm not interested in those, so I stay here. Stay aware of this path!

Hope this helps and doesn't sound too depressing :-) Marat.

Yes it was really good contest=)

I'm just worry about system test queue

How did you know???

Form two arrays of difference between height of current tower and the previous one. Now search small array (elephant's towers) in the big one (bears' towers) like a substring in text. Special case to consider is that if w = 1.

For special case w = 1, output n.

Now observe that we can take the differences of consecutive elements, so searching for elephants is essentially finding the difference-elephant in the difference-wall. For example, if the wall is [3, 4, 5, 6, 1, 2, 3] and the elephant is [2, 3, 4], we can compute that the difference-wall is [1, 1, 1,  - 5, 1, 1] and the difference-elephant is [1, 1], so there are three such occurrences. Indeed, the elephant appears on subsequence a₁, a₂, a₃ (after raising by 1 to [3, 4, 5]), on subsequence a₂, a₃, a₄ (after raising by 2 to [4, 5, 6]), and on subsequence a₅, a₆, a₇ (after lowering by 1 to [1, 2, 3]).

Now this is essentially searching substring in a string, only with large alphabet (which doesn't matter). We use Knuth-Morris-Pratt algorithm or something like that to find them in O(n + w) time instead of O(nw).

I think it can be solved taking the diferences between walls and then string matching(kmp for example) but I got wrong answer on pretest 2.

and Hack.Me just registered 2 hours ago :(

How can you know ? Maybe Hack.Me wrong on Test 171 ? And my opponent is worse

=D

Is it to match the difference of the w with difference of the other string ?

What is the hack case for A , my soln is like this

more than 3 = Alien
3 different stick = bear
less than 3 = Elephant

Solved A in 13 min. Boring screencast (locale: ru; lang: Perl).

You can look my solution http://pastebin.com/V3jPNSjK

Let's denote by Hi = the minimum number of card which should be available in order to build a castle of height i. We may find the exact formula, or calculate this number inductively (Hi = H(i-1) + 3i-1). Having this formula, we realize that the maximum height a castle can have is around sqrt(n). So we can iterate through all possible heights. In order to check whether or not we may build a castle of height i with exactly n sticks, we have 2 conditions:

1) n >= Hi 2) (n-Hi) is divisible by 3

For a floor with a rooms in it, there are b cards in it, that:

b = 2a + (a - 1) = 3a - 1

So, if we can build n cards into a house with k floors, following statement will take place:

n = 3x - k, k + n = 3x

where x is sum of k different summands. It can always be written as x = 1 + 2 + 3 + ... + (k - 1) + y, where y is some integer greater than (k - 1)

When we know it, we can write solution: 7970170

Observe that the number of cards in a floor is 2k + (k - 1) = 3k - 1 where k is the number of houses there. Thus the number of cards used will be . In other words, the number of floors and the value of n must add up to a multiple of 3 (namely ).

Let there be f floors. Since we don't care about the number of houses on each floor, only that higher floors have less houses than lower floors, we might as well set the highest floor to have 1 house, the second highest 2, and so on until the second lowest, and put the rest of the houses at the bottom. In order for this to work, we want (3·1 - 1) + (3·2 - 1) + ... + (3·f - 1) ≤ n.

Now we can use a simple algorithm or a more difficult algorithm.

The first algorithm is simply to loop over the number of floors from 1. Note that is quadratic on f, so this has an upper bound somewhere around , quick enough for the constraints. As long as minH = (3·1 - 1) + (3·2 - 1) + ... + (3·f - 1) ≤ n, we check if ; in that case, increment the result, as f is a possible answer.

Using the example, n = 13:

• f = 1. We have minH = 2 ≤ 13 = n, so we check if ...nope, since .
• f = 2. We have minH = 2 + 5 = 7 ≤ 13 = n, so we check if ...yes, it is, . So we increment the result.
• f = 3. We have minH = 2 + 5 + 8 = 15 > 13 = n, so we don't have enough cards for three floors, much less for more floors. So we break out from the loop and return 1 as our count.

The second algorithm relies on another observation. Note that we want to find the highest value of f where . We manipulate this algebraically:

3f² + f ≤ 2n

(6f + 1)² = 36f² + 12f + 1 ≤ 24n + 1

Thus, if we can make the square root with sufficient precision, we can compute the largest integer value of f; simply do .

Now, if , we count the floors 1, 4, 7, .... If , we count the floors 2, 5, 8, .... If , we count the floors 3, 6, 9, .... So if we add to the floors, we always end up counting the floors 3, 6, 9, ..., which is simply . So given this, the final result is simply .

(EDIT: Codeforces is under heavy load ok. Why doesn't \pmod exist?)

Yeah, I underestimated E, my fault. Could have a problem for D for the first div :-)

It's even sadder when you use a wrong formula for Problem C and realize the correct one when don't have enough time to correct it:(

You have to be really new here if you consider such experience as very painful ;).

contribution is not needed

At first, sort the input array. You just need to permute the array 3 times that the three permutation is same. If it is possible(if two or more pair have the same value or any of three or more numbers are same) then print the value of index by their permutation, for example see the discussion which is written below the problem statement.Hope it will help. =D

I don't want to be jerk but it seems like that you cheated. Style of coding is really different, so I think that someone gave you code, which would be skipped as it in your case.

Because of

#define int ll

What is your problem here? It looks ok.

void create_test(){
	cout << 200000 << ' ' << 100000 << endl;
	for (int i = 0; i < 200000; ++i)
		cout << 1000000000 << ' ';
	for (int j = 0; j < 100000; ++j)
		cout << 1000000000 << ' ';
}

This solution running more then 3 seconds on this test on my pc.

What do you think is a corner case in A?

There is no way for you to see the full test. 7th test is simply 2000 random numbers. Maybe it's not the bug that failed your solution here but you seem to have an overflow when counting the number of possible permutations. You're multiplying them and they can easily become negative.

Problem is in this cycle:

for(it = M.begin(); it != M.end(); it++)
	{
		VI v = it->S;
		perm_no = perm_no*1LL*SZ(v);
	}

perm_no can be easily as big as 2¹⁰⁰⁰. This does not fit in 64-bit integer type. But you can break from cycle, when perm_no >= 3:

for(it = M.begin(); it != M.end(); it++)
	{
		VI v = it->S;
		perm_no = perm_no*1LL*SZ(v);
                if (perm_no >= 3)
                    break;
	}

This change makes solution AC: 7976891.

Create another fake account