Errichto's blog

By Errichto, 2 years ago, In English,

Hello Codeforces community!

Codeforces Round #318 (for both divisions) will take place on August, 29 at 19:30 MSK. It is the Thanks-Round devoted to Russian Code Cup. You will be given 5 problems and 2 hours to solve them. Scoring will be announced close to the round. I strongly recommend you to read all problems.

RussianCodeCup is the largest open programming competiton for Russian-speaking participants by Mail.Ru Group. Its history started in 2011. And since the first championship RCC offers great problems and generous prizes. This year finals will be held on September, 19th. Wish good luck to all the finalists! Thank you, RussianCodeCup, for your gift on the 5th anniversary of Codeforces!

I am honoured to be a problem setter for this round. I wouldn't do it alone. I want to thank Zlobober for his great help with problems preparation and MikeMirzayanov (and all people working on Codeforces and Polygon) for this awesome site. It's an amazing place to learn and compete. My big thanks to winger and AlexFetisov for their help with testing a round. And to Delinur for translating statements. As you see, not only a setter creates a round.

It's my first Codeforces round but not my first problems here. You can check out A, C and D from VK Cup 2015 — Round 2. Also you might remember some of my problems in TC rounds. I'm very happy with finally preparing a full round for Codeforces and I hope you will enjoy it. I tried my best to prepare nice and diverse problemset, you will judge it. In all problems you will have to help Limak who is quite unusual bear.

I wish you great fun and no frustrating bugs. Looking forward to seeing you!

UPD: Scoring is 500-1000- 1750 -2000-2500 in div1 and 500-1000-1500-2000- 2750 in div2. Enjoy a round!

UPD: Editorial

UPD: Contest is over. The winners:

Div1:

  1. Marcin_smu
  2. mnbvmar
  3. subscriber
  4. LoneFox
  5. Shef

Div2:

  1. cesc (5 problems solved!)
  2. fhxb520630 (5 problems solved!)
  3. bugCollector
  4. Izaron
  5. okaduki1

And note from an author. There were some wrong solutions passing. Sorry for that. I tried my best to create strong tests but I failed a bit. Did you like this round? What do you think about problems?

Thanks for participating!

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

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

No T-shirts ?

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

You solve a lot of users' problems in the blogs...

Wish we can solve your problems too ;)

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

    I love Russian ,I love code and I love cup ,it's should be interesting :D

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

Maybe we should study your previous problems well, to get a whole look of the style of your problems. Maybe?

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

Good luck to all participants (Codeforces Round # 318 — Russian Code Cup). I wish you a good mood during the contest and rankings.

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

Considering the previous round i think it will be better to do dynamic scoring.

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

    Considering your downvotes I think it will be better advertisement if they do static scoring.

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

I think someone is getting ready to get first in this contest. to : sorry_dreamoon Be careful. You have a new mission : Antoniuk

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

I hoped this Contest for T-Shirts but ... TT.TT

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

LOL Guys you are so worried about T-shirts as if you can win them)

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

I wish you great fun and no [frustrating bugs]. Oh yeah we all know where this will be going.

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

    Arrrh frustrating bugs. We'll see alright.

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

    **UPD : ** I guess my prediction is spot on. At least from my point of view.

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

This round takes place at the same time as the "Red de Programacion Competitiva" marathon :(

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

Good luck :)

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

I think that I love This contest

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

Actually although all problem statements in qualification and elimination rounds was in Russian two Japanese coders advanced to finals (rng_58 from third place and anta from 21st) :-)

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

Is the statement in Russian only?!?!

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

the stupid one who saw he can't translate, to have upvotes i wish you can translate this comment ************

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

Problems will be in English? or not?

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

Excuse me if I am wrong, but this guy prepared for VK Cup Round 2 one easiest and two hardest problems? If he did than this is real intriging.

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

    I had some tasks and they chose the most interesting ones, that's it.

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

This is usual round, guys. Statements will be both in English and in Russian.

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

Thank you roundwriter! Can't wait to see this round! :)

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

Lets hope Errichto prepares a great editorial as well as a great round for us . In the past few contests he has helped a lot of guys through his insightful comments . ALL THE BEST :)

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

Hopefully, it won't be another Div 0 Contest.

And don't get fooled guys. It will be like last round. In last round, there was a "PPS" stating top 20 of div 2 will get t-shirt, even though they didn't mention it before contest. I guess they are taking things another level higher. Saying no t-shirts now and then giving top contestants t-shirts later :D

Or, they won't be giving any and I am just over thinking. I won't be getting t-shirt either way...

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

Guys, can you please tell me how can i add my school in my profile . Thanks in advance .

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

    Here: Your profile > Settings > Social > Organization

    (If I understood your question hehe.)

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

'Newbie' zone.... be prepared for me.... I'm almost there... ;_;

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

someone should make codeforces fantasy league ,just like fantasy premier league in football ^.^ ,we can bet on favourite coders to win the round

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

    Every one will bet on tourist and every one will win the bet :P

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

      Tourist will bet that "he won't win" and he will intentionally lose to win the bet :)

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

        That will be clear to all and it will be considered as cheating, :P

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

        Wow! But, why should anyone even participate in something like this? Betting doesn't sound nice, besides, how will it help us?

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

        Looks like your guess came true today :/

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

      ofcourse its a raw idea.. we can twist things round such as take any 10 coders where the addition of their ratings should not cross maximum limit or something like this.its upto you how much interesting you can make it :) .

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

Bear Limak will cause us trouble...

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

Looks like something interesting will happen with the bolded problem scores

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

Why 1750 and 2750 written with bold font?

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

    Because usually this problem costs 1500(2500 in div 2)

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

What is the real difference between the knowledge level of a Blue guy and a Red Guy ? ?

I think knowing more algorithms and more exposure to thousands of problems!

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

    They read a problem, and by the time they've finished reading the problem statement, they have the solution. That's the difference.

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

      Even we have a solution to 2-3 problems but when it comes to 4-5th problems ,atleast I do not have any knowledge about the paradigms! Obviously they are better than me but Even I solve every problem related to the scope I have! Same is with everyone !

      I feel like there is something more than that :P

      Because I have been coding since one year and yet blue :P

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

        They can visualize problems better. They are insightful , and can code bug-free in their first attempt .

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

          Bug-free on the first attempt... I wish.

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

      Don't forget to mention: Even a green coder can solve Div2/A immediately after reading. The real difference is the complexity of the problem between that a red coder and a blue coder can code immediately. :D

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

        And I guess that comes through exposure to algorithms and problems..

        Practice and lot of practice!!

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

          Yes, I think practising improve the level of your immediately solving ability. :)

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

Ohhh, nice div1 registrants list ..

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

Where rooms?

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

There is guy who is printing "YES" or "NO" (in capital) in Bear and Poker . I tried to hack his solution and it gave me unsuccessful hacking attempt.Why? Its written in problem we have to print like this: "Yes" or "No".

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

    ?

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

      "yes" and "no "

      are usually case insensitive

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

      I think Codeforces treats "Yes" and "YES" same and vice versa for "NO".I read it somewhere in comments sometime ago .

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

        It's not that Codeforces treats them similarly. Round writers are advised (I think they are) to use the checker which is case-insensitive unless they have strong reasons to have case-sensitive output. And most of the times this checker is being used indeed so (mostly) it doesn't make sense to hack such solutions. It should have been clear today that hacking "YES" <-> "Yes" doesn't make any sense since participant's solution passed pretests which would never happen in case of case-sensitive checker.

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

    There might be some lee-way. The fact that the solution passed the pretests should have made it clear that your hack wasn't going to work though.

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

I guess you should be awarded for designing the first anti-tourist contest ever! at least till now!

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

    The first? Are you serious?

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

      Previous record was 24, now it is 168 :)

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

        and when he was ~20, rating decrease was about ~130.

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

      Of course he's serious, did you look at your own link? Notice how tourist's worst performance ever is 24th and he came 168th this round?

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

        Yes, but I think AliB's comment was posted before tourist fail D, maybe I'm wrong. Anyway, you're right.

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

not able to hack

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

dreamoon hacked my A. Feel so honored!

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

The problems are so nice, thanks for the contest!

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

I liked the problemset, but I've no idea how to solve Div1 D or E. Anyone want to share approaches?

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

I really like problems. Problem statements are clear. Even div2A required simple idea. Thank you

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

I really hate when someones solution has overflow but when you try to hack it , it passes your test but is wrong and should give overflow in this test.
UPD : 12760657 it didn't pass the full tests.

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

    Also some guy fooled me with #define Int long long, lol.

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

      You shouldn't be fooled if you know that Int is not int

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

      I wonder if this is a common thing. I always use "typedef long long Int" but I've never seen someone else do it, at least from the competitors in my country :P

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

Was this contest easy or my skills have improved ?

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

Couldn't hack (or fail) because of lags at the end :( Div1 A-C look quite easy compared to other rounds. Though I failed to implement C..

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

This is the first time I solved A,B,C and had half an hour left. Thanks for that!

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

    D (div-1B) was super easy too. I've implemented seg. tree, but when I looked at the other solutions, I realized how stupid I was =)

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

      Just curious. What's your seg tree logic? Please share. :)

      • »
        »
        »
        »
        2 years ago, # ^ |
        Rev. 5   Vote: I like it +5 Vote: I do not like it
        for (int i = 0; i < n; i++)
          b[i] = a[i] + i;
        for (int i = 0; i < n; i++)
          c[i] = a[i] + n - 1 - i;
        

        For example if a equals to {2, 1, 2, 1, 2} then b and c will be:

        {2, 1, 2, 1, 2}     {2, 1, 2, 1, 2}
        {0, 1, 2, 3, 4}     {4, 3, 2, 1, 0}
        _______________     _______________
        {2, 2, 4, 4, 6}     {6, 4, 4, 2, 2}
        
        

        Now let's build 2 segment trees using b and c to find minimum.

        It's easy to prove that:

        ans[i] = min(i + 1,
                     n - i,
                     a[i],
                     minimum(b, i + 1, n - 1) - i,
                     minimum(c, 0, i - 1) - n + 1 + i);
        

        And the result will be max(ans[i]).

        P. S. Yeah, I know, it's overkill ^_^

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

          Overkill or not, if it passes, its worth a try :)

          Actually, I don't see how your min(...) is so obvious. It took me hours to understand the problem setter's solution.

          edit: Instead of

          for (int i = 0; i < n; i++) c[i] = a[i] + n — 1 — i;

          why not just

          for (int i = 0; i < n; i++) c[i] = a[i] — i;

          ?

          And, min(...., tree(c,0,i-1) + i ,....).

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

    Check it again. Anyway Congrats.

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

      Yeah, my B failed :( . The pretests passed, and now I will debug it.

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

Am I wrong or there were no -50 points if you submit a solution that fails on a pretest from problem's sample tests in previous rounds?

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

I pressed submit when there are still 20 seconds left but didn't submit my code successfully....... So sad T_T

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

    Same here. I tried to submit my code when there were still 15 seconds left, but the submission page didn't load. I just checked that my code was correct.

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

    And that code get AC....

    Edit: It' problem E T_T

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

The problem set was commendable for me, especially the idea of problem C. Cheers!

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

I was a bit late submitting div1 A because I didn't believe that it's that easy(specially after div1 A of previous round) and I must be understanding it wrong or missing something , anyone had the same situation?

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

    I had similar situation with div2 A but the constraints were too low and I got through.

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

    Yes. I questioned myself for 1 min.

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

    My first thought was that it was made this way intentionally — after all those complains which we saw several days ago: "People can't solve A and they ignore contest, their rating doesn't change — and I am losing rating with solved A".

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

    Lol no, A's are almost always trivial x_0.

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

I was trying something like dfs to detect 3 member cycles for Div2-B and finally the flat O(n^3) got AC Suffered 3 WA and around 1.5 hours :(.

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

So is this the first time tourist gets a three digit rank?

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

    I did beat tourist with 6 points!

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

      Tourist doesn't always win every CF round.

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

        But I have only done competitive programming for 9 months, let me be happy :(

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

          I've been coding much longer than that, and I am still green. You are a legend by my parameters :)

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

        I said it's the first time he got a 3 digit rank.

        Please read the question er... comment carefully.

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

      You should be careful now, who knows what tourist does with those who beat him...

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

      Probability of that you can beat tourist in next round is very low

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

        It wouldn't be special if the chance were high.

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

    Well, he gave 167 people a contest to remember.

    Thank you tourist!

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

Can anyone please tell why my submission is giving runtime error? It is working fine on my local ide.

Submission link : http://codeforces.com/contest/574/submission/12757848

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

I was so glad by fast solving Div1A (3 minutes), but in result couldn't solve Div1B, though it is not much harder than Div1A:D
But really nice problems. Thanks!

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

What a contest? Tourist gets 3 digit rank, Petr only with 2 correct submissions until 1hr 45min. Kudos to the problem setter. PS: My personal opinion on the problem set is that it was very good. Since C was easy nobody would have ditched contest as a result of not solving any of them.

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

Some O(qn) solutions passed Div1 D, and one O(n2) solution passed Div1 E. I think more tight time limits for those problems are necessary.

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

    In D we didn't see any O(nq) with low constant factor and we wanted to pass (some solution with bitmasks).

    For E we had a O(n2) solution with many tricks to speed it up and it was still far from AC.

    Two big mistakes :/

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

That was a wonderful round. Fast Editorial and nice problem set.

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

Can problem B div.1 solve by divide and conquer too?

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

    I was thinking the same. Since the structure can be split on the shortest tower, given its height is less than its distance from the boundary, it looks like a D&Q problem.

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

I hope rating update is as fast as system test and editorial

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

maybe problemset was good but there is a big differece between a — b,c and d — e div 1.

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

Hi,

Div2 B

can anyone tell me what's wrong with this solution? http://codeforces.com/contest/574/submission/12750750

Edit: one of my friends told me the problem... Using set.lower_bound() to search can lead to set.end() as the result which when I compare to a number can lead to false result. http://codeforces.com/contest/574/submission/12769046

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

I didn't like having to help a bear politician cheat in div 2 Problem A.

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

    I don't think that's something our mortal minds can comprehend.

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

    I guess he really is a machine like his username says.

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

    It's clearly a brute-force, but seems to be incredibly sped up. The first trick is alignment of the variables in memory (some variables are told to be aligned to 16-byte blocks) — it probably helps cache do its work more efficiently (less cache misses and so on).

    The magic part (inner loop) uses SSE (set of processor instructions which allows many operations to be done at once; why do 100 000 32-bit additions/shifts/comparisons when we can use 128-bit SSE registers to do only 25 000 operations?). You can probably decode what it does here. I guess one can write a simple brute-force and then "encode it" in terms of SSE.

    Still, a question to the author: have you worked for a CPU/GPU manufacturer?

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

      Is there a similar way to exploit SSE in Codeforces for other languages (I'm particularly interested in Java)?

      How much faster would C++ be compared to other languages for this problem?

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

        In my opinion, in Java SSE intrinsics make no sense (Java source code is compiled to Java bytecode which is then run by Java Virtual Machine; you have no access to JVM code, so you cannot optimize it by hand — for example using SSE code).

        I have no idea how other languages compare to C/C++. However, the fact is that many of them may lack support for the intrinsics and thus we won't be able to control the power of SSE.

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

      Actually alignment is required for SSE instructions to work.

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

      Thank you for your explanation. In addition, I think those techniques are not needed if our submission runs on 64-bit systems.

      I have not worked for a processor manufacturer, but I have a bit of experience of performance tuning on CPUs and GPUs.

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

Did author suppose that local optimization should pass in E?

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

It seems that the test data of E is really weak and should be fixed.

This obviously wrong solution of cubelover passed 41 out of 42 tests, and the 42nd test is so small that it could be solved in O(2NN). (maybe it was added during the contest..?) He got accepted with the same solution with some minor modifications.

You can find more obviously wrong solutions which got accepted after the contest..

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

    One specific example from cubelover:

    This solution from Marcin_smu gets wrong answer for this test:

    3
    -1 -3 3
    

    The optimal answer is obviously  - 1 × 1 + 3 × 2 = 5, but it prints 3.

    This simple test could have been made even using a random generator!

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

I hate to wait for rate; but it's late and it's my fate.

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

It seems that in problem C there are no tests with maximal degree 3 and answer NO: 12766417

But such test exists and is quite simple.

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

will i go with rank 108 div1?

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

    1689 not 1700 :(((((((((((((((((((((((( ;_; OH NO

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

Finally red!

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

    I know that feeling :)

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

    And at the same time a better rank than tourist , enjoy the moment :)

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

    So you joined quite recently and have become very good quite fast, could you give some background on yourself, like what age you are and so on? You obviously practice a ton, have so many solved problems having joined only 9 months ago. Anyway it is pretty inspiring to me what a lot of practice in a short amount of time can do.

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

      I'm old, I started when I was working on my masters thesis in maths since I realized that I weren't really qualified for any jobs and I didn't want to do research. But at least it shows that it is never too late to start programming!

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

Why the problemset and the gym are still blocked?

UPD working now.

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

Really nice problemset! Natural and short (but yet original) problems which were really fun to solve or interesting to know the solution :) Thumbs up!

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

Master again.

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

In future (t-shirt giving) contests, we could state that there will be t-shirts for div2 after the contest, in that way, there won't be div 1 people here, and div 2 guys can also have a chance to win t-shirts.

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

Мне кажется что это хитроумный план tourist-а, залажать на контесте. Что бы все снова начали о нем говорить, а то теперь когда он выигрывает никто не удивляется(он же Гена).

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

I tried to hack a solution of the problem C. It showed invalid input. Can someone help? Link: http://codeforces.com/contest/574/hacks/164504/test

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

    You print endl before the last number, instead of after it...

    For example, if n was 5, your code would produce:

    5
    1 2 3 4
    5
    
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh thanks! But I tried using endl in the end also and still got Invalid input. Can you show me the code, how it should be?