laoriu's blog

By laoriu, 10 years ago, In English

Hello everyone!

Today, there will be another CodeForces Round at 18:00 (Moscow time). It is a Div. 2 contest, but Div. 1 participants can take part out of competition also.

My name is Vuong and this is my very first CodeForces round. Hope that this is not the last one. I would like to thanks Maxim Akhmedov(Zlobober) for help me preparing the round, Maria Belova(Delinur) for translating problems into English, and Mike Mirzayanov(MikeMirzayanov) for such a great Polygon and CodeForces.

Be sure to read all problem statements before contest ended. Hope you enjoy the contest.

Good luck and have fun!

UPD The contest is over! Thanks all of you for participating!

Here is top 5 participants:

  1. khykhm110
  2. My_First_Lady
  3. Perditio
  4. AkatsukiPain
  5. s_z_l

The editorial can be found here.

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

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

Would Score distribution be dynamic?

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

    Hopefully not, last contest was dynamic and it was not rated (even if those two are not related)...

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

    yes , all the problems will be about dynamic programming . ok

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

Thanks for the problemset. Good luck to all! :)

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

I can go to bed before the system test over!!!! Because my university will cut off the electricity at 11:30, and my computer can last for only 3 hours without outer-power! What nice news!

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

    mathlover is a super star in my heart,can I admire you?

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

    In our university, The building #15 has electricity supply all the night so I can wait for the system test.

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

    How hard to study in China :D Economy))

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

      This is just some of the rules of the school,because the contest time is at midnight in china,but there are still many hard-working students like mathlover got a red name.

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

      it is because of some fool schoolmasters and teachers but not economy...

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

      Китайцы, успокойтесь!

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

If I'm not wrong, this is the first round set by a Vietnamese! Good job! :)

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

I have been wndering....how many languages does Delinur know?? :D

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

    Usually, problem statements will be written in English, if the author wants it to be put in an international site.

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

    I know don't the exact answer. But one day during a conversation, she said this "But I can translate your message into 4 other languages if you want :P". It means that she knows may be 5 or 6 languages or more.

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

22:00 is good time for me to participate. Thank you for your contest.

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

    You didn't even register for the contest

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

      I went to register page at least 3 times but failed to register because of some network problems. After coding problem B, I realized that I didn't register for this contest.

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

I hope codeforces won't be down today :S

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

Countdown time and Announced time are Different. I am confused.

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

    Both of them are correct. Which announced time have you seen?

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

I wonder will the time be at 18:00(MSK) in the future or 19:30(MSK) for mostly?

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

    I hope most rounds are on 18:00 MSK in the future. That 1-hour switch has really some impact on us(Chinese).

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

      ...but 17:30 CET is too early for me, and you can guess what is my opinion about 16:00 CET...

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

      I hope for 19-30(MSK)

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

I think :
codeforces Round 277(Div. 2)== Happy Birthday contest !!(for MikeMirzayanov's daughter)!!:)

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

    bhut fikar hai tumhe mike mirzayanov ki beti ki .-- written in HINDI now translate it Delinur

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

      please write in English!!
      I can't read this comment.

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

        He said "Why are you so concerned about Mike Mirzayanov's daughter ?"

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

i wish we won't have hack or other problems in this round

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

I bet that there will be one more blog post by DmitriyH after this round.

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

Punish him/her please! (S)he wants solution

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

How to solve C ????

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

    You always need to fix only a half of a string you are staying at.

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

      I did exactly that. Got WA on pretest 2. I am sure its a silly mistake on my part. :(

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

      But How to do it by minimum operation ?

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

        Assume we are in the first half of a string. You are to find the segment which you must fix (leftmost and rightmost positions in the first half). Now you can choose the best way to visit all the segment, there are only two of them:

        right - pos + right - left and pos - left + right - left

        Of course, you also have to do min(abs(s[i] - s[n - i - 1]), 26 - abs(s[i] - s[n - i - 1])) operations for every i=1..n/2

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

          What if both left and right are on the same side of pos?

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

            You can take the absolute values, giving

            min(abs(right-pos)+right-left,abs(pos-left)+right-left)

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

              Well, my implementation ( 8656932 ) was a bit different. So I had to give that extra check, where both left and right were on the same side of pos. Lelby also gave that check ( 8659477 ), but he commented differently. That's where I got confused.

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

        You have to move from first char which needs to be fixed to the last one (or opposite way if shorter).

        For example if number or fixes for characters in string aaaaacdefg is 0, 3, 4, 5, 6. Then if you are on position 2, you move to position 5, if in position 3, move to 2 and then to 5 and if on 3, then move to 5 first and then to 2...

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

        We need to operate only with one half of string. Consider we choose left one. If p > n/2 just reflect it. Them found two indicies — 'l' first letter which need to change and 'r' — last letter which need to change. Minimum action for movement will be min(r-p,p-l) * 2 + max(r-p,p-l) if p inside [l;r]. If p is outside first we need to go in this range. Now we know how much ticks we will spent only on movement, during this movement we'll be on each letter. So just calculate cost of each change in range [l;r]. Result will be movement cost + change cost.

        O(n)

        I hope my approach is right :)

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

How to solve D ?

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

    Define root of a set as the node with minimum (av, v).

    Now we can consider all the sets with that root (each of them will be counted once).

    It can be done via simple dymanic programming.

    http://codeforces.net/contest/486/submission/8659287

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

    Take a fixed minumum number low then maximum value is low + d.

    Find number of sub trees which has at least one node with minimum value and does not has any node that bigger then low + d or less then low. It can be done with dynamic programming in O(N).

    Overall complexty is O(ND)

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

    Thank you both very much! I've got it.

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

Why some people didn't get overflow in first problem when they calculated sum of first n div 2 even numbers and calculated sum of first (n+1) div 2 odd numbers?

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

    I don't know. I made an unsuccessful hack because of this!

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

    It overflows, but both overflow the same, so when they subtract the overflow is gone. If you can find a case such that one overflows but the other doesn't (very unlikely and might not exist because 1018»1015), I think their solution will fail. I spent the last 15 minutes on W|A (Wolfram Alpha) trying to do just that, but haven't succeeded. A program would probably do it faster though.

    EDIT: Actually I think now that even if one overflows and the other doesn't, subtracting them will again mean the overflow didn't matter. 281474976645119 makes one overflow and the other not, but it still works as the overflow is ignored.

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

      Yeah I noticed this after my first unsuccessful hack :D

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

    let's hope for system testing!

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

    Apparently some solutions failed for the input "3037000499"

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

      This doesn't seem to break one solution I'm looking at. Can you show me a submission that fails it?

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

        This one fails (i failed to find this test in time). 8652729

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

          Ok thanks. It's different because they find the sum of all numbers and subtract twice the sum of the odds, and since they divide by 2 after overflowing, subtracting no longer always removes the effect of the overflow.

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

How to solve problem D(problem D is very hard!!)?

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

    My sol is to DFS each note as that node is the max node, then use DP.

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

    Every valid set can be uniquely determined by the smallest node in it.(If there are more than 1 node has the smallest value, we choose the one who has the smallest id). So let's choose an node to be our special node, and starts to dfs under the limit that our special node has the smallest val and smallest id and the gap is no more than d. We get a sub-tree of the original one. And considered sub-tree, You can use dp to count how many way you can choose a set which contains the root (our special node)from the sub-tree.

    It's a classical dp problem on trees. dp[node] means the ways to choose a set which contains the root and the others node come from the sub-tree of it. And you want to calculate dp[x] for the the node x, you just go through his son, and we can either not choose the part from this son's sub-tree or just take it, which has dp[son] ways. So in total (1 + dp[son]) ways. Multiply the sons choices up. And we get the ways to choose a set from the sub-tree of x which contains the node x.As we can let every node in the tree to be our root(special node), we can get the answer for the question.

    Check my code hope that helps.

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

A was easy, B was interesting, C was time-eater and interesting too.

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

+100 to persistency

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

 img

Ban Samsung please.

Translation: he asked me to send him solutions of A, B and C

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

    wow the request is so interesting

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

    this site has no report system?

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

    Did you sended him smth? No? There is no reason for ban then. Yes? Then both should be banned.

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

      I don't think temak would've asked to ban him if he has sent something o_o

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

        It's very same situation as — "You got SMS message: 'Mom! Please, send me 300$ to X-XXX-XXX-XX-XX I'm in big trouble!!!'. You can ignore it, and then there is no criminal. But it's possible to find the owner of this number, send the money and then arrest him, because his attempt was succesful". So there is no chance that Samsung will be banned, because solution wasn't sent! But still, temak posted this image and waiting for something.

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

    that's why Iphone better than samsung:D

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

how to print negative number (A problem) from squee_sp00n's A

if(n&1){
			cout<<"-"<<n/2+1<<endl;
		}else{
			cout<<n/2<<endl;
		}
»
10 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

It seems that nobody solved E using large prime modulos like me.

What was the intended solution?

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

    I solved it in that way :)

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

    I think it is to count the number of indexes belong LIS of length i :) If there is only one index of length i then it must be type 3, otherwise type 2.

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

    Could you explain what do you mean by "large prime modulos" ?

    I solved it simply using segment tree for some calculations.

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

    Quite surprised there's an antihash testcase for 2^64 modulos :|

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

      While constructing testcase for string hashing is not so easy — hacking similar solution for this problem is very easy (and it is well-known olympiad problem). Just take a look at sequence 2 1 4 3 6 5 8 7 10 9... How many LIS it have? :)

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

        Yes, i realize it's not hard to make such testcase, my bad for assuming anything modulo something is hard to hack :)

»
10 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Will the contest also be unrated as the past contest???

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

    No :)

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

    Don't think so. Last one was unrated because of problems with servers etc. Rankings are just always updated few hours after the contest.

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

Sigh

Top4 are once again unrated, two of them registered in the past 24 hours. I'm not saying they are cheaters, but that happens way too often lately :\

Awesome problems by the way, solved all 5! Thanks, author :)

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

why getting wa in test case 16 in 486A - Calculating Function .. my soln 8655625 it gives correct output in my compiler

»
10 years ago, # |
  Vote: I like it -34 Vote: I do not like it

I HAVE A COMPLAIN IN CONTEST IT SHOWS PRETEST NOT SHOW WRONG OFTER CONTEST ITS SHOWS WRONG ANSWER WHY YOU WOULD NOT SHOW AT THAT TIME?

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

    Welcome to CodeForces :D

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

    PRETESTS =/= TESTS, obviously.

    This is the format of the competition. Your solution is tested on some part tests that usually do not cover all corner cases and maximal constraints. After the competition your solution is graded on the official tests.

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

    pretests are a very small fraction of the entire test

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

    I don't know the exact reasons, but if I need to guess, there are probably three reasons for that:

    1) Because of pretest/test separation, there's less need of computation while we're in contest; that's why we can get faster feedbacks.

    2) It's much more exciting and fun to wait for system testing to see your actual results.

    3) Hacking mechanism is based on this feature; this is also related to second reason since hacking is fun.

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

      what a joking u its not fun always you show wrong answer at contest but today you cheat me it;s not fare.I wana my full points its your mistake not mine otherwise i'll never participate in your contest

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

    This is not your first contest, right? There are few tests when you submit, but all tests are tested during system tests...

»
10 years ago, # |
  Vote: I like it -24 Vote: I do not like it

this contest is unrated ?

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

that My_First_Lady seems to have used different templates on C and E. and submitted C after E in two minutes.

just saying.

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

    Yes, that's very suspicious indeed. Sadly I've never seen anyone banned for such reasons which is why we have tons of unrated accounts and/or teams ruining top5 of Div2.

»
10 years ago, # |
  Vote: I like it -53 Vote: I do not like it

see this two code for 1'st question whats differnt.

include<stdio.h>

include<math.h>

int main() { unsigned long long int n,i,j,k; scanf("%lld",&n); if(n%2==0) { i=n/2; k= i*(i+1); j=-(i*i); printf("%lld",(k+j));

} else { i=n/2; k= i*(i+1); j=pow((i+1),2); printf("%lld",k-j);

}

} 2.

include<stdio.h>

include<math.h>

int main() { unsigned long long int n,i,j,k; scanf("%lld",&n); if(n%2==0) { i=n/2; k= i*(i+1); j=-(i*i); printf("%lld",(k+j));

} else { i=n/2; k= i*(i+1); j=(i+1)*(i+1); printf("%lld",k-j);

}

} but first shows wrong answer and second shows correct answer what the difference between them

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

    ...

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

    In case the guy really doesn't understand smth and not trolling: The first programs uses pow function (http://www.cplusplus.com/reference/cmath/pow/) The declaration of this function: double pow (double base, double exponent); — that means result for even integer numbers could be 255.99999999999 instead of 256 since for float(double) numbers those values are pretty same. But here j=pow((i+1),2) you're doing cast to integer. So result could be 255 instead of 256 and no one can guarantee which one exactly.

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

Most of the solution failed test case 31 and 39 for problem B. They didn't know when to say NO :P

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

    We're lucky that we don't need to output "START" / "STOP". Most of us don't know when to say "STOP" :D

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

Heh, had solution for C, but just assuming that there's only one turn, not that the cursor always remains in the first half. Much more complicated to write that way : S

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

codeforces should try to improve their website performance during contest..

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

8652439 Why can this solution for problem A can pass all the data? It is an O(n) solution!

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

    The loop

    for (int i=1; i<=n; i=i+2)
     s=s+i-i+1;
    

    is so simple, that compiler (with optimizations on) turns it into

    s = s + n / 2
    

    because loop is really just incrementing s by 1 on each iteration, and we know precisely the number of iterations. Thus it becomes O(1) solution.

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

      oh...One of my friend attempted to hack this solution with a big number... two unsuccessful hacks... Sadness

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

Why my solution to A 8652258 passed all tests? It almost wrong. Can someone answer me

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

Country wise rankings table has been updated

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

Mind if I ask why 4 out of 5 top are unrated?? I wonder if multi account is OK!

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

Why the next round will be called "Codeforces Round #277.5 (Div. 2)", not "Codeforces Round #278"?

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

    Because next contest that will be after 7 day called "Codeforces Round #278", "Codeforces Round #277.5 (Div. 2)" was created after this contest, and will start earlier