By zeliboba, 8 years ago, translation, In English

Hi, Codeforces!

AIM Tech Codeforces Round 3 will take place on August 24, at 19:35 MSK.

The round is prepared by AIM Tech employees: Kostroma, riadwaw, yarrr, ValenKof, Edvard, bobrdobr, malcolm, NVAL, nmakeenkov, agul, Extr and zeliboba. Round will take place during Petrozavodsk Summer Camp, which is sponsored by our company.

We made our problems a little easier than at AIM Tech Round 1 and AIM Tech Round 2 but we promise they won’t be less interesting. Scoring system will be static.

Thanks to Mike Mirzayanov(MikeMirzayanov) for brilliant platforms Polygon and Codeforces and problem coordinator Gleb Evstropov (GlebsHP). Many thanks to AlexFetisov and winger for round testing!

Our company specialises in proprietary trading, the key concepts in our work are big data, low latency and high frequency. Our team mainly consists of graduates from the MSU Faculty of Mechanics and Mathematics and Moscow Institute of Physics and Technology (MIPT).

We wish you good luck and high frequency rating!

Scoring in both divisions 500-1000-1500-2000-2500

Editorial

Announcement of AIM Tech Round 3 (Div. 1)
  • Vote: I like it
  • +514
  • Vote: I do not like it

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

Now we know what is Edvard new job :)

It would be nice to make combinative d1/d2 round.

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

    I guess one can actually prepare the same problems for both divisions, just with different variable/time/memory constraints for Div1 and Div2 participants. But this sounds more woe than fun :)

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

Will there be T-Shirts as stated here? http://codeforces.com/blog/entry/23240?#comment-276543 :D

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

these aimtech guys really do have a very interesting field of working, artificial intelligence management, i never heard of it before.

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

Standard duration (2 hours)?

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

AIM Tech Round 1: -40, AIM Tech Round 2: -43. I hope my rating change will be positive this time :"D

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

    What is negative rating change?

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

      It's sort of like a lot of downvotes.

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

      That's good you've never experienced it!

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

We made our problems a little easier

You said that last time, too — and it turned out to be just from "3rd place = 3 problems solved" to "6th place = 3 problems solved" :D

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

I know the AIM Tech Round is harder than the ordinary div2,but I will try my best to solve the first problem or the second problem.

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

    Not this time ! Although Question B had tricky cases to deal. Overall, Questions were easy as compared to regular DIV2s. Happy coding.

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

    You didn't give the contest!

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

      I used my another account to take part in this competition.

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

Hope another exciting contest, interesting problem set :)

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

what does frequency mean?

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

    "dum.....dum.....dum.....dum.....dum.....dum.....dum" is low frequency, whereas
    "dumdumdumdumdumdumdum" is high frequency =)

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

i wish high rating for all :D

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

    that who gets the low rating?

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

      I think in the setting rating system if a person go up by x another person should go down by x too! and because of new users the sum of all rating is going up!

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

        It means when you become happy cause of your rating change, there is some one sad of your happiness?!

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

          which is sad :/

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

          truth always hurts. Just a truth-seeker can believe it.;)

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

        Is it called Law of Conservation of Rating?

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

    Thanks , also to you

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

    *wish

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

Thanks for codeforces to provide the chance for me to practice with you that from all over the world whitout money,thank you very much, i mean it :)

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

The comment is hidden because of too negative feedback, don't click here to view it

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

maybe it is new start.

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

Wish that everyone can get a satisfactory rating.

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

    If the rating change formula is correct you are telling an impossible event :( Anyway, wish the most of the user a satisfactory rating.

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

Good luck boys !

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

What does "Scoring system will be static." mean? Usually it is dynamic if I'm correct.

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

    That means basic score for each problem is fixed before the contest (and it decreases during the contest linearly). Dynamic scoring means that basic score for each problem depends on number of accepted solutions.

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

    Actually, I think static scoring simply means that it is not 'dynamic scoring' which is detailed in,

    http://codeforces.com/blog/entry/4172

    Basically, instead of scores decreasing from a fixed amount, the 'initial scores' themselves would depend on the number of contestants who have managed to solve the problem.

    We don't see a lot of dynamic scoring competitions these days but they used to be relatively common about two years ago.

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

So fast Scoring System Update . #GLHF

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

I am a newbie since last febrauary. I hope to be a pupil in this round. I hate my gray color xD

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

    Yes, I know that feeling bro, just as much as I'm hating my cyan colour, good luck today :D

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

I study in the Faculty of Mechanics, perhaps my study will help me solve one of the problems today :P

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

I will be back

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

tourist is registered!

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

9 legendary grandmasters participating :O

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

Div1B was super evil..

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

Good problems, but... After that contest, I hate the number 7 :(

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

    I see you passed it,i had same problem,do you have any clue what the test could be ?

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

0 0 0 0 for Div2 D/Div1 B :(

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

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

Made B 5 sec. after end of round

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

Since "Round will take place during Petrozavodsk Summer Camp", I guess system test will start late?

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

what was the hack test for div2C

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

I wish aaa was not a pretest in Div 1A.

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

    It wasn't

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

      but it was definitely string consists of all a.

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

        Yep, there was a but some people still failed longer aaas

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

          What is the reason for failing longer aaas

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

            They may have added in a special case in their code if the input is "a" but forgot to check if there is more than one 'a'.

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

The difficulty was perfect and problems were interesting. A very nice round (I didn't read div1-d though). I hope there will be AIM Tech Round 4, one day.

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

    translation: give me upvote!

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

      No, translation: I solved E, oh yeah!

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

      Xellos was closer, sorry.

      Also, I think that many setters prepare problems mostly to make us think "wow, I enjoyed that a lot". If someone made their job so well, I'm sure he/she deserves some applause.

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

        I didn't solve D and E and I'm not even mad because the problems were so nice.

        Different from when you see those innovative query on tree heavy-light decomposition problems and you're like "I don't even care if my rating goes down for not solving this, it's so boring"

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

          Oh, sorry I can't give you more than one upvote. Exactly same feeling about these problems =)

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

    Most likely it will be during the next Petrozavodsk Camp

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

    Tasks were nice! (Translation 2 bits away from AC in E). Either way, tasks were really nice :P.

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

I think that the description of Div2A was a bit misleading. "... When it happens Kolya empties the waste section (even if there are no more oranges) and continues to squeeze the juice"

To me that implies that Kolya stops squeezing the current orange, empties the waste section and continues to squeeze the same orange until there's no more juice. But magically, Kolya actually squeezes the entire orange and then cleans everything, resetting the waste bucket.

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

    even I thought of that, my whole contest got wasted because of this ......

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

Very slow codeforces, but tasks were pretty interesting :)

I suppose it will be a lot of fail submissions after end of testing.

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

    That is the first and only feeling I had after the end of today's contest.. Lets hope for the best

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

Div 2 C was easier than Div2 B.

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

I submit 2 codes for problem A,my both code is accepted but on rank list time of second code is considered and also 40 points of penalty is also deducted .why it is so?

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

    It takes the lastest submission in case you found bug(ssss), some godlike cases that may not be verified in pretests.

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

    You get -50 points for every resubmission, and only the last submission is taken into account for testing.

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

    your latest submission is considered.

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

When will the system test start please? So I can decide whether i will sleep before school tomorrow Xp(only 3 hours before I must wake up again) Haha

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

    school in august ? no wonder asians are smart haha :D

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

Can someone give me a hit for Div 2.D??

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

    div2d had so many edge cases... The main can be solved purely using math. As for edge cases, there are (0,0,0,0) (0,1,0,0) (0,0,1,0) (X,0,0,0) (0,0,0,X) where X is a triangular number. You can deduce number of 0's and 1's in since a and d must be triangular, and a+b+c+d must be (n0+n1) choose 2, otherwise "Impossible". The last edge case is when a=0 or d=0, since there can be 1 or 0 of them. But if theres 0 then it reduce to X 0 0 0 and 0 0 0 X case Now you can say that when a=0 then n0=1 and d=0 means n1=1. Now prove that anything else left is always possible to build. :)

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

    although I have stuck with the 3rd case, I can say my idea.

    first, you can get number of ones and number of zeros in the string.

    where:

    1) No. of zeros * (No. of zeros — 1) / 2 = a00

    2) No. of ones * (No. of ones — 1) / 2 = a11

    You can check some validations using these numbers, a01 ans a11.

    No to build your string.

    ans = ""
    cnt = 0 // number of "01"s 
    while(No. of zeros and No. of ones) do 
      if(No. of zeros + cnt <= a01) 
        ans += "0",  cnt += No. of ones, No. of zeros -= 1;
      else ans  += "1", No. of ones -= 1;
    end
    

    then you should validate your string and you can do this in O(Length of strnig) by counting how many "01" and "10" subsequences and then check them with a01 and a10.

    I implemented this idea but I couldn't to figure this tricky case "0 0 0 0"

    sorry for bad English. :)

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

      can anyone explain the example instead of the solution? :(, I even don't understand the example (and the problem also)

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

        I will reverse the problem statement:

        You are given a string S consists of 0's and 1's.

        How many times these subsequences { "00", "01", "10", "11" } do occur?

        The problem itself gave you how many time each subsequence had occurred and you should get the string.

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

      that was my idea but oh god I was so stupid I was confused between substring and subsequence for like 30mins and I was like "wtf they are wrong on example 2" :/

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

        What is the difference between substring and subsequence? could you give me an example?

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

          for instance in abcdef :

          "bcd" is a substring and a subsequence because letters are neighbors in the string and are in the same order

          "bdf" is a subsequence which is letters in the main string in the same order but not necessarily next to each other. But it is not a substring

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

            so here there exist a subsequence "01" if there is a 0 with a 1 later in the string.

            in 11111100000 there is no "01" sequence but in 111100001 there are 4 "01" sequences

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

    Let the number of 1's in the string be X.
    Let the number of 0's in the string be Y.
    Then,
    1. the number of 11 subsequences = X choose 2
    2. the number of 00 subsequences = Y choose 2
    3. the number of 10 subsequences + 01 subsequences = X * Y (one of them is from 1's set other from 0's set)

    Assert the above conditions for solution to exist.
    Now let the requuired string be B, and let us start from a string A and try to construct B from it, where A =
    "11111.. (X times) 0000 (Y times) " — i.e., all 1's followed by 0's.
    A has X * Y number of '10' subsequence and 0 number of '01' subsequences. Now, notice if we shift the last 1 (the Xth 1) one position right swapping it with the first 0
    => 1111..( X-1 times ) 01000.. (Y-1 times)
    Now, A has X * Y — 1 number of '10' subsequences and 1 number of '01' subsequences.
    Keep doing this sort of shifting, you'll eventually be able to arrive at a01 number of subsequences and a10 iff (a01 + a10 == X * Y).

    Beware of corner cases like: "0 0 0 0"
    "K 0 0 0"
    "0 0 0 K" ...

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

Will there be anti-quick sort case on Div2-B for Java solutions?

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

Interesting systemtest. Waiting half an hour, then almost instantly 58%, then it stops again :D

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

    Because partly the testing is conducted during the contest

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

      I know, I was a problemsetter :D

      That doesn't explain the discontinuity, though.

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

        "Because partly the testing is conducted during the contest"

        "I know, I was a problemsetter :D"

        Just red coder things :D

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

    Because the judge alternates between Div 1 and Div 2.

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

Div 1 B is all red...

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

My solution got TLE on problem C. Are you serious???

Edit: Sorry, maybe I need to sleep more. >_<

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

    Isn't it ?

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

      Broom test OP

      So even Nutella grandmasters make this mistake sometimes :)

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

    this problem is too difficult.

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

    My O(n) got 1543ms, after my O(nlogn) got TLE on pretests. It's easy to underestimate constant factors.

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

Could've been a great contest for me, but no..........

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

    I feel the same way lol.

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

    Same here. :(

    I solved 4 problems but got WA on 2 of them due to stupid corner cases. Pretests were weak. >_<

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

One of the most interesting, well developed CF round ever. Thank you so much! :)

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

I can't believe I got WA on test 163 out of 164. -.-

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

...

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

How to solve div1-B?

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

    First, you should notice that a00 and a11 are triangular numbers(and it will give you the values of the number of 0's ans 1's, here you should be careful with a00 = 0, because there could be 0 or 1 zeros, the same for a11). Second, a10 + a01 must be equal to xy, and in fact (you can prove by induction on (x + y) that it's everything you need to construct an string with the conditions you want).

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

    So first of all you have to find how many zeros and ones there will be in total. in order to do that you look at the number of 00 and 11. Say number of 00 is 3 that means that we have 3 zeros in our string because you can choose 3 combinations of size 2 from 3 zeros. So basically if you have n zeros in your string the number of 00 will be n*(n-1)/2 and the same goes with 1's. Though there is something we have to look at, which is when you have 0 of 00's. then maybe there is 1 0 but definitely not 2 because if it was to number of 00 would be 1. So it will be 1 if number of 01 or 10 is more than 0. and same goes for 11's. after you determine the number of 0's and 1's you do the following: you start putting 0's and 1's. if you put a 0 you decrease total 0's. if you put a 1 you decrease total 1's. and if you put a 0 that means you increased number of 01 by the amount of remaining 1's because you will place remaining 1's after that 0 and it will be number of reamining 1's times so same goes for 1's . an algorithm would look like this for that :

    	while(zeros >0 || ones >0){
    		if(b>=ones){
    			printf("0");
    			b-=ones;
    			zeros--;
    		}else if(c>=zeros){
    			printf("1");
    			c-=zeros;
    			ones--;
    		}
    	}
    

    and there are still some cases. if a,b,c,d=0 then you print 0 or 1. if a b c= 0 but d is not you print only 1's. and vise versa. and if a or d is not in the form of n*(n-1)/2 it is impossible as well.

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

      How did you figure out that the approach of just writing out 0s and 1s greedily "while the current string doesn't violate the rule" would work? My first reaction was that I had to consider many different combinations, and, frankly, I still don't quite understand why this works.

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

        well it is not that hard to figure it out. lets say we have 5 0's and 5 1's. if you put 0 at the beginning how many 01's are you adding for that 0 ? 5 times right ? because it would look like this: 0xxxxxxxxx where x is 1 or 0 but in total there will be 5 1's in x's so for that 0 they will make 5 01's. and now you have 4 0's. lets say you will put 1 now. 01xxxxxxxx . and now we have 4 o's left. how many 10's can you make with that 1 ? 4 times right ? because you cant use the 0 at the beginning to make 10. and it goes like this, think simple dont make it complicated :)

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

Why can't I see test cases in practice mode? I want to know where my solutions fail.

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

    Pretty sure you can, at least the start of them... (just go to the submission page 20134499 and scroll down)

    Your solution for B fails for "0 1000000000 0 0". The testcase for C is too big for me to see.

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

      Yes, thanks for your reply.

      A few moments after posting my comments, I was able to see testcases, but before I could see nothing, as if the contest was still going on.

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

Was stuck on problem B with test case n = 1 till the final 1 minute...lucky to discover that before end.

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

Hard time today lol!!!

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

    Your profile picture seems appropriate for you :)

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

    Look on the good side, you did not got a WA on main tests.

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

the statement of problem A was terrible :( so bad

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

    yes, it took me 20min to figure that out

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

      it took me 30 min to understand it and 3 min to code it :(

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

        It took me 1 min to load the page, 1 min to read the problem and another last one to code and submit it :P

        Meant no offense, just joking though, but why you found it terrible, I thought it was clear enough.

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

Can you please tell me why I got TLE in problem C !! that's so weird!! 20125382

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

    use printf instead of cout. and in order to make it a little bit faster you can do this int size = s.size(); instead of looking at the size every time in the for loop.

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

      printf should make nearly zero difference, cout is only used once

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

        you are completely right lol I thought it was in for loop

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

    String comparison is O(n), and you do it n times.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    if (s < prev) {
    	prev = s;
    	ok = true;
    }
    

    s < prev inside loop, comparing strings is O(len)

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

    String comparison

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

    s.length() is calculated after every condition check...which makes your code square complexity....I made this mistake once

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

    String comparison is costly time-wise, this line to be specific: s < prev. It should be replaced with s[i] < prev[i] as you don't need to compare the whole string everytime as you pass on each letter and can compare them individually.

    Here is your code modified, it got accepted. 20135520

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

      thanks a lot dude, it's so tricky I think.

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

        It is, best way to avoid these sneaky little mistakes in the future is by making them in the first place!

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

    No it's not. In the killer testcase your code is comparing a very long string for each character it has, leading to a O(n2) behaviour.

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

How to solve Div2B ?

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

    just sort the data....now you need to visit n-1 points. So you have to check for 2 choices — either leave first point or the last point(in the sorted data set) which has 4 ways of doing so. Check my code — 20124041

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

      Can you elaborate more please ? I am not that good programmer you can see :(

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

        Sort the Points. Assume D as the given Point where you are standing presently ...Now,

        • calculate the distance between D -> Arr[1] -> Arr[N-1] ( Indexed by 1 )
        • calculate the distance between D -> Arr[N-1] -> Arr[1] ( Indexed by 1 )
        • calculate the distance between D -> Arr[2] -> Arr[N] ( Indexed by 1 )
        • calculate the distance between D -> Arr[N] -> Arr[2] ( Indexed by 1 )

        Now calculate the minimum of those result .

        Make sure you are checking all other Corner Cases like ... if the point D is in between Arr[N-1] & Arr[N] . ( there are 3 more Corner case according to my approach . I am sure your are smart enough to find those out )

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

        We have a position x. and an array a. sort array.

        the first case x <= A [0] then the answer (a[n-2] — x)

        second case x> = A [n-1] if the answer (x — a[1])

        in other cases the answer: a minimum of

        ( (2*(x-a[0]) + (a[n-2]-x)),

        (2*(x-a[1]) + (a[n-1]-x)),

        ((x-a[0]) + 2*(a[n-1]-x)),

        ((x-a[0]) + 2*(a[n-1]-x)).

        Multiply by 2 because they have to pass through this segment 2x. early in one direction and then in another. Choose from 4 variants the most profitable

        We do not forget about the option when n = 1; the answer is 0

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

Div. 2 Problem C has a complexity of O(n) but still I am getting Time Limit Exceed on test 27. My solution link is : http://codeforces.com/contest/709/submission/20121635

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

    it is O(n^2) because string concatenation is O(n)

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

    Maybe you shouldn't calculate s.lenght() every time because it's probably a linear opeartion. Just calculate it after reading and use the result in the "for". (at least that's how c++ works)

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

    In "for (int i=0; i<s.length(); i++) {" You called s.length() every time in the loop, and the time of each time you call "s.length()" is O(n). So your submission is O(n*n). You had better use "int len=s.length(); for (int i=0; i<len; i++) {...

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

      it is O(1) in java. reason for TLE is string concatenation

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

    Java string addition copies every time both the string and then gives new String.
    This will eventually turn out to be O(N2) for large operations. You should use StringBuffer for appending the result.

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

waiting for rating change

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

Wish I can turn blue now! Waiting for editorial and how to solve DIV 2D?

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

What is this about cheaters?

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

    ?

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

    Maybe the cheating is in div2C... How some people got it Accepted in few minutes.... !! Maybe it is a old problem......

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

      No, its actually very easy. Problem setters should not assign higher points to easy problems. It is really unfair.

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

Guys thank you so much for such an awesome contest, really enjoyed it, can't wait for more AIM Tech rounds

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

only Div1 Rating changes have been updated , why Div2 haven't been updated until now ?

UPD : it's now updated

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

This is the first time I solved problem D in a contest.....I was having some bad previous contests..I can expect a good rating change now :)

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

    and you got it, congratulations +114 :D

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

after all ... contest was easier than previous ones ...

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

what was the hack of problem c div2

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

    Maybe it was "aaaaaaaa" or something like this....

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

can someone explain why aaaz is lexicographically < aaa ?

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

    It's not, but you must change exactly one substring.

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

    I think you mean aaaz is lexicographilly < aaaa? It's mentioned in the problem statement that "You have to pick exactly one non-empty substring of s and shift all its letters". so you cannot just leave "aaaa" not changed then the least change that could be done is to change the last 'a' to 'z'.

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

      Yeah I missed that part :/. I Guess I have to pay more attention to the problem statement.

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

How to solve div2E ?

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

    I want to know as well, but here's what I think. We have to calculate subtree size of each node(in a rooted tree) and if the subtree<n/2 then we have to find a subtree in the upward-parent-subtree whose size is h, such that removing this subtree makes the upward-parent-subtree <=n/2 . We can check the number of children a node has, and their subtree sizes to get a range of values for h for a particular node.

    I have no clear idea how to code this, or even , if its correct. But that's all I came up with.

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

    You can refer to this approach. Its similar to mine, but by finding the centroid first, we can do this easily in time. If we don't find the centroid first, then we can't do this in time limit.

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

For Problem C i have coded a solution of Time Complexity O(n) but still i'm getting a TLE .

Can someone point out why this is happening?

https://ideone.com/oPOD8j

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

    You have an O(n^2) solution, because of the way how you add the charachters in be=be+s[i]; . Effectively, each such call copies the whole string that is build thus far.

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

      No,i think it's O(n). Suppose you have an array : A{1,2,3,4} and you want to calculate the sum of it.

      for(i=0;i<a.size();i++)
      sum+=a[i];
      

      This addition of integers and addition of character's to a string takes the same complexity i.e. O(n)

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

        Yeah, string s += char is NOT the same as s = s + char. The first appends char, the second computes s + char, then sets s equal to that. I hacked someone on Div 1 B based on this.

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

          Doesn't seem like a very efficient way to handle things. Is there any need for this separation? They could've overloaded the operators to act similarly, unless , there is some use.

          edit: yeah, t=s+a. I'm silly lol

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

            + has to make a copy of the string, otherwise stuff like x = s+char wouldn't work (and the compiler doesn't know s=s+char and s+=char mean the same thing).

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

              I literally figured it out while you were writing this comment lol

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

              Could you explain E's approach?

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

                Denote the centroid of tree as X, then reassign root to X (You can easily find out X). Now X is the tree's root, it means that every sub-child node of X has no more than n/2 children.

                If vertex U is the new centroid, only n — numChild[u] is possibly greater than n/2. Now you need to find the vertex V (V is not sub-child of U) then break it from tree, re-attach to U. Checking new tree

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

                  But how can we do this without iterating the tree back and forth multiple times?

                  edit : I think I understand how.
                  1. We find the centroid C of the tree and root the tree at this vertex.The answer for this vertex is obviously yes.
                  2. Then we move down one of the subtrees. We are now at vertex V
                  3. Then, we must remove a subtree from the other child of C and attach it to subtree of V, such that size of that removed subtree is n/2-subtreesize[V].
                  4. We can achieve 3. by using euler array of the tree rooted at C. This is because the removed subtree will always come from one of the children of C which we are not currently traversing.

                  Correct me if I was wrong anywhere.

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

                  **from the other child of C** => It should be other children of C, which are not child of V.

                  We can find this vertex by using segment tree

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

                  Thanks man :) I think now I've fully understood how its to be done.

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

How to solve div2e?

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

    Remove largest tree from eccentric child if the tree is rooted at i. The largest tree's size should be of course <= N/2 as we will attach this tree directly to i. I used timestamping and some arrays to find the largest tree. You can refer to my last AC code.

    It was very hard to debug it during the contest sadly :( .

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

Anyone Pls tell me how to solve the problem B in Div 2 ?

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

What happened to the rating changes? Are cheaters being dealt with right now?

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

so...... what happened to rating ?

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

I solved Problem B after reading through comment section and after numerous WA's and edge cases. I want to know how did people think about the strategy to solve it ? I was able to solve A and C quickly but could not even figure out how to do B during the contest. Can someone give me some pointers ???

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

    I struggled with it as well, but I can give you some tips.

    Sorting the points is never wrong in a task like this.

    Also, you'll always either choose not to visit the leftmost point or the rightmost point. For each of these, you'll either go like start -> left -> start -> right or start -> right -> start -> left, you take the min out of those 2 posibilities for not taking pos[0] or pos[n — 1].

    The edge cases are n = 1, n = 2 and if you're between pos[0] and pos[1] or between pos[n — 2] and pos[n — 1].

    I agree that the task is really ugly, but taking it step by step it's solvable.

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

    I'm a little late but maybe my answer will be relevant because it's fast to write and doesn't deal with many edge cases. It's a little overkill though.

    It was basically, store all elements and the initial position and sort them all. Then find where the initial position is in the sorted array, if there is a repetition take the smaller position.

    Now just think that you must visit i positions on left of initial position, 0 <= i <= n-1, and n-1-i positions on the right of the initial position. Then you just need to iterator on i and check if these left and right positions are inside the array.

    Take care that if you visit left first the result may be different of visiting right first so you need to consider both.

    That's my submission: 20114511. I found this way very fast to write and easy to cover all edge cases, took me 13 minutes and 0 WAs.

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

when i will get editorial of this round ?? :)

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

Can anyone please help me with the logic of div 2 E-Centroids?

After finding centroid, I find lca of all nodes. Then, I find the node v from each node u such that

n-subtree[v]<=n/2.

Then, I can make parent of v a child of u.

Before finding v, I make sure that none of the children of the root(centroid found initially) have a subtree such that it can be directly attached to u

//code removed

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

    hi, the link you provided does not show anything. make sure you make it public. i checked your last submission it doesn't seem to use lca in the solution.

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

      I'm sorry! last submission

      I realized that LCA is not needed(to my understanding). From the output it seems that I'm printing 1's instead of 0's for many nodes. A possible reason can be that my C itself is incorrect.

      1. Root the tree at a centroid C.
      2. Find subtree sizes. In array ma[], I store the index of two vertices, which are children of C, which have the maximum subtree sizes. This is so that when I am traversing inside the subtree with the maximum size, I can cut the other subtree, as stored in ma.
      3. If cutting one or the other subtree we have in ma[] doesn't help, meaning that

      n - subtree[ma[0 or 1]] - subtree[current node under consideration] > n/2

      then I cut the edge joining C with the subtree that I'm currently traversing. Clearly, such an operation only needs to check the subgraph containing C because the other subgraphs will definitely have size<=n/2.

      But I think I'm missing some test cases. Do you know which cases?

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

        you are just computing the centroid in a wrong way.
        reread your code i believe it's a sleepy mistake.
        here is an ac submission 20357644. i just changed your centroid function.
        BTW, i think this is exactly the same idea as described in the editorial. i don't know if this is intended but check it.

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

          Thank you !!! :)

          I suspected something's wrong with the centroid, but I checked the code just 2 minutes ago and still couldn't find the mistake.

          I didn't realize it was the editorial explanation. I started with LCA and then realized its not needed. Next time I'll make sure I don't repeat such a thing, and check the editorial beforehand.

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

        and i'm actually glad that it doesn't use LCA :P. as i'm not familiar with this stuff yet. willing to study it in the near future though.

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

          With LCA it was not difficult, although unnecessary. It really is easy.

          lca[i][vertex] = the vertex which is at distance 2^i from vertex.(Counting starts at 1. So, a distance of 1 = the node itself)

          lca[0][v]=v;
          lca[1][v]=parent[v]

          lca[k][v]=lca[1] [ lca[k-1][ lca[k-1][v] ] ]

          I think you'll understand why we do an extra lca[1] [..].