When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

cgy4ever's blog

By cgy4ever, history, 7 years ago, In English

Topcoder Open is back! The first round will be 1A:

Time: 12:00 noon EDT Saturday, April 1, 2017

As usual top 250 active coder will advance to Round 2 directly. We will announce the list of coder a bit later, at this time you can check this blog: https://www.topcoder.com/blog/next-algorithm-track-automatic-berths/

You can find rules this year with the schedule here: https://tco17.topcoder.com/algorithm/rules/

Update: Byes are announced here (cut-off rating is 1783): https://tco17.topcoder.com/algorithm/byes/

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

| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

cgy4ever I think top 750 will advance to R2 (not 250)

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

    It is not what he said. Topcoder's active top 250 advances to Round 2 without taking part in Round 1. Then, for every sub-round of Round 1, top 750 advances to Round 2, as you said.

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

Contest will start in 23 hours.

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

Auto comment: topic has been updated by cgy4ever (previous revision, new revision, compare).

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

This round has second Data Science Weekly Challenge associated with it: the author of the fastest submission to Easy problem in Round 1A done in the language which has the least submissions done in it will get a TCO'17 t-shirt!

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

    If by fastest time you mean counting from the time the problem is opened, this seems like a bad challenge as it is trivially cheatable. If this is indeed the case I predict somebody submits Visual Basic.NET solution within 20 seconds of "opening" problem. If it is timed from start of contest ignore my criticism, then it is fine.

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

      From the start of the contest, of course :-) It also has to be a correct submission, which I obviously forgot to state explicitly.

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

Can we filer submission by language on Topcoder?

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

Will there be a parallel round for those with byes to compete?

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

    No we don't have parallel for round 1. (If we have one then it will be something like Div1 contestants solving Div2 tasks, which is not that fun)

    We will have parallel round for round 2 and 3 for people already advance.

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

      That is really fun for me! I like solving easy tasks, it gives me a false sense of confidence! Otherwise I will be frustrated by always having difficult problems to work on.

      I wish that all problems on CodeForces and TopCoder were easier so we wouldn't have to think anymore!

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

A bit off topic, and maybe a newbie question, but why can't I practice from past SRMs right now? There's only TCO rounds in the options for practice rooms.

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

Off topic: does anyone know what to do if arena looks like this on my laptop?

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

Are we allowed to compete in TCO 1B if we qualify for the next round today in 1A?

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

987 registrants! I doubt that there will be 750 non-zero scores!

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

I couldn't hack medium problem because I couldn't slide the window.

»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve Hard ?

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

    I couldn't code it during contest, but I think it might work. Take the mirror image of the left half of the convex polygon, so both halves are in the right half(x >= 0). Now, you need to find the upper hull of this set of segments. Once you do that, you can sum the volumes by using the volume of a frustum of a cone formula.

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

      Cool! Thanks :)

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

      How to find the upper hull ?

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

        So now you have two sets of segments. Note each set has O(N) segments. We want to find all points of interest, basically, the points which can be present on our upper hull. For that, create a set of points S. Add each vertex belonging to at least one of the segments to S. Now for all segments, if they intersect, add their intersection points to S as well.

        Now create another set Y from S such that Y stores the y coordinate of every point in S. Now our target is for all , find the maximum x that it stretches to. To do that, let's fix the y coordinate, say it is r. Now iterate over all segments, and if the segment is such that it intersects the line y = r, then evaluate the line (assume the segment is a line) by fixing the y coordinate in that line as r, and finding the corresponding x coordinate. Find the maximum such x coordinate for every y.

        Now iterate over all in increasing/decreasing order, and use the formula for volume of a frustum of a cone. The radii for the frustum will be the maximum value of x coordinate for the current y value, and the maximum value of x coordinate for the previous y value. Height will be the difference in the current y coordinate and the previous one.

        AC Code: ideone

        Edit: When you are iterating over all points P, don't add (x, P.y) for every line L. Rather add it for only that line L' such that the corresponding x is maximum

        Edit 2: Rewrote Explanation.

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

    Another way of doing it is calculating if only the lefthand side is there, adding if only the righthand side is there, then subtracting the intersection of the two polygons. (Which should be easy to implement if you already have polygon intersection)

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

How to solve Medium?

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

    dp: f[a][b][c]=maximum surface of a cube of axbxc, in the transition cut a slice of length s from each dimension.

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

      And then comes someone who solves it greedily and make you unsuccessfully challenge him :(

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

    There is another solution to this. I divided each side into parts like A=(s,s,s,s,s....,s+a%s) similarly B and C. Then for every possible combination of a[],b[],c[] I calculated required answer.

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

      Optimized version of your solution described in editorial without proving:

      int[] dim = new int[] {A % S + S, B % S + S, C % S + S}; Arrays.sort(dim); dim[0] -= S; return (A * B * C — dim[0] * dim[1] * dim[2]) / S;

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

        This is a greedy approach.

        Let's cut off slices of thickness exactly S (it doesn't make sense to cut off thicker slices). If the total volume of the slices cut is the same, their total area is also the same regardless of the order in which the cuts are done. We can keep cutting them off until a piece with all dimensions less than 2S is left. The dimensions of this piece are given as dim.

        int[] dim = new int[] {A % S + S, B % S + S, C % S + S};
        

        This last piece is also a good slice, with thickness equal to the smallest of its dimensions and area equal to the product of two other dimensions. To make it a slice of thickness S, we can make a cut in the smallest dimension (this preserves the area of the slice). To get the dimensions of the throwaway piece (from which we can't produce any more slices), we model this cut:

        Arrays.sort(dim);
        dim[0] -= S;
        

        Finally, the only part of the original piece that is not converted to slices of thickness exactly S is this throwaway piece. To find the total area of good slices, we take the used volume (the volume of original piece minus the volume of throwaway piece), and divide it by S.

        return (A * B * C - dim[0] * dim[1] * dim[2]) / S;
        
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          It is not complete proving of optimality. Someone can ask:

          Why we can cut off slices of thickness exactly S of whole piece?

          Why we need stop cutting if dimension less than 2S ?

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

            Because if a dimension less than 2S is cut into a and b (a+b<2S), we would at best be having a>=S and b<S so the part with dimension B is wasted in this case(which could have been used in case the other dimension in the original piece was <a+b) so instead we could just retain the piece as it is and do not cut it.

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

So you can literally do nothing and rank 715 :)

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

It is only me or topcoder is too slow ?

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

How to upsolve the problems?

Will the contest be rated? If so, when will the rating be updated?

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

So many failed solutions on 250p problem(mine too)? What was the hack?

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

Will Byes also be there for Round 1B ?

»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

When I go to https://www.topcoder.com, I end up in an infinite loop of automatic redirects. Anybody else experiencing this?

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

    This happens in firefox. Either open in chrome or clear firefox cache.

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

      Thar was chrome, but yeah, clearing some data helped. Thanks!

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

    happens with me. I use chrome

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

In medium I am getting better results than expected.

Code

In Test 3: [49,92,20,3] I get 45080 and I should get 30045. What is going on? I would appreciate any insight.

UPD: I got it. The global variable bool inici shall be inside the class to reinitialize it for every test. Sorry for the noise.

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

    Were u using kawaga edit or something other than standard editor??

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

https://pastebin.com/4kaTEfff

Here is my solution for the 2nd problem. It didn't pass in the contest. I don't know why. I tested it in the practise mode and it showed me "Passed". Also I see many other similar solutions with mine that passed. So can you tell me what is wrong with my source or it is wrong with the system ?

Thank you !

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

    Click

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

      Well why I get TLE ? Isn't my complexity O(10^6) ? Also why in the practise mode it says "Passed" ?

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

        It's complexity is O(n^4). Declare a global cnt variable, increment it before if(ret != -1) return ret; you can see that there 2.97*10^8 recursive calls. I also had same solution but couldn't submit because of one typo error but it failed in practice room afterwards.

        Most people used O(n^3) solution. Instead of loop, you can cut two blocks one with size s and other size side-s. How to prove this is optimal?

        And there is O(1) solution.

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

          My solution's complexity is O(n4) and it passed the 100 100 100 1 case in 0.24s.

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

    I think that's pretty unfortunate. I tested the case provided by dush1729 during contest and that ran in roughly 1.5s in the arena.

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

      Did you test it with my source or with yours ? I saw similar solutions with mine that passed and I don't know what is wrong with mine....

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

        I tested my solution which is almost identical to yours, with complexity O(n4).

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

          Did it pass in the contest yesterday ?

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

            Yes it did.

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

              Well any idea what happened with mine ? It is really strange and I don't care for the current submission but I want to know what went wrong so I can avoid it in the future.

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

                TBH I don't know. Though your solution seems to fit TL by taking S globally, rather than passing in function. Also note that my solution's runtime varies in range 1.53-1.9

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

    It's really unfortunate that your code got TLE. But one correction, your complexity is not O(10^6) it's close to O(3*10^8) in worst case. Which is really tight.

    Besides, in your solve function you are using unnecessary too much if else condition which is also a main reason i think. And more importantly when you solve a problem using recursion it always add a constant factor.

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

How do I know if I qualified? do I get an email or something?

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

    You will get an email. Everyone got a positive score then you will advance (except cheater or ineligible for other reasons).