cgy4ever's blog

Topcoder Open 2017 — Round 1B
By cgy4ever, history, 8 years ago, In English

Exactly 1 week after Round 1A, we will have our 2nd TCO round.

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

You need to get top 750 with a positive score to advance. Note that if you have already advanced (in 1A or receive a bye), then you can't participate.

Find rules this year with the schedule here: https://tco17.topcoder.com/algorithm/rules/

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

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

When will you publish a list of those who advanced to next round from Round 1A ?

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

This round has third Data Science Weekly Challenge associated with it: the person who gets the most (positive) points for challenges while getting zero points for problems will get a TCO'17 t-shirt!

In case of a tie, the person who had the most points for problems after Challenge Phase will win. If the tie still holds, the person who had the most points for problems after Coding Phase will win. If nobody gets positive points for challenges and zero points for problems, the prize will not be awarded.

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

    You mean just fuck up your rating to get a chance to win a T-shirt

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

      1. it's TC, not CF — challenges can get you to top 20, maybe even top 10, if you're really good at them and really lucky

      2. more like you have a chance to win a t-shirt even if you fuck up, it's a consolation prize rather than a best troll award

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

Round 1B will start in 1 day!

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

    Will there be a parallel round for those who have already advanced?

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

      No, we don't. We will have them for round 2 and 3, and the wildcard round.

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

up

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

Does the rating changes happen after this qualification round ?

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

Div1 250 has started to tease even reds :P

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

    Judge's solution is incorrect.

    I challenged someone computing costH2O + costO2 * 2 in int with 300000000, 0, 1000000000, 1000000000, and the result is

    Your challenge of awata was unsuccessful. The method returned -0.231666082168 as expected.

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

      I tried same challenge on my code (in practice session) and got

      Your challenge of praran26 was unsuccessful. The method returned 0.0999999999877 as expected.

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

Don't you guys think that the rules of TCO are weird? You basically have to solve something to qualify to round 2, but it is really, really hard to qualify to round 3. Maybe it makes sense to allow less people to round 2 and more people to round 3. I know, that there are regional events, but they are not available for everyone.

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

    Yeah! Those good times when there were 5 rounds to advance :)

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

      The 5-round scheme adds more randomness to the result. If you fail in one round, you will disqualify immediately.

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

        Agree, from this point of view that is reasonable. Would be nice to some extra step in the current schema between rounds 1 and 2. Currently is top 2500 then top 120 and I am talking on Round 1,5 with top 600 or so with topcoder T-shirts for advancers.

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

    Certainly there is huge difference between R1 and R2, but the difference between R2 and R3 is also huge. For example, in GCJ, only R3 is a serious round for contenders for Finals.

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

How to solve the 250 pointer? :)

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

    Binary search the number of days.

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

    something / (costH2O + costO2 * 2.0)

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

      As far as I understand, it should be one of cases in an if-then-else, but not the only formula. Because we can use 2H2O → 2H2 + O2 but not 2H2 + O2 → 2H2O. So (double)remainH2O / (double)costH2O can be the answer too (if it's less-or-equal (double)remainO2 / (double)costO2)

      Unfortunately, I still don't know, did my solution fail just because of jury error, or it's really incorrect and I still don't know why.

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

How long do we have to usually wait for ranking update on TC? (my first contest)

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

    It's not a standard situation currently. There was an error in jury's solution (see http://codeforces.net/blog/entry/51377?#comment-353340 ).

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

      By the way can anyone explain solution to 1000?

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

        It's essentially DP on tree. Suppose, given a node i you calculate the answer for its children. So, the answer for the node i will be dp[i] = xw[i].(1 + dp[i1])(1 + dp[i2]).., where i1, i2... represents the children of node i.

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

    The result (and rating) has been fixed, you can find it here.

    I'm sorry for the issue and delay, and we will be more careful in the future.

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

Hello guys!!! I am new on codeforces. I gave TCO 17-1B but my solution of 250 points failed the system tests. I am unable to figure out the error. Please help me out!!! This is my function code link : Your text to link here...

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

    2*costo+costw this gives an integer overflow. By the way I have the same error and it seems that TCO initially did that wrong too.

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

      why would it give integer overflow?

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

        costo = costw = 1e9

        So 2*costo+costw is 3e9, what is more than a signed integer can handle.

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

          How do we handle this?

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

            By using a different datatype?

            2.0*costo+costw would implicitely cast the product and thus the sum to a double

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

              So instead of writing double timeadd= (double)remw/(2*costo+costw); i need to write double timeadd=(double)remw/y; where double y=2.0*costo+costw;

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

                In the expression (double)remw/(2*costo+costw) numerator and denominator will be evaluated separately: double/denominator. The denominator consits of ints only, so it will return an int.

                In the next step, when calculating the devision, the denominator will become a double. But the overflow had already happened.

                A valid solution would be (double)remw/(2.0*costo+costw) or just remw/(2.0*costo+costw).

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

Is the editorial available somewhere ???If not ,Can someone please tell how to solve B ???

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

    write k in binary, without the first digit. e.g. for k= 6 you get (1)10

    create a list with the number 1 as only entry. Then for each digit in the binary representation: add (sum of all numbers in the set + that digit) to the set. When the digit is 0, this will double the count of possible sums of subsets. If it is 1, you get 2*oldCount + 1.

    see also: fast exponentiation

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

      Thanks :)

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

      What is the logic behind this ?? I didnt get how exponentiation relates to this ??

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

        There is anoother solution. I claim that you can get every possible value from 1 to sum of all numbers in set S if in sorted set S for each i, s[i]-(sum of values from 0 to i-1)<=1. It is easy to proof.

        Rest of solution is easy, you just need to create set of sum k such that every next number is sum of previous+1. You need only log(k) numbers.

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

          Thanks got it !! The difference of value of 1(or zero) between adjacent sums is the key to get all possible sums ! And final sum should be equal to required K as this will be maximum sum possible ie adding all nos

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

        It is not really related to exponentiation. But there are really similar algorithms to solve these problems: you have one action, that doubles the number of distinct sums (or the exponent) and another action for 2*oldValue + 1.

        So not really related, but knowing about the exponentiation helped me to solve the task.

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

    I have a another solution. find the max x(2^x<=k).next add 2^0,2^1...2^x to vector. if k-sum> 0,then add k-sum to vector(sum=2^0+2^1+...+2^x） So we can get all number from 1 to k.

    → Reply