witua's blog

By witua, 9 years ago, translation,

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:

1. tourist (now tourist become first Codeforces target, congratulations to him)
2. winger
3. RAVEman
4. rng_58
6. bmerry
7. Shik

Div2:

• +137

 » 9 years ago, # |   +22 Although there is no lucky problem but the round itself is lucky. 129=7+74+44+4 isn't it? :)
•  » » 9 years ago, # ^ |   +16 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
•  » » » 9 years ago, # ^ |   +139 129 = 4 + (7 + 4) * (4 + 7) + 4 — symmetrically lucky
•  » » » » 9 years ago, # ^ |   +98 And if we go deeper...(7 + 4) * (4 + 7) = 74 + 47
•  » » » » » 9 years ago, # ^ |   +8 (7 << 4) + 7 + 7 + 7 — 4
•  » » » » 9 years ago, # ^ |   +8 So one problem of the round was detected: return the number of ways, one can make 129 with lucky numbers :)
•  » » » » 9 years ago, # ^ |   +39 129=4+4+4+7+7+7+7+7+7+7+7+7+7+7+7+7+7+7+4+4+4
•  » » » » » 9 years ago, # ^ |   +48 Joke repeated twice becomes twice funnier!
•  » » » » » » 9 years ago, # ^ |   +26 He permutate digits. Now expression is palindromic :) And obviously more lucky :)
 » 9 years ago, # |   -21 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.. :|
 » 9 years ago, # |   -15 Good luck in the lucky round!
 » 9 years ago, # |   +14 nice short problem statements ; easy to understand ..Liked the contest :)
•  » » 9 years ago, # ^ |   0 no background stories FTW
 » 9 years ago, # |   +2 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 exactly mean that both colors must differ...
•  » » 9 years ago, # ^ |   +6 IMHO, problem statements in this contest are completely clear, and you should just read them carefully
•  » » 9 years ago, # ^ |   +1 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.
•  » » 9 years ago, # ^ |   +5 I only point that problem statement without word exactly would be better.
•  » » » 9 years ago, # ^ |   0 Yea, I understand , but why catching for one word when everybody understood the task properly and it was obvious enough what they ment :)
 » 9 years ago, # |   0 Could anyone give a hint on how to solve 204C - Little Elephant and Furik and Rubik? Thanks!
•  » » 9 years ago, # ^ |   +7 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 and divide these values by the total number of sunstrings. be aware of overflow!
 » 9 years ago, # |   +53 Late system testing :( ?
•  » » 9 years ago, # ^ |   -6 Cound witua tell us when will the system testing start?
 » 9 years ago, # |   +39 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: public void solve() throws IOException { long l = nextLong(); long r = nextLong(); out.println(f(r) - f(l - 1)); } long f(long x) { if (x < 10) { return x; } String s = Long.toString(x); return (x / 10 - 1) + (s.charAt(0) <= s.charAt(s.length() - 1) ? 1 : 0) + 9; } 
•  » » 9 years ago, # ^ |   0 Can anyone explain me the idea?
•  » » » 9 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 9 years ago, # ^ |   +6 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)
•  » » 9 years ago, # ^ |   +3 Nice One !..
 » 9 years ago, # |   -11 what the AWESOME!! great problem-set.. :)
 » 9 years ago, # |   +33 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.
•  » » 9 years ago, # ^ |   +2 someone included an anti-quicksort test long ago, and many java solutions failed. maybe something similar exists for hash-maps?
•  » » 9 years ago, # ^ | ← Rev. 3 →   +13 AFAIK, HashMap has 2^n buckets by default. So, If colors divides to big 2^k, it maybe slow? Does TreeSet work well?
•  » » » 9 years ago, # ^ |   +4 It works with TreeMap...
•  » » » 9 years ago, # ^ |   +3 Your submission with TreeSet http://codeforces.ru/contest/204/submission/1891800
•  » » » » 9 years ago, # ^ |   +3 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.
•  » » » » » 9 years ago, # ^ |   +4 I guess it's not linear on this test because of collisions
•  » » » » » » 9 years ago, # ^ |   +4 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.
•  » » » 9 years ago, # ^ |   +2 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
•  » » » » 9 years ago, # ^ |   +1 Hmm, thanks for info..
•  » » » » 9 years ago, # ^ | ← Rev. 2 →   +1 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.
•  » » 9 years ago, # ^ |   +16 If it was added by authors specifically for this purpose I think it is really bad
•  » » » 9 years ago, # ^ | ← Rev. 2 →   +2 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. :)
•  » » » 9 years ago, # ^ |   +1 It could be added after a successful challenge with this test.
•  » » » » 9 years ago, # ^ |   +1 That's why I added "if" in front of my comment
•  » » » » 9 years ago, # ^ |   0 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. :)
•  » » » » » 9 years ago, # ^ | ← Rev. 2 →   0 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 :(
•  » » » » » » 9 years ago, # ^ |   0 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.
•  » » » » » » » 9 years ago, # ^ | ← Rev. 2 →   0 Ignore
•  » » » » » » » » 9 years ago, # ^ | ← Rev. 2 →   0 As far as I remember, It will same to new HashMap(32) and it should not help
•  » » » » » » » » » 9 years ago, # ^ |   0 Yes, my bad
•  » » » » » » » » 9 years ago, # ^ |   0 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).
•  » » » » » » » » 9 years ago, # ^ | ← Rev. 2 →   0 We have checked this. #TLE (3.6s) But we'll update our generator for using with any initial numBuckets.
•  » » » » » » » » 9 years ago, # ^ | ← Rev. 2 →   0 It helps to use HashMap instead of HashMap and shift all values by r ( << r), where r is random int in [6; 32), but yes, this is ugly...
•  » » » » » » 9 years ago, # ^ |   +4 Theoretically you can still remove it ;)
•  » » » » » » » 9 years ago, # ^ |   -7 Is it possible to remove the test case and rejudge? It was good being purple for once :). My hopes are low though.
•  » » » 9 years ago, # ^ |   +14 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?
•  » » » » 9 years ago, # ^ |   +3 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
 » 9 years ago, # |   -13 It's amazing that whenever I don't participate in a contest, It's EASY!!!
•  » » 9 years ago, # ^ |   -7 Agree with you
 » 9 years ago, # |   +81 tourist become first target!
•  » » 9 years ago, # ^ |   +50 Congratulations!
 » 9 years ago, # |   +7 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?
 » 9 years ago, # |   0 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? :)_
•  » » 9 years ago, # ^ |   0 The ratings are not updated yet.
•  » » » 9 years ago, # ^ |   0 Ohh, it's okay then ^^ I was just curious eheh!! Nice round btw :)
 » 9 years ago, # |   +6 what is wrong? div2 is unrated ?
•  » » 9 years ago, # ^ |   0 I am asking the same :D I don't know about some big problems with the contest for div 2.
 » 9 years ago, # |   +6 When will the rating be updated?
 » 9 years ago, # |   +6 If the round is being rejudged or unrated or something wrong with rating calculation, please post an announcement in the blog.
 » 9 years ago, # |   0 Can anyone tell me why this code gets WA? Am I missing something tricky of Div2-A? 1885288
•  » » 9 years ago, # ^ |   +1 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.
•  » » » 9 years ago, # ^ |   0 Thanks. Now I understand.
 » 9 years ago, # |   +4 I've changed color but not raiting.whats wrong?
 » 9 years ago, # |   0 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).
•  » » 9 years ago, # ^ |   +1 yes, negative anwer means an overflow. But you'll get TLE anyway because of using 2D structure. Constraints are too large for it
•  » » » 9 years ago, # ^ |   0 Yes, thanks. Now I realize the problem and yes the code does TimeOut.
•  » » 9 years ago, # ^ |   +1 double div=n*(n+1)*(2*n+1);  this code may overflow,because n is int
•  » » » 9 years ago, # ^ |   0 Thanks, that was the problem. Although the code is slow to get passed.
 » 9 years ago, # |   +4 Why my rating does not change?
 » 9 years ago, # |   +5 no change in rating...
•  » » 9 years ago, # ^ |   +1 I think we are going to have to end up waiting for the next contest for the scores for 129 to update :(
 » 9 years ago, # |   +6 No one care the div2 participants's rating ? So irresponsible...
•  » » 9 years ago, # ^ |   0 VK Cup is coming up, so administration have no time for changing rating.
•  » » » 9 years ago, # ^ |   -9 System must do it, not administration.
•  » » » » 9 years ago, # ^ |   0 everybody forgot about Div2...
 » 9 years ago, # |   0 In problem E of div2 shouldnt the answer for the 2nd test case be: 0,357143 Instead of the presented one?
 » 9 years ago, # |   0 Rating for DIV2 will not be updated?
 » 9 years ago, # |   +3 DIV_2 the Rating is Updated !!!
 » 9 years ago, # |   +2 Liked the contest.
 » 3 years ago, # |   -8 How to solve Div-2 B, little elephant and sorting ? http://codeforces.com/contest/205/problem/B ?
 » 5 months ago, # | ← Rev. 2 →   0 How do i solve 205A, it gives wrong answer on test 9. My approach — if it contains two same time instances then print "Still Rozdil" else find the minimum time duration index element. My Submission : http://codeforces.com/contest/205/submission/118904525