Wild_Hamster's blog

Codeforces Round #308 (Div. 2)
By Wild_Hamster, history, 9 years ago, translation, In English

Greetings to the Codeforces community!

Regular Codeforces round #308 for participants from the second division will take place on 18 June, 19:30 MSK. Participants from the first division are able to participate out of the contest.

It is my second round on Codeforces(First round — Codeforces Round 280 (Div. 2)). Hope you will enjoy this round.

I want to thank Max Akhmedov (Zlobober) for help with preparation of this round, Maria Belova (Delinur) for translation of statements and Mike Mirzayanov (MikeMirzayanov) for great Codeforces and Polygon systems.

Participants will be given five problems and two hours to solve these problems.

UPD: Scoring is standard: 500-1000-1500-2000-2500.

UPD: Congratulation to the winners:

  1. Ttocs45

  2. RNS_JKS

  3. RNS_CUS

  4. kouekosita

  5. grenade

UPD: Contest is over. Thanks for participating :)

UPD: Editorial

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

Comments Comments (222)
| Write comment?
»
9 years ago, # |
  Vote: I like it -57 Vote: I do not like it

i hope this round has harder problems than round #280.

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

    Your last round was interesting and solvable ! I believe it will be easier than round 307 :)

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

    just noticed round #280 is my first contest in code forces. Well, and after this round I am in Div-1, so when is the next round maybe i will be red :D

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

      You are really lucky to get your solution for D passed! :P :D

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

      My history:

      First Codeforces round participation = round #235

      First Codeforces round to get in div1 = round #263

      difference in number of rounds = 28

      Your history:

      First round = 280

      First round to get in div1 = 308

      difference = 28

      And my current rating is the same as that after round 263 . So clearly this is not a good metric to judge how soon you would become red :)

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

Happy Ramadan holiday to all. I wish luck for today's contest to every participants.;)

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

I hope this round have some problems which i am not able to solve.

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

    then u should attempt div 1 mate !!!

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

      The fact is that in many div 2 only contests there are some problems which are very hard and brilliant!Beyond that , i participate unoffically this contest so it is more important for me to learn something new than to get a good rank.

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

Wild_Hamster has a recursive profile pic

how did you make it

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

    His profile pic is in Russian, but my interface is in English :)

    Also the rating and contribution are different.

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

    My guess would be 1. take a screenshot of your profile. 2. copy+paste 3/4th of the screenshot to the remaining 1/4th space by reducing its size. 3. Repeat 3-4 times till its possible to do this within the smaller window each time. But this is just my guess.

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

    блиииин, забыл зарегатся(((((

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

Every contest is simply amazing !! Somebody will participate officially , others no , but the idea is improve in each contest. enjoy the problems and keep the calm !! Good luck and Have fun to everyone !!!

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

I hope that there will be no delay, no lag near the end of contest, and no cheaters :)

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

I think it's time to publish scoring

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

When you know you are closest user to Div.1 but you know it will not be happen :(((

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

Please announce scoring.

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

Please Register me for this round please.Please

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

Did you notice live judgement updates on the status page? Do not hope to see verdict faster by pressing F5, this page now gets live judgement stream directly from the judging module!

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

    codeforces everyday growing! Keep on!

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

    5-10 seconds of the highest quality drama on every submit! (Jaws music on the background) :)

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

For me it's really interesting why each Div2 round there are persons like this http://codeforces.net/profile/liyankui who solves all the problems without participating in any other contest before.

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

    I'm gonna be captain obvious here in case there's someone that doesn't know — Div1 users make new accounts to win Div2.

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

      Ok, what is the goal of doing it?

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

        Very frustrating I know. What is the point of red/orange coders beating div 2 guys? What are they trying to achieve this way? Its somehow fun and exciting for them, but very frustrating for div 2 participants.

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

        There is none, they just want to see themselves on the blog and feel good for being top5. We've all agreed it's a stupid practice, and it has been discussed tons of times before.

        Sadly there is no efficient way to stop them from doing it without limiting other competitors.

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

Its not programming contest, its math contest...

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

    Brute Force, Digit DP, Number Theory ( ok, this one is math ), Geometry and I am not sure about the last one since I couldn't solve it. It was somewhat balanced I guess.

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

      C is brute force :D

      when w=2 or w=3 the answer is always YES , when w>3 you will not use more than the first 16 weights so you can use O(3^16) brute force

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

        not necessarily, my solution uses 100 iterations only

        http://codeforces.net/contest/552/submission/11642323

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

          ok I didn't say it can't be solved faster but constraints allow brute force to pass

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

        it could even be done in O(216) . You assign m to one pane and w0 to w15 to any pane and then try to balance both pans by removing weights greedily.

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

        how did you know that you will not use more than the first 16 weights ?

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

          If w >= 4 and there are 17 weights, then the minimum number we can get (positive) is 4^16 — (1+4+...+4^15), more than 10^9. And it is clear that with more weights, the minimum is even more.

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

            then if we have in the first pan (1 + 4 + ... + 4^15) and in the second pan (4^16) the difference is larger than 10^9. however, why we can't put some weights to the first pan say (4^x & 4^y) then put (4^z) in the second pan to get the scale balanced again ?

            how did you prove that such numbers like x, y, z don't exist!

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

        3^16 brute force can be optimized with meet-in-the middle approach to do it in 2*(3^8)

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

        we can solve C in O(log n)

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

        Sorry, But how do you know that you will not use more than 16 weights? Is it depending on maths?

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

          Yeah, w^0+w^1+w^2+...+w^(n-1) < w^n holds for w>=2 :)

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

        Is it possible to find some weights more than w^16 to get the scale balanced ? If not , Can you explain that , please ?

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

Great! contest was very interesting! thanks to author

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

I have mistake in problem C :(

Problem D is classic, but I don't love geometry...

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

    I think D has less geometry than it seems to have.

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

      but how do figure out how many collinear sets we have ? after that it would be normal permutations and combinations.

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

      I didn't think about it a lot, but my solution have calculating coefficients , sortings and after that line sweep. Maybe I wrong ?

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

      D was also a brute force.

      As time limit for D was 4sec.

      It's sad that very few noticed it. :(

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

        10^8 iterations per second, isn't it?

        Then 4*10^8 iterations in 4 seconds.

        I don't get how come D passed for many submissions! It takes 2000*2000*2000 iterations!

        May be CF is too fast.

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

          I was going to hack a O(n3), then thought of running simple addition 2000^3 times in custom invocation and it took .7s. I was like "brace yourself, something terrible is coming :|"
          10^8 iterations theory doesn't apply to CF

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

          roughly 4 *10^8 iterations are there in 1 sec

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

        D can be solved in n^2logn using some concepts of geometry. It would be a nice one if time limit would have been 2 sec. You can see my code here

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

          I tried the same way but was not able to solve in the contest :( I was missing the condition when slope if line was infinity.

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

two WA due to inbuilt gcc pow function:( in 308-B never using it again...

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

    Yea, I realize now that my 308B is wrong ;_;

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

    Same here, Don't understand why gcc pow function fails though ?

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

    same problem ....faced twice on codeforces

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

      pow gives output in double i tried to cast it to long long but there can be precision issues like the pow function giving 2^3 as 7.999999999999 and not 8 which on casting will give lesser answer.

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

    For some reason codeforces, which uses mingw (i think) is giving a bad answer with pow. Ideone gave right answer for the same code of mine. I feel it should not have to approximate since pow(integer) would return an integer in double form, which would not need any truncation.

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

    I know that feel bro.

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

    Try powl someday or use pow with nearbyint ...

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

I like so much problem C

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

Is it OK nowadays to have "write a brute-force, it works in 3.7 while TL is 4" and "use Python to write it in 10 lines, it has built-in eval" as two hardest tasks of contest?

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

    Eval gets Tl, doesn't it?

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

      With naivest implementation it gets; however, with relatively obvious additional observation that it makes no sense to place brackets near '+' sign (you may move it to extend part in prackets till the end of string or '*' sign and it will not decrease result), you have only a small number of possible ways to place brackets.

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

    Yes, I was a bit surprised my solutions passed on those problems. The TL for D and E should have been tighter.

    → Reply
»
9 years ago, # |
← Rev. 8   Vote: I like it 0 Vote: I do not like it

What was wrong with this approach for problem C? http://codeforces.net/contest/552/submission/11653548

I tried decomposing m into powers of w and if some power of W is W-1 times i put a weight of W-1 on that side . :(

Eg- if 20=3^2+3^2+3^0+3^0 Now 3^2 is 2 times and 3^0 is also two times,so adding 3^2 and 3^0 on side of 20 and 3^3 and 3^1 on other side would balance it,i also handled corner cases

EDIT:GOT AC.Used same concept but properly handled corner cases this time :)

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

I tested my D solution for the worst case and it ran fast enough

I wonder can O(n^3) pass ? hope it will

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

Use Math tags for all of the problems :D

Nice contest thanks:)

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

Could someone explain the solution for C ? Thanks :)

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

    wait for the editorial

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

    If m = 2, then solution always exist — it likes writing m in binary base.

    If m >= 3, find the first value of n that w^(n-2)*(w-1) > m. With m = 3, n = 18 and as m goes greater, n goes smaller. So, an O(3^n) brute-forces (considering each scales to be on the same pan with the object, different pan with the object or outside the pan) with properly branch-bound should be fast enough to get AC.

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

      With w = 3 there is always a solution too, right?

      I'm not really sure, but if we use base 3 (instead of binary), instead of using 0 1 2 we can use -1 0 1 and find any integer combining powers of three this way.

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

    The answer is "YES" if it is possible to add another number that only contains 0s and 1s (in base w) to m such that the resulting sum only contains 0s and 1s as well. Just use the algorithm for naive sum, if the sum at the current digit is w — 1 set carry = 1, if the sum at the current digit is 1 set carry = 0, if sum at the current digit is different than 0 return "NO" .

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

    our m needs to satisfy m = a_100*(w^100)+ .... a_0*(w^0),where a_100..a_0 are -1,0,1 we just test if m satisfies this

    http://codeforces.net/contest/552/submission/11642323

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

    Write m in base w. let b[i] be the i'th least significant number in the representation m in base w.

    Loop over m (in base w) from right to left (from least significant to most significant).

    Then if b[i] is 1, we can match it using (w^i). if b[i] is w - 1 then we can add w^i to the balance side of m. Then the representation of m becomes such that b[i] = 0 and b[i + 1] = b[i + 1]+1. so we increase b[i + 1] by 1.

    Notice this could lead to have b[i + 1] equals to w in this case we should repeat the last case on b[i + 1] (i.e increase b[i + 2] by 1 and make b[i + 1] = 0).

    the last case if b[i] > 1 and b[i] != w — 1 and b[i] != w we cannot represent m.

    In contest I did not handle case where b[i] = w. But when i did (after contest) the solution passed all the cases) 11654584

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

    My solution was not brute force. You can convert m to base w. Then iterate from least significant digit to most significant digit. If a digit d[i] =0 or d[i] = 1 then skip it (w^i is either skipped or added to the set). If d[i]==w-1 or d[i]==w, then subtract w from it, and add 1 to the next higher value bit (d[i+1]+=1). d[i] will become either 0 or -1 (w^i is skipped or added to the other set). This works because subtracting w from a digit is equivalent to adding 1 to the next higher digit. If d[i] is anything else, then it is not possible. complexity: O(logw(m))

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

I’m so weak.QAQ

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

I thought C was about DP by assigning -1,0,1 weight to each power of 'w' to get 'm'. But then i realized, (10^9)^100 is impossible to calculate by the methods I know :( .

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

    I had the same idea! Also had no idea how to implement it. Although I believe that there's a O(1) solution. If that's true — can somebody give a hint? Thanks in advance.

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

      Like, exploiting some properties of 'm'... but I couldn't think of any.

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

      I took advantage that you won't ever need a power bigger than 10^9, so you can just compute the biggest power of m which is lower than that number, and do it your way.

      I did it recursive by brute force using that, taking into account that if w^k > m, you don't need w^(k + 1), because the sum of all the powers of w below w^k is less than w^k.

      Hope I made myself clear, sometimes I find it difficult to explain these things :P

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

    We have to find a solution to this equation: m=a0+a1*(w)+a2*(w^2)+...+a100*(w^100), where -1<=ai<=1 and ai is integer If w=2, then it is always possible, because every number have a binary representation. Let's calculate a0 when w>=3: m-a0=a1*(w)+a2*(w^2)+...+a100*(w^100) Note that m-a0 must be a multiple of w, moreover (m-1)%w != m%w != (m+1)%w. So there are just one possibility for a0. After calculating a0, we can divide both terms by w and repeat the process;

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

    You don't know python 11645160

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

Top 5 Filled with unrated users

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

Good set of problems. Thank you author :)

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

I just saw the 4 seconds time limit for problem D, now I think it should be B instead.

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

OMG very very Good problems

I love (short problem & good problem) that this problems are short and good so I love this problems so I love this contest so I'm crazy

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

C and D have the same number of accepted submissions.

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

Nice Contest , also with strong pretest cases.

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

If the N^3 complexity for the Problem D Passed, How It Can Be D??

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

why gnu inbuilt pow function fails?

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

Is a O(n3) solution worth 2000 points? Seriously?

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

For Problem D,

Is the approach of total triangles(nc3)-triangles formed by collinear points(found using overlapping straight lines,ie,equal slopes) wrong? I was getting wa on 4th test case. here is my code http://codeforces.net/contest/552/submission/11654496

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

    ignore it

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

      How come length is accounted into the picture? I am first finding the total no of triangles using nc3. Dont you think nc3 contains those triangles which are formed from collinear points..I think I need only to remove them..please explain

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

    Not just equal slopes, because parallell lines have equal slopes, but you must treat parallell lines separately.

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

Are you serious?

And it occured to nobody that some guys could write such solutions?

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

    Really not justice for people who wrote n^2logn solution -_-

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

      Yeah, and I have an N^2logN solution which gave TL :P

      BTW, I got TL#7 with unordered map/unordered set and TL#13 with map/set :D

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

        Same story

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

        I got AC with an n²logn solution , maybe your algorithm constant is a little high , try to optimize your code.

        Solution

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

          try to optimize your code

          I did it and it passed on the 10th attempt :D Thanks anyway! :)

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

      Yeah :( The time limit should have been 2 sec. It would be worth solving it.

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

    Are you serious ? :P

    → Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

hey guys...in Problem B...Vanya and Books... it shown in test-6 my answer is wrong..for n=1000000 the result is 5888895 and the correct answer is 5888896 but when i run my code in terminal(g++) the output is 5888896.I used GNU C++ to submit. My Code: http://codeforces.net/contest/552/submission/11650994 Why this is happening?

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

    My guess is that it is due to different casting behaviors.

    If you cast pow(10,count-1) to long long int immediately, you will get AC.

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

My C Solution: http://codeforces.net/contest/552/submission/11647965 So basically, if we look at everything mod w, the only weight that matters is one, because everything else is zero. So if there is a way to get this to work, we can change the current weight and divide by w. Recursively, this gives the correct answer.

Surprised at high number of TLE's, I guess..

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

Just want to clarify for problem C,

we have to put weight(s) on both sides, right? If so, I'm curious that for a case that M = 1, W = 3, it's impossible to do so; however, we're still able to balance the pans by putting the weight on only one side, that is, put w^0 on the other pan.

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

B solution 11647913... why not.

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

Hi all.

552E - Vanya and Brackets

Could anyone explain the following judge?

Input 9*8+7*6+5*4+3*2+1 Participant's output 837 Jury's answer 1987 Checker comment wrong answer 1st numbers differ — expected: '1987', found: '837'

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

    9*(8+7*6+5)*4+3*2+1=1987

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

    Actually i didn't solve it...but for your query it because 9+(8+7*6+5)*4+3*2+1=1987 :)

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

      Lol teleport....u literally teleported before i could answer

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

    9*(8+7*6+5)*4+3*2+1=1987

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

Is this logic correct for E: you will place bracket between * and * and if only 1 * then the bracket is either on left or right of it. So precalculating using DP= t= |s|^2.Total time=t + k^2, where k=number of * in expression(<=15).

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

I liked your contest not just because of the good problems but also because of fast rating change.(I got specialist though)

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

accepted solutions of problem D should be rejudged with stricter time limit so that O(n^3) solution timeout. Then only standings will become fairer.

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

pow()... :-|

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

I have a question guys. My code for problem B: 11655174 seems to return 99 when calling pow(10ll,2).
I notice this does the same on my mingw, but returns 100 correctly on g++ and ideone. Is there any reason for this?

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

Check ur new rating. Really fast rating.

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

Image and video hosting by TinyPic

Nice!!!

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

Yay, finally in Div 1.

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

For ProblemB 'Vanya and Books' my answer is not 'Accepted' with the message saying "wrong answer on test 18'. But when I re-run the same code it gives me correct output. Don't know how the program gave an invalid output out of the blue. My Submission

Am sort of new to Codeforces, my apologies if this is not the correct place to put forth such queries.

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

    Your code is awesome, but you forgot one thing. You have taken all necessary variables in long long int but n!

    Your code works fine up to 8-digit. Even works for some 9-digit numbers too. But fails for large 9-digit numbers. Why? because, you need to do multiplication in long long.

    For 9-digit and 10-digit number, re-think about the lines: res += (n-99999999) * 9; and res += (n-999999999) * 10; respectively.

    Say, n = 999999999. Then what would be the calculation of (n-99999999) * 9 portion?

    = (999999999-99999999) * 9

    = (900000000) * 9

    = 8100000000 which is a 10-digit number and could not fit in long int.

    So, change the line long int n = 0; into long long int n = 0; and get Accepted!

    Another thing I have noticed in your code that you have used the same variable n as local and global at the same time. It is a bad practice for programming contest. Sometimes, it could massacre your contest!

    Thanks and sorry for my bad English as well as bad explanation. Happy Coding!

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

In case anyone is interested there is a way to solve problem C trivially without a computer if you are given the base w expression of n. My solution uses this approach, it runs really fast, you don't need to calculate anything, you just need to read the base w expression.

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

In problem B,my solution is working fine for a particular output on my system but its giving a different output when i submit the same solution.This was my submission 11656471 Is it because i am using long long int and lld specifier? In which cases does the online compiler might behave differently than my local system?Thanks

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

    It is for your (long long int)pow(10,(double)x). Be careful to use pow function. It is very dangerous! It calculates in double, so precision error occurs. Just handle it manually. Thanks in advance.

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

my solution of second at 5th test case is giving ryt answer in all other compilere like ideone etc....herein code force compiler it is giving wrong answer.....how is it even possible

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

Why liyankui was skipped?

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

    妈的手速快就要被skipped? 管理员可不可以出来解释下？？

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

      谁让你32秒切一题。。rank2都看不下去了

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

为什么liyankui会skipped? 有老司机出来解释下嘛？

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

题目太简单都是liyankui的锅！

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

5道程序代码风格完全一样，程序没有雷同。凭什么skipped？ 哦你可能说有5个人同时在做，妈的做这种sb题liyankui需要开挂？

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

随随便便就封号？ 封你mb! why are you so diao?

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

我喷你了这么多，是不是也该把我封了啊？ 哦对你是毛子看不懂中文哦！ 我推荐用有道翻译！

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

    Mind your language. If you really want to complain, go open a new thread and use English. Stop embarrassing yourself here.

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

    go and learn English!

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

Awesome contest !!! C and D were good but O(n^3) wasn't fair !!
finally div1 !!!
P.S:- Very Happy

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

I'm so sorry for my behavior just now ..

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

    No problem, I didn't understand anything either way.

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

Hello, Div.1!!! Looking forward to the next round!

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

Whats the mathematical principle for problem C? I have seen some solutions they are operating on m (decrementing and incrementing according to divisibility by w which so conveniently uses powers of w only once) but cant seem to figure out how they came up with the solution e.g.11657140

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

    I don't know how that solution specifically works. But I notices that the base w representation of n can only have the following digits:

    0 (this can appear without any restriction)

    1 (this can appear only if the digit to the right is 0 or 1)

    w-1 (this can appear without restriction)

    w-2 (this can appear only if the digit to the right is (w-1 or w-2)

    Just read the base w representation and check if all the digits are as mentioned above.

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

Still waiting for tutorial....

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

Where is tutorial?!

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

question about problem D: can anybody explain why my O(n^3/6) solution was not accepted? here is the code 11645613

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

    You need to optimize your code for a brute force approach.

    You can get rid of the if statement in the inner loop by starting j = i+1 and k = j+1. Also move the x1, y1 computation one level higher so that it will not be recomputed for every k.

    It passes then 11670552

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

Editorial, please -

→ Reply
»
9 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Can someone help me with my question B submission, its running fine on online compilers ? Here is the link: http://codeforces.net/contest/552/submission/11640318 Edit : Got it after reading the editorial !

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

Can somebody please elaborate the Problem C editorial? Whats the concept behind the solution. Why the number m needs to be converted to base w.

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

    OK I'll try . — we need to find if solution to equation M=w^0*a0 +w^1* a1 + w^2*a2.... Exist or not . This equation is equal to M-w^0*a0 =w^1 *a1 + w^2*a2.... Rhs has a common factor of w so lhs should be divisible by w . a0 can have 3 values -1 ,0,1 We try all cases of a0 and check if Lhs formed is divisible or not. Since w^0 is 1 we have m-1 , m+1, m. If any of the three is divisible my w. That would be new value of m. And equation now becomes m'= w^0 * a1 + w^1 *a2.... Which is solved similarly untill we reach a point such that m,m+1,m-1 is not divisible by w by m( answer doesn't exist) becomes 1 (possible)

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

    where are the editorials of the problems ?

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

wow, all top 5 winners had their first contest, kinda neat :)

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

uw_ttocs

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

Can you give me an editorial, Wild_Hamster?

→ Reply