Hi!

Time brings to you next **Codeforces** round, this time it is with number **129**. It will take place in 11.07.2012 at 19:30 (Moscow time). This time the problems are authored by me, Vitaliy Herasymiv. Long time ago I was the author of 4 Codeforces rounds, they were about lucky numbers. But, unfortunately, nothing is constant, so this time there will be no problems about lucky numbers.

A lot of help in preparing of the problems was from Gerald Agapov (Gerald), Alexander Kouprin (Alex_KPR), Vitaly Aksenov (Aksenov239), The problems were translated to English by Maria Belova (Delinur). Thanks to all of them.

I hope you will like this all.

Good Luck!

Div1:

Thanks all! The results are the following:

- tourist (now tourist become first Codeforces target, congratulations to him)
- winger
- RAVEman
- rng_58
- RAD
- bmerry
- Shik

Div2:

You can read editorials here.

Although there is no lucky problem but the round itself is lucky. 129=7+74+44+4 isn't it? :)

actually, it's unbelievable!

129=7+7+7+7+7+7+7+7+7+7+7+7+7+7+7+4+4+4+4+4+4

129 = 4 + (7 + 4) * (4 + 7) + 4 — symmetrically lucky

And if we go deeper...

(7 + 4) * (4 + 7) = 74 + 47

(7 << 4) + 7 + 7 + 7 — 4

So one problem of the round was detected: return the number of ways, one can make 129 with lucky numbers :)

129=4+4+4+7+7+7+7+7+7+7+7+7+7+7+7+7+7+7+4+4+4

Joke repeated twice becomes twice funnier!

He permutate digits. Now expression is palindromic :) And obviously more lucky :)

hope this time problem set will have good English translation.. I have seen that sometimes GOOGLE TRANSLATOR give better translation.. that time i am trolled.. :|

Good luck in the lucky round!

nice short problem statements ; easy to understand ..Liked the contest :)

no background stories FTW

cite from DIV2.D (second sentence of statement):

`He has n cards, each has exactly two colors`

and the last one of input section:

`The color of the front of the card may coincide with the color of the back of the card`

In my opinion word

exactlymean that both colorsmustdiffer...IMHO, problem statements in this contest are completely clear, and you should just read them carefully

If it wasn't mentioned that the color of the back may coincide with the color of the front, then it would be unclear, but it's clearly enough mentioned and if you didn't read it , it's your own faulth for not reading carefully.

I only point that problem statement without word

exactlywould be better.Yea, I understand , but why catching for one word when everybody understood the task properly and it was obvious enough what they ment :)

Could anyone give a hint on how to solve 204C - Little Elephant and Furik and Rubik? Thanks!

First of all let xi and yj be the same letter in string X and Y respectively. The number of substrings of the same length in X and Y that contains xi and yj is: (1+prefixSize(min(i,j)) * (n-suffixsize(max(i,j)) in 0-based array Now for any matched xi and yj characters, find the number of all such substrings. this code runs in O(n^2) and obviously wouldn't fit in time. Consider that if j<i the above formula becomes (1+prefixSize(j))*(n-suffixSize(i)). So for each letter iterate over i and keep the summation of (1+prefixSize(j)) for all j<i using dynamic programming and multiply it by ((n-suffixSize(i)). do it again for j>=i and divide these values by the total number of sunstrings. be aware of overflow!

Late system testing :( ?

Cound witua tell us when will the system testing start?

While browsing through some of the solutions ,I found this amazing short one by winger for Div1-A/Div2-C..Very nice and simple solution that most of us missed:

Can anyone explain me the idea?

I have similar solution.

F(x) is number of tens, which less or equal to X, and 9 (numbers 1..9). One thing — if first digit of x > last digit of x (examples — 51 (5 > 1), 623 (6 > 3)), we mustn't count last ten, so we subtract 1.

Its simple..The function f(long x) returns the number of the numbers that have the same first and last digits. So if x < 10 then that all the single digit numbers less than x are what we are looking for and so x is returned .Otherwise u can see that for all the numbers whose length >=2 have the unit place digit will be equal to the highest order digit exactly ones in every 10 numbers .So we add x/10 to our result. -1 is because we dont want to add the single digit numbers and for them we add a +9. The remaining part is just for checking if the residue of the number when divided by 10 can also be used or not .

Finally becuase we need to count that in the interval [l,r] we find f(r) and the subtract from it f(l-1)

Nice One !..

what the AWESOME!! great problem-set.. :)

My thanks to witua for the contest!

Does anyone have an idea what is 71 test (Div-1, B) about? Many java solutions failed with TLE on this tricky one.

someone included an anti-quicksort test long ago, and many java solutions failed. maybe something similar exists for hash-maps?

AFAIK, HashMap has 2^n buckets by default. So, If colors divides to big 2^k, it maybe slow? Does TreeSet work well?

It works with TreeMap...

Your submission with TreeSet http://codeforces.ru/contest/204/submission/1891800

Yeah, I already checked this. It is rather slow (720ms), but nevertheless. I still don't get whether this is some magic test or linear solution may fail out of HashMap inefficiency.

I guess it's not linear on this test because of collisions

I get that. "Magic" stands for bringing down java hash map (it's specific hash function, which you may find in java sources) on purpose.

Please note that hashMap uses special precaution to counter it — instead of using hash value right away, it uses h ^ (h >>> 20) ^ (h >>> 12) ^ (h >>> 7) ^ (h >>> 4). Hence one need to carefully prepare anti-HashMap test

Hmm, thanks for info..

We have made it about an year ago for using in hacks. This transformation can be inverted in a similar form.

Upd. It works regardless of Java version and input sorting/shuffling.

If it was added by authors specifically for this purpose I think it is really bad

Had the same thought. If it was added intentionally, then (as PeterGriffin mentioned), if it comes to that, why couldn't authors always add an anti-quicksort test for all java solutions to fail. :)

It could be added after a successful challenge with this test.

That's why I added "if" in front of my comment

I bet you're right. I took a look at the tests previews, and it seems that the authors have 63 tests, give or take. Curious situation. Perhaps Vitaliy could clarify what was it. :)

Well, that test was not added by me and it was added during the contest, so I haven't noticed it. I also think it is a bit bad :(

Ok. Then, as it comes to me, it's a cruel lesson about not using HashMap class on Codeforces. Worth mentioning that it is especially funny because there is no way to do such mean things on TopCoder.

Ignore

As far as I remember, It will same to

new HashMap(32) and it should not help

Yes, my bad

Egor, map capacity is still chosen as the power of two, so it doesn't change anything, even the load factor doesn't work (correct me, if I'm wrong).

We have checked this. #TLE (3.6s)

But we'll update our generator for using with any initial numBuckets.

It helps to use HashMap<Long> instead of HashMap<Integer> and shift all values by r ( << r), where r is random int in [6; 32), but yes, this is ugly...

Theoretically you can still remove it ;)

Is it possible to remove the test case and rejudge? It was good being purple for once :). My hopes are low though.

Why is it so bad?

Sorry, but really, in this thread, I could not find any arguments at all. Everyone just silently accepts it's bad. It may well be so, but why?

I see at least couple of reasons: first, c++ people use tree map by default without thinking about it — it is a bit of unfair advantage, second, if we add test for Java we should add such test for every supported language that has hash map in standart library and is subject to similar exploit

It's amazing that whenever I don't participate in a contest, It's EASY!!!

Agree with you

tourist become first target!

Congratulations!

Excellent competition, I enjoyed solving the tasks and they were all very clear. One of the better ones in a long while for me.

By the way, is there something wrong with my browser, or did all the rating changes in Div2 for this contest get removed? If so, when can we expect it fixed?

I only solved one problem... I will try to improve and get better, but shouldn't I have gained some more points on my rating? :)_

The ratings are not updated yet.

Ohh, it's okay then ^^ I was just curious eheh!! Nice round btw :)

what is wrong? div2 is unrated ?

I am asking the same :D I don't know about some big problems with the contest for div 2.

When will the rating be updated?

If the round is being rejudged or unrated or something wrong with rating calculation, please post an announcement in the blog.

Can anyone tell me why this code gets WA? Am I missing something tricky of Div2-A?

1885288

Even if there is a pair of same numbers, it doesn't mean that there's no less number than those. That is, I think you should check all the numbers before everything.

Thanks. Now I understand.

I've changed color but not raiting.whats wrong?

For Little Elephant and Furik and Rubik (204C and 203E) I am getting a WA for http://codeforces.com/contest/204/submission/1894333

The test case that fails gives a negative answer. Am I running into overflow errors? Also what I have done is that I first collect the indices of all the alphabets into a 2D structure and then try to match the corresponding characters. Also is it possible to get the complete test case locally at which my solution fails. The testers shows the partial test case? (If not this functionality should be there).

yes, negative anwer means an overflow. But you'll get TLE anyway because of using 2D structure. Constraints are too large for it

Yes, thanks. Now I realize the problem and yes the code does TimeOut.

this code may overflow,because n is int

Thanks, that was the problem. Although the code is slow to get passed.

Why my rating does not change?

no change in rating...

I think we are going to have to end up waiting for the next contest for the scores for 129 to update :(

No one care the div2 participants's rating ? So irresponsible...

VK Cup is coming up, so administration have no time for changing rating.

System must do it, not administration.

everybody forgot about Div2...

In problem E of div2 shouldnt the answer for the 2nd test case be:

0,357143

Instead of the presented one?

Rating for DIV2 will not be updated?

DIV_2 the Rating is Updated !!!

Liked the contest.

How to solve Div-2 B, little elephant and sorting ? http://codeforces.com/contest/205/problem/B ?