witua's blog

Codeforces Round #129
By witua, 12 years ago, translation, In English

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
  5. RAD
  6. bmerry
  7. Shik

Div2:

  1. xiaoshua2
  2. ahm.kam_92
  3. HanzhongBall_Quanling
  4. daidailanlan

You can read editorials here.

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

Comments Comments (85)
| Write comment?
»
12 years ago, # |
  Vote: I like it +22 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like 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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +139 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +98 Vote: I do not like it

        And if we go deeper...
        (7 + 4) * (4 + 7) = 74 + 47

        → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

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

        → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +39 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it +48 Vote: I do not like it

          Joke repeated twice becomes twice funnier!

          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
              Vote: I like it +26 Vote: I do not like it

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

            → Reply
»
12 years ago, # |
  Vote: I like it -21 Vote: I do not like it

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.. :|

→ Reply
»
12 years ago, # |
  Vote: I like it -15 Vote: I do not like it

Good luck in the lucky round!

→ Reply
»
12 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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...

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    IMHO, problem statements in this contest are completely clear, and you should just read them carefully

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I only point that problem statement without word exactly would be better.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    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!

    → Reply
»
12 years ago, # |
  Vote: I like it +53 Vote: I do not like it

Late system testing :( ?

→ Reply
»
12 years ago, # |
  Vote: I like it +39 Vote: I do not like it

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;
	}
→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can anyone explain me the idea?

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      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)

      → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Nice One !..

    → Reply
»
12 years ago, # |
  Vote: I like it -11 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it +33 Vote: I do not like it

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.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

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

    → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 3   Vote: I like it +13 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      It works with TreeMap...

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it +4 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
              Vote: I like it +4 Vote: I do not like it

            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.

            → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Hmm, thanks for info..

        → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
        ← Rev. 2   Vote: I like it +1 Vote: I do not like it

        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.

        → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it +2 Vote: I do not like it

      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. :)

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

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

        → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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. :)

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like 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 :(

          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              12 years ago, # ^ |
              ← Rev. 2   Vote: I like it 0 Vote: I do not like it

              Ignore

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                12 years ago, # ^ |
                ← Rev. 2   Vote: I like it 0 Vote: I do not like it

                As far as I remember, It will same to

                new HashMap(32) and it should not help

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Yes, my bad

                  → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                12 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                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).

                → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                12 years ago, # ^ |
                ← Rev. 2   Vote: I like it 0 Vote: I do not like it

                We have checked this. #TLE (3.6s)

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

                → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                12 years ago, # ^ |
                ← Rev. 2   Vote: I like it 0 Vote: I do not like it

                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...

                → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
              Vote: I like it +4 Vote: I do not like it

            Theoretically you can still remove it ;)

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              12 years ago, # ^ |
                Vote: I like it -7 Vote: I do not like it

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

              → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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

        → Reply
»
12 years ago, # |
  Vote: I like it -13 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it +81 Vote: I do not like it

tourist become first target!

→ Reply
»
12 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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?

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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? :)_

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The ratings are not updated yet.

    → Reply
»
12 years ago, # |
  Vote: I like it +6 Vote: I do not like it

what is wrong? div2 is unrated ?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
12 years ago, # |
  Vote: I like it +6 Vote: I do not like it

When will the rating be updated?

→ Reply
»
12 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

1885288

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks. Now I understand.

      → Reply
»
12 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For Little Elephant and Furik and Rubik (204C and 203E) I am getting a WA for http://codeforces.net/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).

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it 
    double div=n*(n+1)*(2*n+1);

    this code may overflow,because n is int

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
12 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Why my rating does not change?

→ Reply
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

no change in rating...

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
»
12 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it -9 Vote: I do not like it

      System must do it, not administration.

      → Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

DIV_2 the Rating is Updated !!!

→ Reply
»
12 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Liked the contest.

→ Reply
»
7 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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

→ Reply