Furko's blog

Codeforces Round #186 (Div. 2)
By Furko, 12 years ago, translation, In English

Hello everyone!

Codeforces Round #186 (Div. 2) will take place on Thursday, May 30th at 19:30 MSK. This is my first Codeforces Round and I hope that everyone will enjoy this round.

I would like to thank Gerald for helping me prepare this round. Special thanks to Delinur for translation of all problem statements into English.

Problems point values today is: 500-1000-1500-2500-2500

Good luck & have fun! :)

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

Comments Comments (147)
| Write comment?
»
12 years ago, # |
← Rev. 2   Vote: I like it -117 Vote: I do not like it

I hope that the contest will be rated.

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

    This is not your problem!

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

    That's why you have to respect this simple rule : "You may edit your comment only for fixing grammar mistakes or small changes. Do not change the main idea of your comment."

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

Fast announcement.

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

hope this round be successful

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

Let's get ready for fun!

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

Lets just hope this contest goes fine and rated. :)

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

Wish this contest will be rated. BTW thanks for early announcement. :)

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

Oh MY god!!!I have taken part in three CF round...But I am unrated now(Because all of those three round have something wrong...)= =...SO I don't want to miss this one ....But ..At 23:30 on Thursday, I will on the train to Chengdu to take part in a invitation match.....WTF....Who can help me!!!!!

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

    let me play for you. :D

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

    This is life.

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

    What kind of help do you expect?

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

      I need a laptop when I am on the train.... and a wifi....Although I usually write code on the cellphone by c4droid and submit by chrome....But...as you know, it's not convenient...

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

    So...please the judge system good luck and don't have fun ....please this round can be rated....I want to be rated!!

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

I hope everything will be ok this round.

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

For Furko its his first codeforces round and i hope that it will be very easy or very hard :)))

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

THIS IS MY FIRST CONTEST IN CODEFORCES ....WISH ME GOOD LUCK T-T

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

    Good luck.

    P.S: Your Captain Obvious

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

Thinks for this round.I'm so glad it's coming soon.

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

hopefully this round will be successful! good luck everybody! :)

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

This is going be heavy loaded contest. 2177 and still counts.

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

    Not so "heavy" loaded. April fools day contest has 3200 registered user, and #175 has just a little more than 3000.

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

      Don't forget it's just Div2 contest. I think many Div1 coders will not participate in it.

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

        175 is also a div2-only contest :D.

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

          Ok. I'm not saying, that contest is going to be the most busiest :)

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

After hard Chinese problems, I think easier European.

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

Gl && hF

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

This is the most unlucky hacking attempt, isn't it? :(

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

wasted so much time trying to find out why my brute force solution didn't work for the second problem when a very easy dp implenetation I made in the end passed all the pretests... yet another bad contest for me :(

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

how solve problem D?

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

    I was going to ask the same question!

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

    dp[i][j] = minimum cost to repair j holes from the first i holes Complexity: O(N^3)

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

      how do steps?

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

        Try every i <= k < N, dp[k+1][new_j] = min(dp[k+1][new_j], dp[i][j] + minCost(i, k)). minCost(i, j) can be precalculated in O(N^3).

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

          How to precalc minCost(i, j)?

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

            You take all the intervals from the input and then do something similar to Floyd–Warshall.

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

              The floyd-warshall part is not necessary.

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

                Hey, do you have cerealguy's permission to use his photo? :)

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

                  I didn't know there was already a cereal guy here when I chose this pic.

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

                  You have my permission.

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

                  there are some minor differences, size of head and also bowl or even the table !

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

            first of all, each cost[i,j]=INF.

            for each l,r,c you get, cost[l,r]=min{ cost[l,r] , c }

            then cost[i,j]= min{ cost[i,j] , cost[i-1,j] , cost[i,j+1] }

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

          Uhn!Could you explain what is the meaning of the recursion formula and the 'minCost(i,k)'?

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

            You have currently decided what to d with the first i holes. You repaired j from them. You try to repair every interval (i,k), i <= k < N. The cost to repair this interval is minCost(i, k) which is precalculated. You end up at dp[k+1][new_j] because you have already decided what to do with the first k+1 holes and you repaired some additional holes. Also, you can decide not to do anything at this hole (go to dp[i+1][j]).

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

    dp[i][j] = minimum cost for fixing j holes out of first i holes.

    dp[i][j] = min(seg.cost + dp[i-seg.size][j-seg.size]

    where seg = {l,r,c} and all seg.r == j

    I didn't submit as I was a minute late, but I believe it to be correct.

    UPD: Nah, not correct logic, small modification required to it.

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

      My idea is the same as yours but got wrong answer on pretest4.In fact,we won't fix a hole more than one time. try this test: 3 2 3 1 2 1 2 3 2

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

    This is my idea but my code wasn't right for samples: First I define dp[i][j][k] = minimum const to fix at least k holes in j first holes using first i companies. while companies are sorted by their right points. And the update: dp[i][j][k] = min (dp[i — 1][j][k], dp[i — 1][j — (j — company[i].left + 1)][k — (j — company[i].left)] + company[i].cost)

    I saw that the difference between second and third dimensions of dp is always the same, so I omitted third dimension. And so this dp is my solution: dp[i][j] = minimum cost to fix at least j — n + k holes in first j holes using first i companies while companies are sorted.

    Is this solution right ? :-?

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

I hope tests for problem C are good enough to fail Java solutions which use Arrays.sort().

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

    Such test are included to pretests.

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

      Yeah. I couldn't pass test 11 on Java. I finally pass them, when rewrite solution to C++

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

      Thanks for trying to include that test, but my solution passed pretests just to time out on test 48 (Is that a hack input?).

      I guess it is my fault to keep forgetting not to use Arrays.sort() on arrays of primitives

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

        I add shaffle to my solution in Java and get TL too. Probably we need to read input data faster

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

    I think it's 100% unfair. Quick-sort is the same for every language, Java probably have more overhead, but again — I think it's unfair.

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

      Shaffle array before sort it in Java.

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

        Ok. I got it, it looks like tests are written to kill exactly Java implementation of quicksort. Good job!

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

      The default way of sorting things is not the same in every language. Modern compilers (GCC, Python, .NET starting from version 4.5, Java when sorting objects) tend to use worst-case algorithms, mostly Introsort and Timsort. However, in Java, integer sorting still uses double-pivot quicksort which is O(n2) in the worst case.

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

        So, is it way to fix it? Write your own sort?

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

          Randomly swap some items of array. And after that u can use Arrays.sort()

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

            You may want to know about Collections.shuffle routine.

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

              Yeah, according to javadoc — Collections.shuffle runs in linear time. So it's a good solution. Thanks

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

          Or, box int-s into Integer-s and use an object sorting routine (Collections.sort?). It may be slower though in the general case.

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

            Funny stuff. I shaffle my List, but get TL again in practice.

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

      submit in java 7

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

    http://docs.oracle.com/javase/6/docs/api/java/util/Arrays.html#sort(int[])

    The sorting algorithm used in Java for Arrays.sort(int[] arr) is tuned quicksort which offers very good average case performance.

    Many contestants used Arrays.sort() today for problem C and have passed System tests. I think if the solution fails, the problem lies elsewhere.

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

      My solution was using Arrays.sort() and failed pretests with TLE.

      The same solution is passing after these changes: - Use FastScanner implementation by martinezgjuan (which uses BufferedReader + StringTokenizer). - Use Java 7 (not Java 6)

      Now is passing with worst running time 951ms (no need to shuffle the array).

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

        Java 7 also uses quicksort, it's just your luck that nobody has made anti-java-7-hack.

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

I am really curious about what the pretest 4 of problem D is.

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

that was a great contest after ... :)

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

May someone introduce the intended method for Problem E ?

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

anybody knows why system testing is taking very long time today??

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

    Big number of testcases for problem C, I guess. Also, contest is merged for both divisions, so there is a lot of participants => solutions to judge

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

    and a lot of submit in contest

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

    Ask messi. He is best ;)
    EDIT : I thought there are more FC Barca fans than others in CF and I'll get pluses. 8)

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

Problem D is really beautiful, solving it was tons of fun!!

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

O(N3 + M) on problem D got me TLE :(

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

    It's funny. My O(N^4) passed.

    Sometimes the speedy inner loop is more important than the asymptote. I wrote carefully to eliminate 31/32 of the transitions in the dp without computing them.

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

    haidora1, I think that the cycles

    for(int n = 1 ; n <= N ; n++){
for(int k = 1 ; k <= n ; k++){
for(int i = 0 ; i < f[n].size() ; i++){
for(int h = n ; h >= 0 ; h--){
...

    if f[N].size ~ M , give you O(N3 + MN2) .

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

TLE-SOLUTION passed solution why the second solution passed and the first one get TLE

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

Wow, so many AC for problem C which pass with execution time of exactly 2000 ms, which is the TL for that task. Ofcourse on the other hand some codes definitely fail by only a few ms in this case. Now I wonder — is the TL set a little too low and hence might reject some codes with TLE even with the correct idea/implementation of solution OR is the TL a bit too high and that's why it lets some weaker codes pass that actually shouldn't?

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

    The Time limit is enough, those codes probably used slow input methods

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

unrated?

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

So, what is the point for CodeForces to support several languages as they do if you will have problems that cannot even run within the time limits using that language, regardless of how efficient you do it. You may have the exact same code in Python and Java, but you get TLE in Python (The same happens sometimes with Java and C++). Then, why support Python? Why don't you just get serious and support languages in which problems can be done like in TopCoder? Or just increment the time limit for certain languages, whatever you feel more confortable with. That would be a lot easier for contestants! In my opinion, it is NOT fair to get a problem wrong when the algorithm is identical to others who got it right, being the code language the only differentiator.

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

    Can't agree more. The same algorithm runs in time if coded in C++, but in python it gets TLE. This happened in problem C for many Contestants.

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

    Python is easier to write correct code in than C++.

    The syntax is simpler, the edge case and corners are less likely to cause you trouble, the array bounds are checked so that errors show up right away, debugging and tooling is better, Python has a repl so you aren't always compiling-testing-compiling-timing just to try an idea, and you don't have to worry about static type declarations. C++ is a pain with cruft from legacy implementations, the syntax is verbose and cryptic, the template system is full of hidden troubles waiting to bite during a contest, and even the compiler error messages are indecipherable.

    But C++ runs about ten times faster than Python.

    So there are advantages and disadvantages to both. You are allowed to switch languages between problems. You can even pick your algorithm and then choose your language for each problem based on speed and convenience.

    Being able to choose wisely is part of competing here.

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

      I have to disagree with you there. I know Python have a lot advantages over C++ in terms of readability, testing and debugging; that's the main reason I code in Python rather than C++, or even Java that I use as my second choice.

      I believe it can be challenging enough to come up with an algorithm that works for a particular problem and also have a quite good and reasonable complexity. So, why would my solution be wrong when is as good as yours?

      I can see how almost every C++ coder codes everything in C++, but you can say that you have to "choose wisely" your code language for a particular problem, when even the easiest problem you already code it in C++. So, when do you actually choose? I believe that is not the reason.

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

      I think the main issue here is that it was not possible to get AC in Python with any solution. While I understand that you have to think about efficiency twice in python (sometimes naïve code gets accepted only in C++ while in other languages you have to think of smarter solutions), I still consider that the most important ability to learn in these competitions is algorithmic skill, not language syntaxes or quirks.

      In my opinion, is better if, for these kind of problems, Codeforces won't accept Python to avoid the misleading information that is possible to solve the problem with Python.

      In short, we (at least me) are not here to learn the syntax and tools of languages, we are here because we would like to solve algorithmically challenging problems.

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

      I think the constraints were not very well checked for the problem C. My code in Java barely passed the tests (1880ms) by even using fast custom made I/O routines and with an O(n lg n) algorithm. Had I not used the fast I/O library my code would have easily failed. And Java is not even one of the slowest languages supported. So either time limits should be loosen up a bit and maybe also increase the input constraints so algorithmically worse solutions fail even in C++.

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

        I don't think so. This for loop might be the reason why the code is slow. for(int i=1; i<=n; i=4*i){ for(int j=0; j<i;j++){ total+= nums.get(j); } }

        There are ways to do the for loop in a single pass by noticing the math pattern. E.g. http://mirror.codeforces.com/contest/313/submission/3799994

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

          Oh, then it could have been a bit faster. Thanks for the tip :)

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

            Your pass is not that slow though :). 1 + 4 + 16 +... ~ 3 passes of the array.

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

      When I see n <= 10^5 and I have a O(nlog(n)) or faster solution, Python is the first choise.

      → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +21 Vote: I do not like it
    Or just increment the time limit for certain languages

    So… You have a job, your boss gives you a task and you implement it in Python. Everything is great, until customers start complaining that they have to wait minutes for your software to run. But you don't see it as a problem and tell your boss: "I know, it's Python, just tell them to wait more!" Does this sound realistic?

    In my opinion, programs should be judged against real-life criteria, such as real running time and memory usage, not against arbitrarily chosen adjustments so that "different languages are equal". This is fair, and treating programs in different languages differently is not fair. If your language fails to be on par with others, then it is the language's fault, not Codeforces' fault.

    It is about using the right tool for the job. C++ and Python have their advantages, and also have their disadvantages. C++ is fast, but hard to program in. Python is easy, but slow. You consider both options (which is more important — short code or fast code?) and choose the better tool in order to achieve a better result. If you knowingly chose the inferior tool, then it is your mistake and you will get penalized for that.

    Now, here you might say that you had no idea your Python code would run so slow. But this is just a part of the learning process — you tried it and received negative feedback, and this will affect your future decisions (you will likely choose not to do the same thing again).

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

My same code got Time limit exceeded in contest but Accepted in practise...

I wonder why???

TLE code : 3800440 AC code : 3803673

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

    thats really mysterious....u should probably report this issue to the admin with the above details.

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

    Probably the way they measure the runtime of a code is not smart enough. Report it so they can do something about it, if possible. Not only your particular case but in general.

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

    TLE code : 3799383 AC code : 3804162

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

It is really funny, IceTube has become purple and Goldensea is blue ! and I think he can't compete in Div 1

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

I had no idea about the difference in runtime between read using scanf/printf and cin/cout in C++. I always use scanf/printf in codechef and spoj but I was confident here in codeforces. I got TLE in problem C and I change cin/cout by printf/scanf and I got AC in 1 sec. Great, I will use scanf/printf here too.

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

    Try resubmitting the exact same code that gets you TLE again. It could get AC now. A lot of participants have had this problem today. If so, I think you should report this to the authority.

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

It seems like many participants' solution of problem C got TLE during the contest but the exact same code gets AC after the contest! This is really unfair for the people who've faced this.

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

Any quick explanation on how to solve Problem E?

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

    Greedily, i in set A should add m-i-1 in set B. If the amount of i are more than m-i-1 's, we should add m-i-2. Before that wo should do i+1 add m-i-2. So use a stack to solve it. Complexity O(m+n). The O(n) is printing answer.

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

What is meet-in-the-middle algorithm ?

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

    I have only used this algo once, with some help from a friend. So I might not be able to explain efficiently. Still giving it a go.

    Here's a demo of the algo -

    You have a set of integers consisting of no more than 34 elements and want to find the number of subsets such that the sum of the integers in a subset is an integer N (N is a known value).

    A brute solution would be to try all 2^34 ways, which is not efficient.

    So what we do is we split the set in two equal subsets (meet in the middle algo), try to form all possible subsets for each set and record the results (the number of results is at most 2^17 for each set), then for each element in one set, run binary searches to find upper limit and lower limit for compatible results in the other set.

    I don't know if this explanation is good enough. Maybe you can take a look at this. http://www.infoarena.ro/blog/meet-in-the-middle

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

Why my code got WA on testcases 11 ?3805151

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

Can someone give me an idea for Problem C??

I was actually trying to simulate, but I think it is unnecessary... can someon eplease help?

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

    yes, actually you don't need to simulate the assignment in your code

    the idea is to select biggest 4^n numbers then biggest 4^n-1 then 4^n-2 until 4^0

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

Great contest

Really waiting for editorial, specially for brilliant problems D and E. GL & HF!

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

TLE : 3798859 ACC : 3806006 what should i do about it?

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

3806042 why am i getting runtime error? Its working perfectly on my console

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

    In C89 you have to return 0 from main(). Also, you should not cast away const.

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

      Thanks a lot.It got accepted after using return 0 :)

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

hopefully there will be a new round this sunday for both div 1 and 2.

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

3811425 Ilya and matrix Hi, can someone refer to above submission and tell me why it is giving TLE error. I mean i have written in JAVA and used the buffered reader. I tested the same on my laptop (a core2duo machine) for a test file with data of size 1048576 and those many numbers and it completes in 500millisecs. but i always get TLE. is my reading method faulty? or the algorithm. I only have one loop.

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

    yeah got the problem. i was using Java6, changed to Java7 got accepted in seconds.

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

In C problem,why I used cmp function(write by my self) tle but didn't use can ac!!

→ Reply