RCC 2014 Warmup
By andrewzta, 11 years ago, translation, In English

Russian Code Cup is a competition organized by Mail.Ru Group for Russian-speaking programmers. This year the competition will run for the fourth time to gather top 50 to great finals in Moscow in October.

Though Russian Code Cup is open only for those who speak Russian, the team that is working on problems for Russian Code Cup has decided to make a present to all CodeForces users and set up an extra round for everyone.

The round will be held on April 17 at 19-30 Moscow time. The round will be open for everyone and will have both div-1 and div-2 tasks. It will use standard CodeForces rules. The writer of most problems is Aksenov239 — author of many Russian Code Cup problems.

We wish all participants good luck and see you on Thursday at http://mirror.codeforces.com

UPD: Score for problems: Div1: 500-1000-1500-2500-2500, Div2: 500-1000-1500-2000-2500. Good luck!

Announcement of RCC 2014 Warmup (Div. 2)
Announcement of RCC 2014 Warmup (Div. 1)
  • Vote: I like it
  • +244
  • Vote: I do not like it

Comments Comments (125)
| Write comment?
»
11 years ago, # |
  Vote: I like it +15 Vote: I do not like it

will the round be rated?

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

"Though Russian Code Cup is open only for those who speak Russian" will the problem be translated in English??... Can the one that can't speak Russian take part in it?

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

    The Russian Code Cup itself is in Russian, it will not be translated.

    RCC Warmup round will be like ordinary CodeForces round (just "sponsored" by Russian Code Cup), so it will have statements in both Russian and English. Sorry if there is any confusion.

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

are the problem's difficulties as usual rounds?

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

    Hard to say. No special attempts to make problems easier or harder were made, however you can never tell ;).

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

will the round be rated for every codeforces members or only for Russian participants??

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

    i think for every one

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

    Strange idea. This would probably only increase the amount of fake "Russian" accounts.

    CF rounds are always rated for anyone in the division for which the round is.

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

    This round will be like usual CodeForces round. If it will have statements in both languages, I think it will be rated for everyone.

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

Great start!

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

Good Luck everyone! Hope that the website wont be down again during the contest.

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

delay for ten minutes?

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

    yea!

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

    While we are at it, shouldn't it be "Codeforces is temporarily unavailable" instead of "Codeforces is temporary unavailable"?

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

Those hacks in B! I did a bitmask dp with complexity O(N * 2^M) as did many, I believe. Is there some very tricky case or is the time limit strict?

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

    I think this is trick here: You won't need to ask more than 20 friends to help you.

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

      Ah, this wasn't my mistake. I wasn't properly computing my new dp values. I fixed it now — 6396342 :D

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

    I hacked 2 people who did not sort friends by the number of required monitors

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

      I missed this trick , Learned a nice trick (i am almost a newbie :p)

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

For Div1 problem B, it was very tricky that INF=1e18 isn't enough. I resubmitted because of this, and made 4 successful hacks.

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

    i think you mean div 1 B not C . you can make INF = the worst Case better than certain value :)

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

I think the problems were harder than usual.

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

Can't Div.2 Problem A give some explanation about sample tests?! Total inapprehension.

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

    Yeah, I was confused with the problem in the beginning!

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

    I agree, I'm totally confused with Div2 problem A and problem B description.

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

    statement was horrible... :/

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

sorry, my mistake, yeputons find differ between tasks.

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

    It's interesting how many people have seen this problem before.

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

    I misread, please ignore.

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

      would be able to fill a rectangular table N × M with squares of different positive integers in such a way,

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

Problems were very interesting...!!! Thanks for this Round.

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

Can anybode tell me, how could it get TL?!

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

    cout. Write ios_base::sync_with_stdio(0) or use printf.

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

      I've solved over 100 problems using cout, but solutions work with such restrictions. And endl also hadn't create problems.

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

      I used ios_base::sync_with_stdio(0) and still got TLE : http://mirror.codeforces.com/contest/418/submission/6387665

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

        Too many arithmetics at each iteration :) I think — division costs so much.

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

        Use this:

        ios_base::sync_with_stdio(false); cin.tie(NULL);
#define endl '\n'

        Also, on MSVC ios_base::sync_with_stdio(false); doesn't actually do anything.

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

          (y) hmm... just changing endl to '\n' passes in 530 ms. Flushing problems — slows the output!

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

    10^6 numbers : large output, same with me : should have used printf.

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

    I think it's beaucase you use endl.

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

For Div1 A: Outputting 10^6 numbers using cout with ios_base::sync_with_stdio(0) caused TLE :/ (also there was no large output warning).

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

    strange I have used cout and endl and my solution passed.

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

      998 ms!!! also using '\n' in place of endl halves time because flushing happens only once.

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

Wow, so are time limit failures on problem A (div 1) something you were aiming for? While it's obviously good to remember that iostream is slow, you probably should have used different input bounds for that problem (or different time limit). There was enough room for hacking in that problem anyway, so TL-trick seems to be an overkill. Besides, in one of the previous D2 contests CF used to mention that "I/O size is too big for iostream, so don't use it".

Just my opinion (of a person that got burned on this).

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

    Ya, CF gives large input/output warning in such scenarios : so I didn't bother using cout with ios_base::sync_with_stdio(0) (and got TLE!) which seems to be as fast as printf in many scenarios : it must be only 1.2-1.5 times slower than printf anyways.

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

Why no explanations to the sample cases? Some of the wording was more than a little confusing (not that I'm complaining with my hacks), and I suspect some people failed because of it.

Also Div2C/Div1A really should have the "large printing" warning — there's no point to having people who solved the problem TLE because printing is too computationally expensive. That makes it not a programming problem anymore but just semantics about syntax, which (at least in my opinion) does not a good problem make.

Also it seems like it is almost impossible to pass with Java — only one person managed it with Java 6 and not many more with later versions. Just a very bad problem.

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

    Also it seems like it is almost impossible to pass with Java — only one person managed it with Java 6 and not many more with later versions. Just a very bad problem.

    So, you've made a real application, and have sold it to a customer. The customer soon responds back: "On big inputs your program is too slow, while your competitors' solutions don't have a problem... Can you fix your program?"

    And you reply: "No, my program is fine, increase your time limits instead and ignore better solutions."

    Does this sound plausible? If you choose to write in language X, you have to know and accept its advantages and disadvantages. It is your choice to use this language, and so you can't complain if its disadvantages bite you back.

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

      I'm not sure which solution of mine accidentally became Java, but I was unaware that I still use this language for Codeforces. Thank you for correcting me. I will be sure to take Java's disadvantages into account when coding in C++.

      The issue with this problem stems not from the fact that a slow solution is not passing. The issue is that, despite the fact that the contestant is really solving the problem, different methods of printing result in wildly different verdicts. Besides the precedent of specifying not to use cin when this is a possibility, this is just a terrible problem from an algorithmic standpoint. What is the purpose of a problem that is all about choosing the correct printing method? Perhaps it's good as a homework problem, but it has no place whatsoever in a contest. Especially since some languages just can't do it (and Java is not exactly an obscure language...) under typical circumstances.

      Anyway, there is a profound difference between industry coding and recreational coding. Pick any nontrivial problem, and pick a random solution. Is this code you want to see in production? Of course not. With some exceptions, the formatting will likely be difficult, there is likely to be silly hacks to get around issues rather than writing clean code (as there should be with time constraints), but most importantly you probably need to take a long time to figure out what the code is doing. When was the last time you saw a solution with proper documentation, abundance of comments, and written for readability, accessibility, and evolvability? So the objection "this code wouldn't be good in industry" is a stupid one — no contest code would be good in industry (if it is, you're probably not doing contests right!).

      I'm not sure whether you work in the coding industry, but when was the last time you considered runtime as a serious factor? Besides not doing something insanely stupid like making a code O(N^8), there just isn't a great need to. Sure, several algorithms are useful, but implementing complicated things to avoid a logarithmic factor is silly. And anyway, code should not be elegant or clever — it should be readable and understandable. If you see

      // to convert prefix to postfix
main() {
  char c = getchar();
  (c == '+' || c == '-' || c == '*' || c == '/') ? main(), main() : 0;
  putchar(c);
}

      in somebody's code, even though this is some pretty damn cool code that person should be out of a job quickly. It's not worth the headache that someone else is going to have when trying to edit this code a few years down the road.

      I suppose we'll agree to disagree, but I think a good contest problem is one that provokes thought, has a nice solution, and gives that "aha!" moment when you solve it (perhaps because of my math background where an inelegant problem is considered a huge disappointment, not a good exercise). This particular problem satisfies exactly 0 of these criteria. Ok, maybe you have to think a moment to realize you can just connect a vertex to the k nearest clockwise ones, and maybe another moment to prove it if you're so inclined. But there's nothing interesting about the problem, and it's not one of those problems that you recognize a week later as "oh, I remember that problem! That was a nice one" (assuming you remember it at all, which this problem doesn't give much reason too). It's just not a good contest problem. A good homework exercise in the speed differences between output, but not a good contest problem.

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

        Did not want to edit such a long post. I want to clarify that I don't mean anything against the authors of the problems. Writing good contest problems is very hard, and ensuring they are more or less new (or at least not recently used) is just as hard (for example this problem from a month ago is extremely similar to this C). Anyone who goes through this self-inflicted pain is to be commended regardless of the end result. Bad problems happen, and when they do all we can do is give as constructive criticism as we can and move on.

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

    I had an interesting situation yesterday. I solved this problem in my favourite language — PERL. I sent submition and it passed pretests. Later I thought that Perl may be too slow to AC, and it was easy to translate Perl code to Pascal. So I did. And then I skipped my Perl submision, and sent Pascal's. At final tests I have TLE. But later I tried to send my Perl's program and it passed through 342 ms (6392774). So sad I was! But I was surprised, that Perl can do this!! My Pascal submision used up to 1000 * 499 iterations each having 2 "write", but later I joined to 1 "write" and passed in 826 ms. Why Perl hadn't TLE? I used array to push here my results, and later I asked to print whole array. Another succesfull variant was to make empty string, and add to it ("push back") answers, and later — ask to print this line (or so called "multiline") — 6395984 857 ms.

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

Div.2: Why not 1000-1000-500-2000-2500 ? I joined to contest when less than an hour left, and solved only C. Statistics said to me to try to do so.

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

For D-Div1 I thought of 2 segment trees that you hold while you are decending in a rooted tree. Of course , I have to find the LCA in log(N) and the point that is at the middle distance between two nodes ( also log(N) ). It's quite complicated because is a lot to implement.

What would be a simpler way to solve D ?

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

Worst English statements Ever!

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

When can we see our new rates? When is the system test going to end? Anybody knows?

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

Div.2C I used cout instead of printf, and it turned out to be TLE. So sad!

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

Hundreds of solutions failed because of one fucking endl.

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

    And hopefully hundreds of authors learned to use '\n' or "\n" instead of endl next time.

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

    Fortunately I passed Pro.C(Div.2) by a fluke with 997ms using endl.

    6390244

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

    I don't understand why my solution passed 1000 499 and failed on 999 499. http://mirror.codeforces.com/contest/418/submission/6386127

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

      On 1000 499 your program took 966 ms. Not surprising that another similar case would take over a second, it's just random variance.

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

        But it should be strictly less, shouldn't it? The latter case will have less iterations. If this is random variance, then this problem was a mistake on the part of problem setters.

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

          Suppose that with probability 95% the 999 case will execute in time from 949 to 1049 milliseconds, and the 1000 case — in time from 950 to 1050 milliseconds. Still this doesn't forbid the first case from executing in 1040 ms and failing, and the second case in 980 ms and succeeding.

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

      I don't know. But maybe division by 999 is slower than by 1000?

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

The problem http://vn.spoj.com/problems/VMQTREE/ was similar to the Div. 1 D problem today, except the 50000-limit and the multiple-tests. Sorry, because I don't have the English statement.

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

    We haven't known that.

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

      Can you explain why in problem E you used pashka solution as reference one, but only set TL about 16% over its runtime? What wrong solution you tried to fail with such tiny margin?

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

        Sorry for late answer.

        Because there is normal solution, which is passing in the half tl, and for this one we haven't normal proof about asymptotics. Because of that we have added special test at which pashka's solution isn't working well. This is the same test at which you have failed. But it have passed because of the buben-constant and I wanted to make my solution to pass half tl.

        And it was so pity, that your solution haven't passed, because this contest could have been the "best" contest.

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

          But you had not answered second part of my question — what solution had you tried to fail? Also you either want approach to pass — and that means setting tl at least 2x of the approach runtime — or you want it to fail — and that means setting tl several times under this approach. You did neither here

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

            I wanted that the solution, that you have sent, could pass only with some buben-optimization. I can fail pashka solution too, if I manage against some constant. Really, pashka's solution don't pass. I don't know, why you know background information.

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

              Well, I can prove my solution's runtime. It is worse than yours by factor sqrt of log. But now lets look at c++. Do you think my solution rewritten in c++ would not pass?

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

                Probably it can, you can check it. I don't think, that it can be much faster because of memory.

                And sqrt(logn) gives you x4 slower solution. And it's big difference.

                I think, that this is my fault that tl isn't so clear, but as a result the solution with wrong asymptotics haven't passed. I think, you can agree with my last statement, that wrong asymptotics shouldn't pass. And here you have written solution on your own risk.

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

                  I do not believe anyone within one's mind would try to differentiate solutions with factor of 4 because just so much depends on implementation. I do not believe you wanted to and I do not believe you are sincere when you say that you are glad you did. I do believe whole contest has poorly set time limits

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

                  Maybe you are right, maybe I'm wrong. But we haven't asymptotics for this solution. That's why we aren't consider this solution to easily pass tl.

                  My sincere apologize, but your solution has wrong asymptotics, and really I can't see the problem. If somebody have solved this problem with the same solution, we could have considered to change tl.

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

                  Because I believe given existence of solution with runtime of 3 s one need to either set tl at least 6 s or at most 1.5 s (and while we are at it I do not like tls of less than 2 s at all — if you do not want to clog judge queue use multitest)

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

    I was tester of that problem. I'm so sad that I forgot about this match and skipped it :(

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

Too weak pretests. TopCoder level weakness, except there we at least see those tests.

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

I can't believe I got 3 'Failed System Test'! My experience in contest: Always use printf :(

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

dont you think its unfair? For Problem C Div 2* half of the people who get pretest passed got time limit for not using something like printf!!!! please for next times mention that we should use! (sorry for bad English)

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

    I think you are talking about Problem C Div 2 and not Div 1

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

Is there anyone else, who got AC on Div1 C using random :P? http://mirror.codeforces.com/contest/418/submission/6394595 (corrected link) So bad, that I couldn't make it during a contest, because my solution got TLE on case 2 1 ; / (but not on 1 2 :P).

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

    I used random in Div1 C to generate two rows of length n and m.

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

      But if you got that it suffices to generate two rows of that length you have already solved 90% of problem :P. So it doesn't count :D. I tried to find solution of form

      aaaaaaab

      cccccccd

      eeeeeeef

      ... and fortunately solution of that form always exists :P (at least for n, m <= 100 :D)

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

        Yeah I checked that too during the contest but was not able to continue XD. how do you use that fact?

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

          Just generate some rows of that form which fit, start from any initial position and change one randomly chosen row from actual candidate to solution into another randomly chosen one from all generated rows till you got a solution. Also you can look at my code.

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

    Can you explain a bit your idea , please ?

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

    I took 4 random numbers in range from 1 to 100 and put them like this:

    x x x x x y
x x x x x y
x x x x x y
z z z z z t

    202 ms

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

      Wow, solution without any deeper thoughts and it works :D! Great!

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

      but why does that work?! i tried to prove but couldn't, please explain a little more.

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

      Actually it does not work :D. "50 68" is a counterexample. Even if solution exists my computer says that it will get TLE :P.

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

        Oops =)

        However, such a solution does not exist for this test and some others: 

        { 50, 68 }, { 50, 72 }, { 50, 83 }, { 50, 84 }, { 50, 87 }, { 50, 90 } 
{ 82, 68 }, { 82, 72 }, { 82, 80 }, { 82, 83 }, { 82, 84 }, { 82, 87 }

        But if change the upper limit to 120, it will be for any input.

        In fact, we can just iterate over these 4 numbers. With the limit of 120 it gets AC in 15 ms

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

          I iterate over all 4 numbers and got Accepted
          First I think testcases are too weak but I don't now is that fair or not.
          Second why if the limit is 120 this solution is valid for any input ?
          cout<<"Thanks"<<endl;

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

            I don't know if solution of that form exists for any input, but I'm pretty sure that setting limit to some constant won't be sufficient for arbitrarily large input. And why 120 works for n,m<=100? Because you can simply check it for all valid inputs :P. I doubt that there is a nice proof of that fact.

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

just cout<<endl nd cout<<"\n" being the reason for AC nd Tle is not justified. Not at all.

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

Give this comment '+' if you want the contest be unrated. Give this comment '-' if you want the contest be rated.

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

TLE in Div 2 problem C with cout , AC after the contest with printf -_-

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

    Me too :(

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

    cout's normal behavior is to sync with C's stdout stream. Put this as main()'s first instruction: ios_base::sync_with_stdio(false); You should expect a major io improvement.

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

In problem C of div 1, we only want to find two matrices: A[m..1], B[1..n] and the result will be A x B and matrices A, B such that sum of square of all its elements are also a square. But we know that: 169 can be express as sum of k square number with 1 <= k <= 155, so the given problem can be solved straight forward. This is my code:

http://mirror.codeforces.com/contest/417/submission/6395366

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

Div1 A / Div2 C can be used to compare time taken by different print statements.

Time taken on my solution —
1. Using cout and endl 998ms :)
2. Using cout and "\n" 265ms
3. Using cout and '\n' 202ms
4. Using printf 296ms (strange?)

Can anyone explain why 3 is faster than 2?

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

    Because printf("%d", x); has to parse the format string each time, and cout << x; already knows at compile time what should it print, cout in theory should be faster than printf. And it seems that in this case it is not only in theory, but also in practice.

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

    I think 3 is faster because interpretation of one sign takes less operations, than interpretation of string, contains one sign.

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

My solution for Problem C got TLE on Test Case 40(solution id: 6392630) during system testing and after the contest I submitted the same code, it passed Test Case 40(solution id: 6395155). After some time, I submitted it again and it got TLE on test case 34 (solution id:6395832) which it had passed on previous two submissions. Don't know what's wrong??

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

plz explain how to solve problem D of div 2 .

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

    The number of problems were only 20, so we can ask what is the min cost for a given subset of problems. To do so, sort the persons offering services in decreasing order of monitors demanded and for each one of them run a subset-sum type loop update for each subset 0 ... 1<<m -1. This ensures that subsequent updates to a set from a subset has fewer monitors and hence does not include the cost of monitors, only the extra cost x. Include the base case of monitors cost + x for subsets covered by single persons and you are done. Time Complexity : O(n * 2^m)

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

Sad situation in problem C div2. This shouldn't happen again. -_-

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

was it only me or did anyone else have difficulty understanding the very first question? I thought the no of problems was 2 for this case

1 10

7 2

1

because 1 problem for main round and another problem for additional round.

for this

2 2

2 1

2

no need of problems, all the past finals winners will proceed.

So, my assumption was there can be three cases 0, 1 or 2. Can anyone explain what the question is really asking? I appreciate it.

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

    think like this:

    • the number of winners from rounds is at least equal n*m-k, and

    • if he decide to have i main rounds and j additional rounds, then total problems is c*i+d*j and total winners from rounds is n*i+j, and

    • the question asks you to print the smallest value of (c*i+d*j) that satisfies n*i+j>=n*m-k :)

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

tourist had so much luck in this contest :P! Egor on 2nd place got TLE on E, because TL was very tight and flashmt on also 2nd place got TLE on A, because of endl's instead of \n and they will easily win if it weren't for those unlucky TLEs!

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

Horrible problem statement. Could not understand A and B of Div2.

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

Problem A,B and C is too week in data

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

The problems is nice,I find many bugs in my code,although I have passed the pretest

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

Getting WA in case 11 in DIV2 number B problem :( :( Can any one provide me a small test case for which i will get WA? Here is my code.6398585

→ Reply