rng_58's blog

AtCoder Grand Contest 004
By rng_58, history, 8 years ago, In English

Note: The contest was moved to Sunday in order to avoid collision with TCO Russia.

AtCoder Grand Contest 004 will be held on Sunday (time). The writer is sugim48.

Contest Link

Contest Announcement

Let's discuss problems after the contest.

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

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

I just notice that the start time will be exactly same with TCO Russia Regional: http://tco16.topcoder.com/regional-events/tco16-russia/

That means Petr (and other people include myself) may not be able to participate.

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

    Thank you for the information, the contest was rescheduled.

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

      Thanks for moving! I will still be unable to participate since I will be on a plane from St Petersburg at the new time, but it should enable most of the other TCO event participants to take part.

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

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

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

Reminder that the Contest starts in < 5 hrs.

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

How to solve F (both for tree and not)?

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

    Uploaded the editorial.

    F looks very hard but after a single observation it looks much easier.

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

      Did other people miss the condition N-1 <= M <= N in the problem? Then the problem goes from impossible (in general graph case) to almost exactly the same as the small subtask.

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

enot got 2200 in F while others got only 1500. Is this a bug?

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

    1500 is partial point for the tree case.

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

      Oh, I didn't notice that F has partial point Orz

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

http://pastebin.com/pWvL9CzW

Problem B. Fails for test cases 13 onwards. Please provide test cases where this fails.

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

    Your answer is 32.

    The right answer is 24:

    * * * * * * * * * *  // all places unpaid
1 * 1 3 * 1 * 1 3 *  // pay for 6 places, total cost = 10
* Y * Y Y * Y * Y Y  // shift, total cost = 20
1 Y 1 Y Y 1 Y 1 Y Y  // pay for 4 places, total cost = 24
    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

wow, no AC submissions D:

can anybody point out what i did wrong in these codes?

A: https://ideone.com/LaCRZi if even, we can divide them into equal parts, else the answer is minimum of a*b, a*c, b*c (i derived this formula)

B: https://ideone.com/L5wdSL

first find the slime tht has minimum energy to catch (call the energy mn), basically all other slimes can be catched with either a[i], or mn+x, then just sum the numbers

C: https://ideone.com/whuoRY

BFS, backtrack, then mark all used path nodes visited, BFS again...

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

    if((a[0]%2==0)||(a[0]%2==0)||(a[0]%2==0))

    The above line from your code for A doesn't look right, does it?

    And why would your B and C solutions work? The logic is wrong in both.

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

      oh damn, initially the variables were a,b,c. but converted them to arrays to sort easier... the fault is in me, cannot beleive i did not notice it even tho i code is short...

      i get what i did wrong in B, but can i have countercase for C?

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

        Btw. learn to stress-test your solution (run it on many random tests to find a counter test).

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

rng_58, can you please increase the stack size for Java? And probably also for Scala and Kotlin.

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

    It is supposed to be 256MB (see stack limit section), do you think it works properly?

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

      I guess it doesn't work, because my solution gets a runtime error in D unless I set the stack size manually to 16 Mb using the following:

      Thread thread = new Thread(null, this::solve, "solution", 1 << 24);
      → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Looks like mmaxio also had problems with the stack size during the contest.

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

      BTW, another problem I faced with D is that my O(n) Java solution gets TLE, although it is almost identical to the accepted one by mmaxio... Considering that I use a pretty fast input reader, any ideas what is wrong with it?

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

In the editorial of B:

"if K = 2 and you need a slime of color 3, there are 3 ways to get it"

Why isn't just capturing a slime of color 3 a way? We can capture it without shifting anything! The editorial and problem statement isn't clear to me. Can someone please explain?

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

    I didn't understand the editorial of B either...

    Can anyone use an example to explain? Thanks a lot.

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

    Here we consider a case where we cast exactly K magics. Of course it is possible to just captuer a slime of color 3, and this case is covered by K = 0.

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

    Consider that you shift exactly 2 times. For slime i,

    1. If you want to capture it directly, capture it after you shift 2 times.

    2. If you want to get it from slime(i-1), capture slime(i-1) after you shift 1 times.

    3. If you want to get it from slime(i-2), capture slime(i-2) before any shift.

    If you fix the number of times you make a shift, the cost of shift is fixed. Therefore you only need to consider which kind of slime should you catch to get a slime of color i.

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

Hi!

Does someone have an idea why this is wrong on A ? http://pastebin.com/n5eZuxUq I spent 1h trying to figure out lol

I am not sure about the unsigned long long type but I don't see why it would be a problem

Thanks.

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

    You are declaring A B C as integers and then multiplying them before casting them to unsigned long longs. ex: 999999999 999999999 999999999, your code prints out 808348673 while the answer should be 999999998000000001.

    Try this: http://ideone.com/oDtVeg.

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

      Thanks !

      oh god 1h for that -_-

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

        Btw, when you're solving a small problem that doesn't need the best performance you could also declare everything as int and add 

        #define int long long

        At the begging of your code so that you don't have to deal with casting and all that.

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

Can anybody give example why greedy aproach doesn't work in D? I sorted all vertices by heights and then updated those vertices with depth more than K and updated children corresponding to the vertex..Link to my solution

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

    Try test

    8 2 1 1 2 3 3 3 3 3

    Answer 1

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

      Awesome! I just could not see that happening!! Thanks a lot!!!!

      → Reply