scipianus's blog

Codeforces Round #271 (Div. 2)
By scipianus, 10 years ago, In English

Hello, Codeforces! On 6th October at 19:30 MSK the Codeforces Round 271 (Div. 2) will take place. Div1 participants can take part out of competition, as usual.

I am Ciprian Olariu (scipianus) from Romania and this is my first round on Codeforces. It is more special as it is held right after I became red on Codeforces. I would like to thank Maxim Akhmedov (Zlobober) and Gerald Agapov (Gerald) for helping me to prepare this round, Delinur for translating the statements and also MikeMirzayanov for Codeforces and Polygon platform.

In this round the main characters will be Mole and Marmot, two good friends, and you will help them in their activites.

Please note that this round will have an experimental duration of 2.5 hours and 6 problems. The scoring will be 500-1000-1500-2000-3000-3000.

I hope you will enjoy the round. Good luck and have fun :)

UPD : To avoid overlapping Topcoder SRM #635 and Bayan 2015 Contest Warm Up, we decided to move round to Monday 19:30 MSK

UPD 2 : The editorial was published here

UPD 3 : Round has finished. Thanks for participating. Congratulations to the winners:

stonebuddha

Syloviaely

vanhanh.pham

__PLEASEDONTHACKME__

LOVESY**

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

Comments Comments (152)
| Write comment?
»
10 years ago, # |
  Vote: I like it +42 Vote: I do not like it

6 problems? why not add one problem to take place the DIV1? :(

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

    This is an experimental round format for Div.2, the 6th problem added is an easy one.

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

      So 6 problems of the contest will be @,A,B,C,D,E instead of A,B,C,D,E,F??? ('@' is the previous character of 'A' in ASCII)

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

      the 6th problem added is an easy one

      So you mean that between problems E and F one of them is easy ???

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

        I mean that there are 6 problems, sorted by difficulty :P

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

          That means the 6th problem added is the 1st one! :p

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

    Its sad because most of us will not solve D,E (div1) anyways. We could just do rated "div 1" seperately with last four problems :P

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

    even if not adding one more problem, how about using the 6 existing problems like this

    1. Div-2 A
    2. Div-2 B
    3. Div-2 C + Div-1 A
    4. Div-2 D + Div-2 B
    5. Div-1 C
    6. Div-1 D

    then both divisions will have 4 problems (maybe contest time can be reduced).

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

    its experimental round format

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

Crosses with SRM 635: TopCoder schedule

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

OMG, doesn't Bayan Contest Warm Up round overlap with this?..

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

I think the time should be changed because at the same day there would be a Bayan contest and it would be held 2.5 before your contest while it's duration is 3 hours. Edit:oh adamant was faster than me.

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

And now, the age of 2.5 hours contests...

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

    The age of > 5 problem contests; first 270, then bayan, then this.

    I guess codeforces is showing evolution !

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

Now the date and time should be fine. Sorry for inconvenience.

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

The contest ID is lucky "474" :D

The contest will be great, hope that!

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

why without div1

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

    What will you do with a div-1 contest ?? :P

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

I always attended contests like "Happy New Year Contest" , "April Fool Contest" etc etc . But never attended an "Eid Contest" ;) (Luckily today is Eid Festival here in Bangladesh :) )

So , Eid Mubarak to all Programmers :) :)

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

Oct. 4 — SRM 635
Oct. 5 — Bayan Warmup
Oct. 6 — CF Round 271.. div2

Nice three days :)

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

Good luck!! I think everyone will enjoy this contest.

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

It's Eid contest for some contestants :D.Today is Eid(Eid-ul-Azha is the 2nd largest festival of Muslim community) here in Bangladesh including some other parts in the world. And some other countries were observing Eid in last 2/3 days. Happy Eid Mubarak to you all :).

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

Did anybody receive any emails? 4 Hours to contest and no email for me yet... . Or maybe because I'm div 1? (sry, first unofficial round :D) Luckily I found out through one of my friends.

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

    I think you registered before the e-mails were sent. I guess they send only if you didn't register. Edit: Register for the contest I mean.

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

    They don't send div2 contest's notification to Division 1 contestants.

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

2.5 hours seems a challenge, hope my battery is enough

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

All eyes again on worse ...

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

Denial of judgement??

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

My problem A is now like this I don't know is it hacked.

00:03:08 Pretests passed [pretests] → 8107570 However,The hack says 117673 2014-10-06 20:26:22 SINUS waltz7l9 A — Keyboard N/A Ignored What does this means?

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

Why isn't possible to hack using generator file?

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

00:03:08 A Denial of judgement [hacks] Hey ! my points!

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

In C problem, can any 4 moles make a regiment or 4 consecutive moles make a regiment? Please clarify ASAP..

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

    There is another place to ask such questions, in the contest itself.

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

      Thanks!!! I didn't know such place previously..

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

Problem E is very interesting, I like it. hope to learn easier solution

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

Can binary search pass the time limits for problem B?

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

How do you do D?

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

    Let's f[n] be the number of good sequences with length n. Formula is f[n] = f[n-1] + f[n-k]. Then if g[n] = f[1]+f[2]+...f[n]. Answer to a, b is g[b]-g[a-1].

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

    If I am correct than we have a recurrence relation:

    for n and k, where n is the maximum of all (a[i], b[i]) (to be safe n can be set to 100000, the maximum length of sequence) and k is the number of 'W's consecutively.

    T(n)=T(n-1)+T(n-k)

    base case T(0)=1, T(1)=1 and for all (n-k<0) T(n-k)=0

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

      Would you clarify/prove why the relation is actually correct?

      It is clear that the first summand in the recurrence corresponds to combinations when 'R' letter is added to combinations derived from T(n-1) step. By it seems that there are more than one way to do it, no?

      The question is the same for the second summand.

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

        Think of this problem as the coin change problem. You've got 1 coin of value 1 and 1 coin of value K. What is the number of ways of putting this coins in a row such that their sum is equal to N?

        I hate dynamic programming. However much I try to understand the concept, I always fail at it.

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

What is the 4th pretest in problem E?

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

What is pretest 3 on D?

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

Can anyone tell me the correct process to hack by generated input. I tried it in two contests. It shows invalid input with this message — "FAIL Expected EOLN (stdin) [validator A_valid.exe returns exit code 3]"

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

    Same here! Though I've hacked before successfully using a generator.

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

    Probably you just forget to print the last new line symbol. Hack tests are strict in all whitespace symbols, you just follow the format exactly.

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

      http://pastebin.com/ASAUu3Ld

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

        You output a space after each number, you should not output the last space.

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

          Is there any way i can practice hacking ?

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

            No way to practice it outside of contest, if you mean that. Did you try TopCoder approach (separate challenge phase)?

            Anyway, there is not that much to practice here, just keep in mind that when you are trying to challenge somebody's solution your test will go through a validator which checks its correctness. And validators are very strict in terms of input, every space and new line should be exactly as they are described in the statements.

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

              Thanks a lot :) . I understand now . Though there was no restriction about trailing spaces.

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

            Try to get into div-1 , then participate in any div-2 only contest,do first 2 easy problems and have fun of hacking without fear of loss in ratings.

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

              There is only one problem with this approach — you will get into a room with div. 1 participants only and it becomes more complicated than hacking in div. 2 :-)

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

                yeah , but he can practice hacking at least.

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

    Yea i got 4 "Invalid input" errors due to that error, but it worked out this way .. http://ideone.com/apqkIr

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

Tried hacking at the last minute, but I got an 'Invalid Input' error, even though I'm pretty sure that the input format was correct. Do trailing spaces at the end of a line cause that?

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

Any other solution of E aside the segtree?

UPD : sorry i mean E but i wrote D

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

what is the solution of E?

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

Problem E was in Andrew Stankevich Contest 29 Task B : Financial Software

the two problems are almost the same :D

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

I implemented everything except for E (even though I have an idea with Normalizing coordinates + DP + 2 Fenwick trees), and I'm very curious about a not so messy solution for E (maybe some greedy may work, not sure though). Anyway thumbs up for the round, scipianus.

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

    not so messy — no normalizing and one segment tree instead of 2 Fenwicks.

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

    2 Fenwick trees isn't messy at all. You just do all the stuff with LIS twice with small modifications.

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

How I can solve problem C?

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

    Try all the 256 ways to rotate the points inside a regiment and see which one is the best. Backtracking and strong nerves are your friends here. Also knowing how to deal with rotations is very useful.

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

      I can't rotate the points, so ignore this problem :|

      how rotate the points?

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

        For rotating I did the following:

        x,y=x-a,y-b
if angle==0:
    return x+a,y+b
if angle==90:
    return -y+a,x+b
if angle==180:
    return -x+a,-y+b
return y+a,-x+b
        → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        cheers (link)

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

        cheers link

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

      I created a solution brute forcing the 256 possibilities, but it kept failing on Pretest2.

      The only thing to consider while rotating was making sure center was shifted to origin right?

      Debugging it such problems is hard. :(

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

    I didn't solve it but i think it is purely math. For each mole there can be 4 orientations. So for a regiment there can be 256 orientations. Just check all these orientations and output the optimal answer.

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

      but problem C is hard than problem D!!!

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

        Not harder. Just painful to implement and quite prone to errors!

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

          mb difficulty(problem) = difficulty(algorithm) + difficulty(implementation) + ... ?

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

        Definitely not, D requires some programming skills and a bit complex things like precomputation, C is straightforward, never mind it took much more of my time.

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

[submission:8118906][submission:8118827] My two submissions for D. I used the recurrence dp[i], if (i-1>=0) dp[i]+= dp[i-1] dp[i]%=MOD if (i-k>=0) dp[i]+= dp[i-k] dp[i]%MOD

and then summed from a to b using another array. Why is my solution failing ?. Pretest 3 precisely.

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

    when u printf the last array : arr[b]-arr[a-1], because it is under the modulus it will result wrong answer if arr[a-1]>arr[b] so to avoid this you should say : ((arr[b]+mod)-arr[a-1])%mod

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

    :( I spent almost an entire contest trying to make this work but couldn't :(

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

      If x is negative after MOD operation, just add the MOD value to it. You could also general formula which should look like this: ((arr[b]-arr[a-1])%mod+mod)%mod

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

Its My first time i Cleared D & E pretest.. Even though its Midsems here i couldnt resist this contest.. Hats of to the problem setter for making this contest so much fun..

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

I thought that I ignore a content when I read a statement, but... Today's blindness and worms eating were not nice. Really :)

What about making more positive problems next time? (Rethorical question)

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

    I almost threw up whilst reading the worm eating part :|

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

One of the best Codeforces contests I have ever competed in! The problems were awesome! Kudos to the setters :D

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it 
main(){
    int i,d=10000-3;
    cout<<d;
    cout<<endl;
    for(i=1;i<=d;i++){
        if(i!=d)    cout<<1<<" ";
    }
    cout<<endl;
    cout<<d<<endl;
    for(i=1;i<=d;i++){
        if(i!=d)    cout<<d-2<<" ";
    }
    cout<<endl;
}
This is correct hack or invalid input? Problem B
→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Weak pretests for B = Happy happy me :)

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

    It makes me happy too (9 successful hacks)

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

problem D is easy problem!!!

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

Mb such contests will reduce rating dispersion (more problems => rating estimation is better). But it will be harder to prepare good round.

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

Great round, I enjoyed the problems a lot.

(maybe I say this because I solved a lot :P)

Edit: reached div1 :D

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

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

Tourist scored more than 10k points in this contest. Is this the first time this has happened?

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

    Well having 6 problems for a div-2 contest isn't that common either.

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

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

How does tourist solve all problems in 30mins of which he does the first one in a minute?

How can he manage that much reading, typing speed.

Does he do screencasts like Petr? I'd love to see a screencast of him competing.

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

http://mirror.codeforces.com/contest/474/submission/8116443 why wa on tc 34??

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

    Really silly mistake, dp[1][1]=(k==1)?1:0; should be done after taking input. But actually this isn't necessary at all. Just initialize the base case for position 0 and loop from 1 instead of 2. The DP value for position 1 should be calculated automatically.

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

I think this solution should not pass. Maybe the test cases were weak.

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

    fail on test

    100000 1

    1 2(99998 times) 3

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

      Yeah, I know that. I just wanted to check if it would pass or not. To my surprise it did. The test cases were too weak I guess!

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

    it's a funny magic, but the minimum constana is 128 xD, with 127 WA 39, with 128+ AC!

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

I think 2.5 hours long contest with 6 problems is more enjoyable than 2 hours long contest with 5 problems. Looking forward to participating in more rounds in this format.

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

I hadn't had integer overflow bug for like a year, but now it just came back from E! (I assumed h <= 1E9). Thanks for warning me to be always careful.

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

Problem B: 8122368

Time Comlexity: O(mlog(n)).

Why TLE?

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

    I also used the same idea. Probably the TLE is happening due to using pair in vector. You don't need to push both the starting and ending values, only starting value should suffice. Then BS on that vector. You could look at my solution: 8113015.

    UPD: Your BS implementation is wrong. It is doing linear instead of binary. Replace u-- with u=mid-1 and l++ with l=mid+1.

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

      Using vector doesn't lead to TLE. My binary search is indeed correct and it divides the search interval into half each time, that's an O(log(n)). We have m queries, that's O(mlog(n)) which is sufficient indeed to pass the system test.

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

        I didn't say using vector, I said using pair in vector. But that is not the case here, your BS implementation is wrong and is running in O(n) instead of O(log(n))

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

          It's funny that "BS" is often used as an abbreviation for "bullshit". How accurate it is here :D

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

            Right, like not sure if the BS function is actually BS or BS! :D

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

            Never encountered that xd. Though I encountered it as short form of Bachelor of Science ; d.

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

            This is the funniest thing I have ever seen on codeforces lmao

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

    I think that function "bs" works at O(n). And asymptotics your program O(nm).

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

      It should be u = mid — 1, l = mid + 1. You are indeed correct. Sorry and have a good night.

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

    I don't think you write a correct binary search. "u--, v++" looks abnormal for me. Should it be something like "u = mid — 1, v = mid + 1"?

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

Can anyone look into my solution it is giving TLE but i am not able to understand why ??
http://mirror.codeforces.com/contest/474/submission/8123046

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

I saw successful hacks with test containing char 'q'. Is it valid? I think no.

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

EID MUBARAK All the problem solver :)

→ Reply