Neodym's blog

Codeforces Round #262
By Neodym, 10 years ago, translation, In English

Hello, CodeForces! On 20 August at 19:30 MSK will take place 262 (Div. 2) round. Div1 — participants can take part out of competition, as usual.

The problems were prepared by Victor Vasilevsky(vitux) and Aliaksei Semchankau (me). We'd like to thank Gerald Agapov (Gerald) for help of preparation of this round, Michael Mirzayanov (MikeMirzayanov) for comfortable platformes Codeforces and Polygon, and Mary Belova (Delinur) for translation of statements.

In this round you will help to different good people. We sure that every participant will find an interesting problem for him:)

gl & hf!

UPD: It will be used a standard scoring.

UPD2: Also we'd like to thank Vitaly Aksenov(Aksenov239) who helped a lot in fixing of Russian statements.

UPD3: We'd like to congrat top-5 participants!:

1) buptcjj

2) 6wr1

3) ladpro98

4) shaojj

5) linjek

Also we'd like to congrat jellygendut, who got 20th place and solved problem Е — It has been solved by 3 participants. Nobody has solved all problems, but every problems were solved by participants succesfully.

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

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

The link to timeanddate is broken ;)

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

Brace yourself, newly registered users are coming.

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

    recently new registered users are very genius!

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

      are you sure about "new" users !!

      I am not sure but i think 90 % among of then is Div1 members.

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

        Irony is the very complicated thing, huh?

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

      lol

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

Two consecutive Div.2 only rounds ! :|

Time for a Div.1 + Div.2 round :)

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

    Hope that time of div1 will not be long.

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

    Maybe it should be called Div.1.5.Because it is harder than usual Div.2 and easier than Div.1.

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

I think this is time to be pupil.. :D

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

Happiness is , checking the 'Contest' tab each alternate day, and finding a Codeforces Round there! :)

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

    sadness is to discover that the contest is div2 only

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

      Sadness is losing internet connection in the middle of a rated contest while you just want to submit a problem and having connection back as soon as the contest finishes! :)

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

        Happiness is to find out later that the solution you wanted to submit was actually wrong and thankfully you did not make any other submissions as well in the contest. Ratings saved -_-

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

          No, happiness is finding out that you actually submitted it somehow and got a REALLY high place because of it.

          And sadness is finding out that it failed on systest no. 124.

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

            As I see, happiness can be anything! :D Maybe we should create this topic: What is happiness at Codeforces?

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

            is that happened to you? Failing on 124 B(

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

              In Gym, once. But not in this "happiness/sadness situation".

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

    A lot of happiness and sadness theorem :p

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

A wave of "Black ID" ~ ~

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

    I don't know why your handle of codeforces is so special :|

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

      The first time when I used Topcoder Arena,I thought that "TopCoder" have a better message,so chose It.It is To Be Top Coder for me , but not for TopCoder,INC.##Too young at that time .~,~ ~,~

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

gl & hf :P 2 mny CHRs

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

The first Codeforces Android Application is now available on the Google Play Store. You can download it here-

https://play.google.com/store/apps/details?id=com.innsolutions.codeforcesstats

With this app you can do the following things- 1. User Info- Basic Profile Info, Rating Change History, Submissions History of any user. 2. Compare Users- Compare the overall info of as many users as you want or Compare Head To Head which lets you compare upto 4 users in Common Contests, i.e., contests in which all the given users have performed. 3. Search Problems- Search for problems by tags, index, name, contest id or solved count. 4. Search Users- Search by name, handle, organisation, city or country.

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

    sadness is , in our country we can't visit google web page,because of Great Firewall :(

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

    LOL! :D

    I try It Application. It seems to me that it's a completely useless app. Sorry.

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

      Hey knst no need to say sorry. You did not like this app, that's fine. This app does what it's supposed to do, whatever's written in the description. If those features are of no use to you, just go ahead & uninstall it.

      As far as the ad displayed there is concerned, i have nothing to do with it. Those ads are put there by Google & i had no idea these type of ads could be displayed. Well I'll remove the banner ad in the next update. Sorry for the inconvenience.

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

I have a question (I'm new to here.. I've attended just one round in Codeforces)

If I register this round, then I must attend the contest? so If I have a important thing to do, and I can't attend the contest, then my ratings will fall down?

(sorry for bad english :< English is not my native language...)

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

    Rating won't be changed unless you submit something.

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

      Aha! Thanks for your reply. I've worried about that..

      I'm a high school student in Korea, and the contest will be started at 00:30 AM in korea.. It's too late here :<

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

Time i move up to specialist or maybe Expert

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

    you only need -2 too reach newbie even if you get rank 1 you cant reach expert :|

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

      I went from 1283 to 1602 in one contest, so it is definitely possible.

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

    Keep Calm and be expert ;)

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

    You are sure to succeed if you work harder.believe yourself :)

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

      Thanks for the encouragement guys and too keyvankhademi thanks for the moral boost i needed that.

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

gl & hf :)

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

Help me :( I am new here and I am not able to find any link to register for Round262. There's just date and time link but no registration link :/ Someone help me quickly, only 90 minutes left for registration.

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

Let's (not) hope for more math(!)

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

My first contest hope I get good ranking :D hue hue

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

    Are you a genius black (unrated) ? or no?

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

      He's from Krusty Krab. I do belive he is!

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

        What do they do in Krusty Krab?? He got 6th place!! :D

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

          They cook Krabby Patties, WITH CHEESE :D You must learn cooking them. Please refer to spongebob. ;)

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

            Their Krabby Patties must be as hard and brute as his hardcode 7530765

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

              :o longest code ever I saw in my life that someone make in contest :|

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

                I guess he wrote another code to generate this code :) It seems easier.

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

    guy,good luck to you !

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

oh,div.2!why two times?

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

Hope for all "beautiful" bruteforce problemset only and strong pretest :v

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

    even my granny can solve brute force let's hope to be able to solve hard problems ;)

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

I think some of the people in Div. 1 are using some fake accounts to enter Div. 2 contests and because of this we can't rise. I think you should find a solution to this problem.

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

Let's have fun and enjoy codeforces!

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

what a hot contester:O

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

Scoring?

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

I've always had this question in mind.

When you click on Registered Users > Friends.

How are the users ordered? On what basis?

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

    on time of registration it's easy to understand when you register you come first :D and so on

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

Sadness is electricity go out in the middle of a rated contest ! Egypt !!

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

WOW, a record in registrants 4824 :D

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

Over 4000 contestant take part in. This will be an interesting round!

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

hi can someone from codeforces look into it hightail gives it correct ans but it fails on pretest 1

sub id-7526210

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

Shame.

x

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

There are many newly registered users on top of standings... the same to what happened at recent contests...

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

Wasn't B harder than usual?

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

I think my solution of problem B will not pass system test, but i got 4 successful hack on problem B. :P

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

    the same :D

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

    What is the tricky test in problem B?

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

      writing your own pow() function :P

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

        Is it because of integer overflow?

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

          nope, precision error when casting to long long, pow() function returns double, just check this, cout<<pow(5,2), then after casting see this cout<<(long long)pow(5,2), returns 24 instead of 25

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

            I wrote my own pow function, and i failed the system test because of overflow. Anyway thank to you that now i know i should use my own function for pow for precision.

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

            Do you know how could i reproduce it in my computer? I get 25 and not 24 in both cases, I swear... When i run the testcase in which i failed in the final tests in my computer, it returns the correct result... I HATEE THISS!!!!

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

              it can return either 24.999999999, if you cast in this case, it would return 24. But it may also return 25.00000000001, and in that case you will end with 25 only after casting. There may be some case where it is failing. Try printing the float values in your submission.

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

              you can use the O(log n) implementation in pow

              a^n=a^(n/2)*a^(n/2) if (n%2==0) a^n=a^(n/2)*a^(n/2)*a if(n%2==1)

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

      Some people enumerate the x rather than s(x).Some people didn't consider all the answer should less than 1e9. Sorry for my poor English.

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

        Some people check s(x) in range 1..72, and I don't understand why.

        Are they really thought, that max(s(x)) == 72?

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

          They probably thought that 10^9 has 9 digits and 10^9 — 1 is 99.999.999, which has 8 digits. And 8 * 9 = 72.

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

          But one man in my room check s(x) in range 1..100 and check res=b*pow(i,a)+c in range if(res <= 1000000000) And it is clear solution... :)

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

            It is really a correct solution cause s(res) can't be bigger than 81

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

              It is correct; for s(x) ≥ 82, you will simply fail either the check s(res) = s(x) or the check res ≤ 109 all the time.

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

          I did max in range 72. Made the silliest of counting mistakes!! Green now!!

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

Lets make a predictions D's test #7 K equals 3 ..!

I only doubt on 3'Ks for my solution.

UPD: a bug found. maybe K equals 2.

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

What is the tricky test case for Hacking B ?

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

Problem B was so easy to hack! Just use (for example) "5 710 1" as an input for people who used int instead of long long :)

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

There was something wrong with pretests for the second question . I was getting the correct output on my compiler. But when I added if(x == 13726)cout << "" ;

I could pass the pretests I don't know why .
→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

While I'm trying to hacking a solution by generate input using generator in c++ I see a line. ( I don't remeber it). I put -o2 but it doesn't work. What should it print in that line?

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

Can somebody please explain, why http://ideone.com/rbsIwP works on ideone, and not on the judge (or in codeblocks either). I wasted around 50 minutes wondering about the problem with my solution, and at last just gave a try to user defined power function and it worked. But why was i getting different results from two judges running the same compiler??

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

    If you used pow(), then note that this function works with floating point values and might not compute the exact answer. For example, pow(5, 2) might return 24.99999999.

    It is generally undesirable to involve floating point computations in places where integer math would suffice.

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

      Ok, I knew it returns double so used casting....but just carelessly ignored the fact that it might need a ceil function as well...will try testing with (long long)ceil(pow());

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

        What if pow(5, 2) returns 25.00000001? :)

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

Contest is over ! I solved C by binary-search the answer + O(n) check. D seems to be hard with that xor operator. I got E pass pretest using back-tracking n elements from a set of a few boundary points. Hope my solution can get AC.

Upd: Yeah!!! E Accepted. Hello Div 1 :))

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

Wrong answer pretest 1 of problem B ??? really frustrated!!!!

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

    Got the same problem then one of friend told me not to use the built in power and replace it with your function implemented simply iteratively and it worked. I hope same is the case with you :)

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

    Yes, that happened to me as well. You have to define a pow function yourself, the default one won'w work (no idea why honestly).

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

how to solve B ?

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

    you must try all of s(x). s(x) is in range(1..81). so for each s(x) you calculate x=b*s(x)^a+c. If x>0 && x<1e9 you add x to the list of answers. Something like that :D

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

      You forgot to check is s(x) equal to current sx

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

    x = b*pow(s(x),a) + c As s(x) <= 81 as x <= 1e9 Take a loop from 1 to 81 For each i find x = b*pow(i,a) + c If s(x) == i and 0< x < 1e9 then x is a solution

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

    My solution for example. You check every sum of digits from 1 to 81 and compute X from equation. Then just check that sum of digits of X is equal to yours.

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

    You just need to iterate through different possible values of s(x) as there are only 81 possibilities for it in case of 999999999 it will be 81. now find the expression b*s(x)^a +c and check whether obtained x has the same s(x) value or not.if yes increase the counter.also need to check whether x<=10^9.

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

      could you explain pls why there are only 81 possibilities,i couldn't get that point.

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

        If s(x) is the sum of the digit of number x, then the maximum sum we can achieve is with number 999999999 (10e9-1). In this case, s(999999999)=81. Hope this helps :)

        We cannot have a sum larger, since 9 is the biggest digit we can get

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

    I was getting wrong answer on pretest 1. Can anyone check my submission. I did the same thing as you guys mentioned. http://mirror.codeforces.com/contest/460/submission/7530259

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

      Never use already implemented pow function unless you need it for doubles, write your own, its not hard, and even O(exponent) one is okay with time :)

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

      7534711

      You must be careful with pow(). Also, there is bug somewhere else.

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

I just noticed D asks for any subset with cardinality <= k, not any subset with cardinality = k... Now I know why everyone was getting AC so fast :P (hint: the xor of x*4, x*4+1, x*4+2, x*4+3 is always zero)

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

    how to solve K=3?

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

      2·2i - 1, 3·2i - 1, 3·2i for some i if there's any; otherwise the XOR is at least 1.

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

        that seems not to be the only condition. counter example: 5 ^ 10 ^ 15 = 0

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

          If the range includes the numbers 5, 10, 15, then the range also includes 7, 11, 12 (generated by i = 2) whose XOR is also 0.

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

        I'm wondering: how did you think of this triplet?

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

          I thought that 3, 5, 6 works (gives XOR of 0), so there is a possibility with three numbers. Then I toyed around with proving of stuffs. Like, the most significant bit that is set among the three numbers must be set twice for the XOR to be 0 (e.g. 5 and 6 both have third least significant bit set). Then the remaining number will obviously be the minimum, and consequently to minimize the range covered (and thus maximizing the probability of a range having these numbers), we need them to be . Then the second most significant bit must also be set twice, so we have three numbers 2i + a, 2·2i + b, 3·2i + c where , and obviously we minimize the range covered by letting a = 2i - 1, c = 0, and b = 2i - 1 follows. Then I also managed to prove that this is the best solution; that is, if these numbers aren't possible (and k = 3), then there is no solution with XOR 0.

          Confused? Yes; I'm not even sure how I managed to stumble on that solution.

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

          I used this in my solution. Suppose k = 3 and there are three such numbers whose XOR gives 0. Let's look at the numbers bit by bit. First, the highest bits will be

          1.....
1.....
0.....

          (there is no other possibility). Now, for the next position, there are several possibilities. First, all three bits can be 0:

          10....
10....
00....

          We can actually do this for zero or more positions:

          1000....
1000....
0000....
 ^^^
 0+ times

          But on the last position there has to be something different, otherwise the first two numbers would be equal. So, on some next position there won't be three zeroes, and we arrive to the other two possibilities for this position. The second one is

          1000..1...
1000..0...
0000..1...
 ^^^^^
 0+ times

          We want to keep the numbers close to each other because of the l, r constraints. So let's make the biggest number small as possible and the smallest number big as possible:

          1000..1000
1000..0111
0000..1111
 ^^^^^
 0+ times

          And for the third possibility:

          1000..1...
1000..1...
0000..0...
 ^^^^^
 0+ times

          notice that if we can use it, then we can also use the solution for the second possibility. So, the final answer is

          1000..1000
1000..0111
0000..1111
 ^^^^^
 0+ times

          or 2i + 2j, 2i + 2j - 1, 2j + 1 - 1 for permissible values of i, j. Now we can just check all values of i, j and see if the result fits between l and r.

          And now (I realised this after seeing chaotic_iak's answer), if we have an answer of form

          1000..1000
1000..0111
0000..1111
 ^^^^^
 0+ times

          then the answer

          11000
10111
01111

          also fits the l, r constraints. So we can let j = i - 1 and only check

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

    if x%2==0 then x^(x+1)^(x+2)^(x+3)==0 :D lol

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

    nice observation, thank you

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

My solution for problem C was failing the test case

6 2 1
1 2 2 2 2 1

because of an under flow that I discovered 3 mins after the end of the contest ! :D Ok that's something new :D

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

    And I failed the B because of an overflow and failed the C because of an underflow :)

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

In fact, this competition was really fun. I knew I will be hacked at B, cause I didn't check the upper limit, so I started searching for people that didn't do same thing, and got 5 successful hacks. After that, I noticed that a lot of people were only checking the sum of the digits up to 72, so I started a brute force program to find some solution which sum of digits is >72, and found one, another +500 points. In fact, the thing I wrong-solved it gave me bonus points. The thing I forgot to set upper bound of binary search to 2*10^9, so I lost that task, and only one guy also forgot that, the guy who hacked me. :D Btw, the contest was great!

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

How to solve C , Can anyone explain ?

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

    Binary search the solution, and try to implement your own check method, can the minimum be x?

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

      Can u explain ur check method ?

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

        Uhm, lemme try(atleast how I did it) First, make an array left, such that left[i]=max(0,x-a[i]) After that, iterate through that array, and see, if the current number of "open" intervals is less than left[i], open more left[i]-cur intervals, always number of total intervals and number of current intervals. You can check my solution, it failed because of the high constraint, the check method is right.

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

http://mirror.codeforces.com/contest/460/submission/7531713 what was wrong with my div2 C solution? I used binary search

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

    One problem is that the answer can be more than 1e9.

    For example:

    1 10000 1
1000000000

    The answer is 1000010000, so you just need to change "high".

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

This contest was very frustrating >.<. At least I learned that using the built-in function pow() is bad and I definitely won't use it in future contests. The amount of newly registered users placing in the top 500 is insane, and seeing others in your rooms getting hacked by reds before you can even try to hack them is sad. Please let there be a contest for both Div1 and Div2 soon to stop this!

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

fastest sys test I saw in my life !

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

thx for B =)

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

HATE LONG LONGs!!! HATE COMPILATION ERROR!!! I was late with my correct D solution just for 5 seconds!

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

Back to Specialist !

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

In the task statement for B, it is clearly written: "Print only integer solutions that are larger than zero and strictly less than 109.". However, the output for the 10th case is:

6 208000352 1333225037 -2113928864 -881045069 855318976 -1059281175

Can someone offer an explanation, please? :)

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

    That is your output, not the judge's answer.

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

      I am an idiot. Sorry for taking your time. :P

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

    This is the output of your program not the output of the tester's solution !

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

Hi, I try to make a solution for B problem, but my solution failed in the final case, however I can not understand why, somebody can explain me, here is my solution http://mirror.codeforces.com/contest/460/submission/7531464

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

    You check whether number is smaller than 108, rather than 109 (count zeroes). AC:7534579. And exponential format is your friend (it is absolutely precise because mantissa of double is 52 bits: 7534816) in avoiding such errors.

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

    the argument to sumDig() function in the following line can be greater than what 'int' can store :)

    if(i == sumDig(b * pot(i,a)+c))
    → Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    In function SumDig(int a) , I think the parameter should be SumDig(long long a) instead

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

Well, I'll be green again :-(

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

First blood on E! And 1 condition away from 2nd place...

I'm surprised at how many people failed it and especially at how many reds did, it seemed like the pretests were quite strong (due to asking for a complete solution). I solved it using DP on states (,) of towers placed so far, plus not trying all points but only border points — observe that if we can pick points (x + 1, y) and (x - 1, y), then for (x, y) to be picked as the last point in a possible solution (these other points don't give better solutions), and respectively, but then and we can move this point (x, y) left and right without changing the answer; similarly for the y-coordinate. Then, I get an O(N3R3) solution with a good constant.

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

I tried to solve C in a different way, Like , I built a segment tree with range minimum query with the left most minimum value. Now each day , I find int r = RMQ(1,n) and update range from r to r+w-1 with value 1. after mth day the RMQ(1,n) is the answer. I got WA in case 8. I don't know if it is due to my wrong implementation of the segment tree or my idea is wrong. Can someone tell ? Here's my submission 7531931

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

Bad Day for me in problem B.

Hacked

AC

The only difference is that I did not check for x > 0 && x < 10^9.

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

Codeforces round 262, div 2 problem 2

http://ideone.com/7ghrM6

my code is working correct on ideone (for the incorrect test case) but its giving wrong answer here. Please help!!!

http://mirror.codeforces.com/contest/460/submission/7533280

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

    Dont use implemented pow, write your own.

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

    try to code your own pow function because you loose data going from double to long long.

    inline ll ipow(ll x, ll a)
{
	if(a == 1)
		return x;
	if(a == 2)
		return x*x;
        // and so on..
	return 0;
}
    → Reply
»
10 years ago, # |
  Vote: I like it +2 Vote: I do not like it

For Problem B

my solution on ideone gives the correct output for the case : 3 2 8:

http://ideone.com/JctOLq

but on codeforces compiler it is showing different answer: http://mirror.codeforces.com/contest/460/submission/7534562

can somebody explain why ?

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

    It happened because you used the pow function which works with doubles and has precision errors. It has been said in an earlier comment that (long long)pow(5, 2) returns 24 instead of 25 because the double returned is 24.9999 and it is casted to an integer value.

    The MS C++ compiler has another implementation for pow and it works better in this problem. This is how I got ACC with the inbuilt function.

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

Very nice contest. D was very interesting , especially when k = 3. E was a bit harder than usual. I only succeded in makeing a back placeing half of the towers and put the other ones simetrically. I am not sure of it's correctitude , but I think it's a way to go as N ≤ 8.

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

Problem B, Getting right answer con muy visual studio and ideone, but in the contest shows a different answer,#7533294

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

    I actually got the same problem =D

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

Can someone please give a clear explanation how to solve problem C?

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

In problem C, test case 5

10 8 3
499 498 497 497 497 497 497 497 498 499

How is the answer 500? Isn't it supposed to be 499?

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

    Water indices [1, 8], [2, 9], [3, 10] (one-based).

    EDIT: Wrong reading. (I didn't solve C.) Water indices [1, 3], [2, 4], [3, 5], ..., [8, 10] instead.

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

    We have m = 8 and w = 3. So lets do 8 operations:

    after 0 operations: 499 498 497 497 497 497 497 497 498 499
after 1: 499 498 498 498 498 497 497 497 498 499
after 2: 499 498 498 498 498 498 498 498 498 499
after 3: 500 499 499 498 498 498 498 498 498 499
after 4: 500 500 500 499 498 498 498 498 498 499
after 5: 500 500 500 500 499 499 498 498 498 499
after 6: 500 500 500 500 500 500 499 498 498 499
after 7: 500 500 500 500 500 500 500 499 499 499
after 8: 500 500 500 500 500 500 500 500 500 500
    → Reply
»
10 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

vitux Neodym I am always getting this stupid warning in B, even though** I have no printf statement in code**? Please tell me the reason. it is not even allowing to submit.

Code : http://ideone.com/2kAsED

Here is the screenshot. Screen-shot : http://postimg.org/image/5rtdr33kt/

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

Can someone explain how to solve C using binary search?

I can't figure out how to check if some number 'X' is a solution.

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

    the check function is f(x) :

    you can do it greedy, 

    for i to n
   if seq[i] >= x : no do nothing!
   get how much do need to do until x  (seq[i]-x)
   restart need to m
   add need seq[i, w+i]
    → Reply
»
10 years ago, # |
  Vote: I like it +1 Vote: I do not like it

When will i get the editorials for this contest

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

Problem C : Please Explain why updating from left-Most or Right-Most minimum solve the problem.Will It be work (Select any continuous Subarray of length m containing minimum number) and why??[contest:460][problem:C]

.

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

    i doubt the 'any continuous subarray of length m containing minimum' will work, but left most or right most will

    this is my general idea : input : 6 2 3 1 2 1 2 1

    updating left most smaller will resulting an array : 2 3 2 2 1

    then, because 1 is smallest, we choose updating index 4 till 6, becoming : 2 3 3 3 2

    if we update the middle first (index 3), it will has result : 1 3 2 3 1

    and after that, anything we choose will still have value 1 in array

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

Topocder SRM 630 in 6 hours, will miss it :(.

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

Irony of the day ! When I thought that this is was not my contest. I had a message from Codeforces telling me that I got one of the best rating changes in this round.

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

Problem C: A teacher can have a birthday after 10 ^ 5 days? :D

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

    Yes, if teacher lives on Saturn or Neptun

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

My Code For Problem B gives the right answer for 1st case on my IDE But Different one on the judge !!

http://mirror.codeforces.com/contest/460/submission/7536450

What is the reason behind that !!

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

    You are using the built-in pow function. It has been discussed above why it's not correct.

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

Country Wise Standings for this round has been updated.

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

Hi, I'm new here. I submitted for the first problem two times, I got a run time error in the first attempt and my second attempt was accepted. and I didn't solve any other problems. The strange think is that my rating decreased!! Can anybody explain why this happened? thank you

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

    Your expected rank was less than 1733 and you got around 2400 so that's why your rating was decreased.

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

I wrote short description of possible hacks with some statistics. If you are interested — take a look: here.

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

Hi.

I had error in the problem B, for one case.

Now that I can see the result, it is very strange because on my computer gives the full result.

This had happened to me once I think. What mistake I be making?

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

    Man please do you read posts? It has been asked a lot. Nevermind, you need to make your own pow function because built in pow function won't work. That's the whole thing.

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

    Please read the comments above, the pow function works with doubles and sometimes has problems with precision. Write your own pow function and everything should be better.

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

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

The final answer about using the pow function is:

  • Use the BUILT-IN function with type casts ONLY IF your language is "Microsoft Visual C++ 2010"

  • OTHERWISE use your own function (e.g. when using GNU compilers)

As far as type casts are considered, see this submission as an example: http://mirror.codeforces.com/contest/460/submission/7535442

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

    The answer is to avoid pow() altogether for integer math. It works with floating point values, there is no guarantee that it will return the precise answer. Even if it does compute the precise answer for some integer values, double still typically has less than 64 mantissa bits, and the result cannot be always stored exactly.

    For example,

    (long long)pow(5.0, 23)

    on MSVC++ returns 11920928955078124 instead of 11920928955078125.

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

I had seen the editorial,seen the solution but didn't understand the solution of problem-C(present),why we do binary search in that problem,can anyone easily explain me the solution :/ .

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

    I will explain my solution, which got AC during the contest.

    First of all, we can notice that if we binary search the minimum height of a flower, we'll call it X, and we can do at most M updates to make each flower of height >= X, any minimum height < X can be a solution of our problem, because we can do the same updates as for X.

    Now, we have X and we try to see if X can be a valid solution. Let's note S[i] = minimum number of updates we should do over the first i flowers to make each flower with index from [1...i] at least of height X. We look at the i-th flower and we determine it's current height as follows: CurrentHeight[i] = InitialHeight[i] + S[i — 1] — S[i — W]. (S[i — 1] — S[i — W] denotes how many updates we did over the intervals of length W, which cover the i-th flower). If CurrentHeight[i] < X, S[i] = S[i — 1] + X — CurrentHeight[i] (we do X — CurrentHeight[i] updates with the leftmost element as the i-th flower), else S[i] = S[i — 1].

    If S[N] <= M, X is good and we look for a bigger one, else we look for a smaller one :)

    Code: http://mirror.codeforces.com/contest/460/submission/7521789

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

Round #263?

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

where are this rounds editorial?

→ Reply