tunyash's blog

By tunyash, 11 years ago, translation, In English

Hi all! This round is prepared by me, caustique, el_sanchez, KAN, malcolm. I thank Gerald, who has organised our work and helped us with tricky situations, MikeMirzayanov for the system of organasing contest Delinur for the translation.

I hope that all problems will be OK and everyone will find intersesting problem for him/her.

Winners:

div1:

  1. lovelymoon
  2. niyaznigmatul
  3. cerealguy
  4. ainu7
  5. cgy4ever

div2:

  1. dotato
  2. netman
  3. kybconnor_4

I apologise for the mistakes in statements. I will be more careful in the next time.

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

| Write comment?
»
11 years ago, # |
  Vote: I like it +13 Vote: I do not like it

scoring system?

  • »
    »
    11 years ago, # ^ |
    Rev. 2   Vote: I like it +28 Vote: I do not like it

    Standard. Score distribution is not defined at the moment

    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      The word is actually "standard". I've seen it get misspelled a lot on this site, it's about time I let people know how to spell it correctly.

      [http://www.oxforddictionaries.com/definition/english/standard] [http://www.merriam-webster.com/dictionary/standard]

      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it +27 Vote: I do not like it

        Thank you =)

      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it +68 Vote: I do not like it

        This is a common bug for all Russians :) In fact, the word "standard" in Russian is spelled like "standartny" with "t" but not "d". And even if you know the correct English spelling sometimes it may be hard to remember the correct ending.

        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it +37 Vote: I do not like it

          Cool, thanks! Now I know why it keeps happening! :)

»
11 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Oh,I smelt some special tricks..

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

    I think we should careful with problem A. :)

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

      yes ı misunderstood problem A. I thought digits bigger than k werent allowed :(

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

        Yes. And I was spend for 15 minutes to thinking about sample test 2 util the announcement appear

»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I guess the problems will be short and interesting. Like this blog.

  • »
    »
    11 years ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    You know what's interesting?

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

      Did you know facts are considered to be interesting. So this proves there are things that are universally interesting.

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

      I don't understand your mind clearly. But I think interesting 's different with every pepple. With me, that 's tricky test and many solution has ben hacked! O_o

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

hope problems will be good..

  • »
    »
    11 years ago, # ^ |
      Vote: I like it -16 Vote: I do not like it

    don't even hope that problems would be so easy for you

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

      A strange comment for a gray one...

      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it +17 Vote: I do not like it

        Guy that writes gray code?

        • »
          »
          »
          »
          »
          11 years ago, # ^ |
          Rev. 3   Vote: I like it -17 Vote: I do not like it

          No.Guy who has the rating very small(of colour grey).You are purple, I guess

»
11 years ago, # |
  Vote: I like it -74 Vote: I do not like it

giygctr gotcs metrr o'le!!

»
11 years ago, # |
Rev. 2   Vote: I like it +25 Vote: I do not like it

why is today's problemset so hard?

»
11 years ago, # |
Rev. 4   Vote: I like it +20 Vote: I do not like it

This round is similar to Round 144 Div1 standings This round prepared by tunyash too.

»
11 years ago, # |
Rev. 2   Vote: I like it +23 Vote: I do not like it

look at Antoniuk at div. 1. He worked well :D

P.S : He is in last page.

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

this exam very suck for div 2 everyone have solved A and B and no one able to resolve the C , D , E

  • »
    »
    11 years ago, # ^ |
      Vote: I like it -16 Vote: I do not like it

    I can't agree with U. Problem C was just an exercise for Range Tree, main problem was to realize it(I wasn't successful in it ._.).

    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +20 Vote: I do not like it

      sum(x,y,z,t)= (s[x]+...+s[y])*(s[z]+..+s[t]) = a

      you can solve this by fixed [x] and [y] and pre calculating [z] and [t]

      nothing about Range Tree i guess.

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone knows the 4-th test for B?

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If anyone can tell me what is the pretest 3 for problem A div 2 I would be very thankful...

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

    Show your code.

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

    The test would be like this:

    1 6
    01234567
    

    Answer should be 1.

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

      No leading zeroes are allowed, from my understanding:

      "The first line contains integers n and k (1 ≤ n ≤ 100, 0 ≤ k ≤ 9). The i-th of the following n lines contains integer ai without leading zeroes (1 ≤ ai ≤ 10^9)."

      So that wouldn't be a valid test....

      • »
        »
        »
        »
        11 years ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        No leading zeroes are allowed, so it can be like this:

        1 6
        12345670
        

        Answer still should be 1.

        MISTAKE: k-good number should contain each digits no more than k, but if number contains each digits no more than k AND other digits more than k, it still be k-good number.

    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      a[i] (1 ≤ a[i] ≤ 10^9)
      
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    case 2 0 0 0

    answer =2 your code gives 0

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

    1 0 10

    interesting observation about k == 9, but k == 0 ...

»
11 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Does anybody know what's the 5-th tests for C ? I would be very thankful

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Div 2. Problem C

The moment I realized I can't think better than O(n^3logn) or O(n^4) for MaxSum in a rectangle.

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

    That was the moment I realized the array contained only digits so I could do it in O(n^2).

    Most enlightening moment I got in a contest.

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

    I had an O(n^2log(n)) solution that I couldn't finish coding. I'm not sure if it is correct though, because it uses O(n^2) space.

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

    how do you do n^3logn?

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

where are the editorials/tutorial to div2 213?

»
11 years ago, # |
Rev. 11   Vote: I like it +26 Vote: I do not like it

The bad description of problem D div2(problem B div1) really makes me mad!!!!

I read it more than 5 times and still don't know what are you talking about, until I found the Note at the bottom and read the Note more than 5 times.

How can you use nothing to exchange something?

You should say:

Set x can contain nothing.

Set x and Set y can't contain the same item instead of the shit of "Note that each item is one of a kind and that means that you cannot exchange set {a, b} for set {v, a}. However, you can always exchange set x for any set y, unless there is item p, such that p occurs in x and p occurs in y.".

"John knows that his city has n items in total." Ok, there are n items in the city, but how many items in the market?

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

    For the second sample, why cost two days? why not three days? Input 3 5 1 2 3 output 6 2

    • »
      »
      »
      11 years ago, # ^ |
      Rev. 5   Vote: I like it 0 Vote: I do not like it

      first day = {} -> {1,2}
      now assume he leaves {1,2} at his home.

      second day = {} -> {3}
      so now he has all of {1,2,3} with him in two days.

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

        Thanks, I got it. It's hard to understand this problem of the poor description, but the solution seems not that hard.

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any Ideas for problem C , Div 2 ?

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

    You observe that in a rectangle the sum is (Ax1+A(x1 + 1)+...+Ax2)*(Ay1+A(y1 + 1)+...+Ay2), where x1,y1,x2,y2 are the corners, and the maximum sum of a sequence is 9*n.

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

    Range Tree. U just need to find all x1, y1, x2, y2: sum(x1, y1) * sum(x2, y2) == a. But you should do it smart: 1)Find all x, y: a % sum(x, y) == 0 2)for each of them find all x1, y1: sum(x, y) * sum(x1, y1) == a

    It seems like this solution is )(n ** 4 * log(a)(because of Range Tree)), but it is O(n**2 * k * log(a)), where k is number of divisors of a(close to log(a)).

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

      No range tree. You just need to factor n and n is equal to the multiplication of range sums that can be calculated in quadratic time

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

      No.You just keep a vector ap where ap[i]=number of sequences of sum i, i<=9*n. For a subsequence [i,j], if A%sum(i,j)==0, you add at result ap[A/sum(i,j)].Take care at the case when sum(i,j)=0 and when A=0

»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Anybody home ? someone start system testing

»
11 years ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

In problem A

When writing Let's call a number k-good if it contains all digits not exceeding k (0, ..., k).

Here, doesn't it mean that a k-good number can't have any digit greater than k ???

So far I know, it means, a k-good number can have all digits without those which are greater than k. Any digit in that number can't exceed 'k'.

It has given me a lot of pain.

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

    You cannot assume that it does not contain digits greater than k as long as it has not been mentioned in the statement.

    Actually, you just cannot assume something when it has not been specified in the problem statement.

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nooo, finally found out one minute after the competition, that my C gave time limit exceeded because I forgot to print the final \n. First time I've had that bug :(

»
11 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Got owned for the 100th time by integer overflow for div1 A T_T

  • »
    »
    11 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    <epic fail>
    in my code was:

    typedef int li;
    ...

    #define int li
    </epic fail>
    P.S. Of course, it must be typedef long long li

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

    Same here, mistakes like this will kill me someday.

    Hoping rating doesn't decrease much ...

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

    Overflow too. T_T

»
11 years ago, # |
Rev. 2   Vote: I like it +114 Vote: I do not like it

Congratz lovelymoon for his E 5163338 :D (11.996s, TL is 12s)

»
11 years ago, # |
  Vote: I like it +63 Vote: I do not like it

What is the intended solution for Div1 C? Is it possible to prove it without testing all valid inputs?

  • »
    »
    11 years ago, # ^ |
    Rev. 2   Vote: I like it +16 Vote: I do not like it

    UPD: Sorry, here was the solution for B, not C.

    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      Correct. That is, however, the solution to Div1-B :)

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

        Ah well, that makes sense:) Sorry

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

          Well, since you already wrote it, you should probably leave it around, maybe in a separate thread.

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

      I think this is solution for Div1 B, not Div1 C

    • »
      »
      »
      11 years ago, # ^ |
      Rev. 2   Vote: I like it +3 Vote: I do not like it

      I understand that the reduction works, but why does that mean that the restriction doesn't mean anything? Why can't the algorithm still find a move that is illegal?

      • »
        »
        »
        »
        11 years ago, # ^ |
        Rev. 2   Vote: I like it +8 Vote: I do not like it

        Consider any two sets A and B, with c(A) + d >= c(B). Let their intersection be denoted as C, meaning A\C and B\C don't have anything in common.

        c(A) = c(A\C + C) = c(A\C) + c(C) >= c(B) — d = c(B\C) + c(C) — d

        c(A\C) >= c(B\C) — d

        We can substitute set A\C with set B\C, thus turning A into B.

        Therefore, for any two sets A and B such that c(A) + d >= C(B) we can turn one into another in one step.

        Every step in our algorithm does exactly that, so every move we make is legal.

        Does that explain it?

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

          Yep, I got it now, thx.

        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it +18 Vote: I do not like it

          I thought we have to swap whole set we have currently with some other set. Really poor problem statement. :(

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

            Yes, I thought that too, until I analyzed the sample test cases.

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

    Mmm. My solution constructs correct set with k' ≥ k elements. It's possible to prove, that we can obtain correct set for any k. But then I use statistic to prove, that I can obtain correct set with exactly k elements. I will write about it in editorial.

»
11 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Nice contest and interesting problems.... Like your other contests....thanks!

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there an alternate solution for Prob:C Div2 ? Something using Data-Structures ?

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

k-good numbers input 1 0 1000000000

Output

1

really 1<0?

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

    It must contain all digits who doesn't exceed k, so if 0 wasn't present, the number was invalid. But it can contain digits who exceed k, that's not a problem. So, yes , 1 > 0, but 1 0 1000000000 should get for output 1

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

      very bad translation, it is k-good if it contains all of (0,..,k) was better, I'm not American by the way

    • »
      »
      »
      11 years ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      kind of know the reason. "the number contains all digit from 0 to k " is not equal to " the number only can contains all digit from 0 to k.". I should not have this assumption.

      • »
        »
        »
        »
        11 years ago, # ^ |
        Rev. 4   Vote: I like it +1 Vote: I do not like it

        Actually problem is in "not exceeding k (0, ..., k)". There was no need of this portion.

        When writing Let's call a number k-good if it contains all digits not exceeding k (0, ..., k). it means, a k-good number can have all digits without those which are greater than k. Any digit in that number can't exceed 'k'.

        Anyway which happened it was to be happened. No doubt, short description of last contest was nice to see. But we also hope better translation from this great community.

»
11 years ago, # |
  Vote: I like it +12 Vote: I do not like it

tanks for the contest. this was to this date my best contest and I don't think I am ever going to get a better rank in codeforces. I didn't like problem C, I solved using simple backtrack. problem A and B and D were great.

»
11 years ago, # |
  Vote: I like it +11 Vote: I do not like it

That moment in which you get WA #115 on Div1-D because you forgot that rand() only goes up to 32767... :(

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

    Can you describe your idea?

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

      Suppose you know GHD divides some element a[i] of the array. You can then take the gcd of a[i] and all other elements, and count how many times each of the divisors of a[i] also divides other elements of the array (should be easy to do in n log n). The largest one that appears more than n/2 times is the GHD.

      Now, the question is finding such an element a[i] quickly. But as GHD divides at least half of the a[i]s, the chance that you take an a[i] that has the required property is over 50%! So just take a[i]s randomly until you run out of time.

      • »
        »
        »
        »
        11 years ago, # ^ |
        Rev. 2   Vote: I like it +5 Vote: I do not like it
        for (int i = 0; i < d.size(); i++) {
                 for (int j = 0; j < i; j++) {
                    if (d[i] % d[j] == 0) cnt[d[j]] += cnt[d[i]]; 
                 }
              }
        

        I see such chuck of your code. It doesn't seem to be O(NlogN) as announced in your short editorial, it's rather O(NlogN + (number of divisors of a[i])2 which consumes much more time.

        Can you tell how you're going to process this part of solution in O(NlogN) time?

        • »
          »
          »
          »
          »
          11 years ago, # ^ |
          Rev. 3   Vote: I like it 0 Vote: I do not like it

          Maximum number of divisors for a number up to 1012 is less than 7000. So it is not considerably worse than O(NlogN) part I think.

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

            It's true assumption when one is trying to code working solution during a contest but what if the numbers will be up to 10^16? You still we be able to factor one number quite quickly and to calculate all GCDs quickly but the part with 2 loops to traverse list of divisors will be bottle-neck in such solution.

            I'm just trying to figure out better approach to solve this problem.

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

          vector d represent the divisors of a[idx] which is theoretical have at most 2*sqrt(a[idx]) elements. but practical it is much less.

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

        What a weird solution !

        thank you.

  • »
    »
    11 years ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it

    that too, it was the last test! really unfortunate!

»
11 years ago, # |
  Vote: I like it -9 Vote: I do not like it

please update ratings! thank you so much

»
11 years ago, # |
  Vote: I like it -22 Vote: I do not like it

I hope Petr rise again :)

»
11 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

:)

»
11 years ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

I just found the "problem revision"(30) in the detailed submission page.
But What is the problem revision? Thanks for help!

Problem Lang Verdict
365D — 30 GNU C++ Wrong answer on test 8

»
11 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

This contest is very great, with so many rand() needed and some hard problems :-P

»
11 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Editorials please !! :)

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

hi everyone, for problem B,

why this verdict???

1 1000 Answer 1 Checker Log wrong answer Answer contains longer sequence [length = 1], but output contains 0 elements

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could anyone have a look on my submission 5162269 for Matrix problem? I don't understand why I am getting a run time error...

  • »
    »
    11 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
      if(a%(it->first) ==0 && m.find(a/(it->first))!=m.end() ){
    

    It looks like you divide by zero in this string.

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

    i think it maybe because you are trying to compute a%(it->first) and a/(it->first), but the value of it->first maybe zero if the string contains a 0 character.

»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Thanks for the contest, Finally I became blue!! :D ..

»
11 years ago, # |
  Vote: I like it +8 Vote: I do not like it

at the very beginning i got problem A,B done within half an hour while just before the contest end,i wrongly took the lower bound of ai as 0 and think i may be able to hack some careless guys who also didnt handle the data 0,so i quickly submitted problem A again with speical judgement for the case when ai is 0,...then the system reply tell me ai must be >= 1.and my rank in room suddenly drop from 8 to 16.. it really proves that evil will be rewarded with evil.ToT

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

A and B 's very easy. But C 's so hard. (Just with me :) )

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

i liked the problems, though i could not participate

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there someone fix the description of problem D. Free Market? How to understand this statements: "Note that each item is one of a kind and that means that you cannot exchange set {a, b} for set {v, a}. However, you can always exchange set x for any set y, unless there is item p, such that p occurs in x and p occurs in y.". For the samples, second one, why 2 days? one change a day, at least three days? input 3 5 1 2 3 output 6 2

How could those get AC?

»
11 years ago, # |
  Vote: I like it +14 Vote: I do not like it

I look forward to editorial

»
11 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Thanks for beautiful problems.I enjoyed so much :)

»
11 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Unbelievably lucky! lovelymoon's (div1 winner) E problem takes 11996 ms (TL is 12s) on the maximum test case :)