-emli-'s blog

AtCoder Regular Contest 068 / Beginner Contest 053
By -emli-, history, 8 years ago, translation, In English

Hello everyone!

Today 15:00 MSK will be held personal competition.

I invite everyone to participate and let's discuss problems after the contest.

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

Comments Comments (25)
| Write comment?
»
8 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I think the event time is off by a week. And the contest also isn't today.

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

    Today

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

      Yes, the contest is today. (The link to timeanddate.com is off by a week).

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

I extended dj3500's hightail tool to parse online atcoder contest. I hope it works. If some hightail user wants to try out for testing purpose that would be awesome. Please drop a few words after using, if it worked or not. Specially I am interested to see if it performs okay across different platforms. I have finished it a few hours ago, so I am not that hopeful, but let's see.

You can download the jar file from here.

How to use: As usual, go to "Add contest", input the contest link like: http://agc009.contest.atcoder.jp or http://agc009.contest.atcoder.jp/ or https://agc009.contest.atcoder.jp/ or agc009.contest.atcoder.jp and so on. Put your username/password below, and hit Parse. (I have not tested the timer, but it should also work). username/password is only needed for "online contest". If you want to parse past contests, you won't need them.

Since the tool works with id/password, so please be careful. The id/pw is not saved in any local file, so that should be fine. However there is some threads online about taking "password" as String vs char[]. I have not taken the security measure that far. You may also run it via terminal "java -jar zzz.jar" and see if you see any exception when it was running.

Update: Timer also seems to be working.

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

In this problem I can't find rotation die of numbers. I tried, but possible it was wrong. The author of this problem why you didn't describe this. I wasted my time to find numbers on rotation.

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

    How to solve Yet Another Die Game?

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

      **HINT : ** You can make 11 in two moves.

      ans = (N / 11) * 2;
left = N % 11;

if(left)
	{
		if(left <= 6)
			ans++;
		if(left > 6)
			ans += 2;
	}
      → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Only 6->5->6->5->6->5->...
      So, if n mod 11 = 0, the answer is n / 11 * 2,
      and if 1 ≤ n mod 11 ≤ 6, the answer is floor(n / 11) * 2 + 1,
      and if 7 ≤ n mod 11 ≤ 10, the answer is floor(n / 11) * 2 + 2.
      Code: http://arc068.contest.atcoder.jp/submissions/1080980

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

      you can start with any side face up

      to make the max points you need to get 6 -> 5 -> 6 -> 5 -> ....

      so the optimal side to start is 5

      now , for 2 operations you can make 11 points

      the ans is :( x / 11 )*2

      if (x%11 != 0)

      you should add 2 operation if x%11 > 6

      or add 1 operation if x%11 <=6

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

How to solve E?

Also, please update the editorial, the editorial posted is for the recent grand contest.

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

    for each 1 ≤ d ≤ m , you need to count number of points li, ri such that li ≤ d, ri ≥ d or li ≤ 2d, li > d, ri ≥ 2d or li ≤ 3d, li > 2d, ri ≥ 3d ... , so its just some rectangle sum queries which can be done offline with BIT.

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

    Simply put, use a fenwick tree. I was crazy enough to use one that supported range updates, which was completely unnecessary :(.

    The observation you have to make here is that you're going to iterate the positions where the train stops like the harmonic series, which will make your baseline complexity O(m log m).

    The algorithm goes like this:
    - Iterate the jump length (denote this as x) in decreasing order.
    - While the longest segment we have in our heap is longer than x, pop it from the heap and update the fenwick tree accordingly.
    - Iterate i, i+x, i+2x... and count number of segments containing the point using fenwick tree.

    In implementation, do not use heap. Use sorted vector.

    Complexity: (n log n + m log m)

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

      By "update accordingly" you mean remove the segment from the Fenwick tree? So in the beginning, you add every segment?

      How would you do that without range updates??

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

        I guess this was unclear. Sorry about that. You are correct, you have to add every segment in the beginning. However, you do not need range updates for this. When updating segment [l, r], just update the l-th position in the fenwick tree by 1 and update the (r+1)-th position in the fenwick tree by -1. The number of segments containing the i-th position is query of the i-th position in the fenwick tree: query(i), not query(i)-query(i-1).

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

    All trains will visit about stations in total so you can run a simulation. Sadly, if you simply remember how many souvenirs can be purchased at a station, you may overcount whenever a segment is large enough to accomodate a train more than once.

    To overcome this, notice that for a train of type d you will always visit a segment whose length is  ≥ d so these segments can be counted towards the answer and thrown away. The smaller segments will be visited at most once and can be handled with a segment tree in the above simulation.

    In the increasing order of d, add segments that are no longer "long enough" to the segment tree and simulate the train d.

    Example solution: http://arc068.contest.atcoder.jp/submissions/1083406

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

    There is also a different solution in O(n*sqrt(m)). Let S=sqrt(m) and for each souvenir interval I, do the following:

    For each 1<=i<=S, check whether the i-th train stops in I — if yes, increment that train's counter. For each S<=i<=m, the i-th train will make at most S stops in total. For each k, the set of trains that visit I on their k-th stop is either empty or some interval [a,b] with 1<=a<=b<=m. Iterate over 1<=k<=S and increment everything in [a,b] using a prefix sum array — except everything that you already incremented for some other k.

    Implementation: http://arc068.contest.atcoder.jp/submissions/1085135

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

How to solve Card Eater?

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

    Let the number of i in a[i] -> c[i].
    Let sum = min(c[0] - 1, 0) + min(c[1] - 1, 0) + ... + min(c[100000] - 1, 0).
    The answer is n - floor(sum / 2) * 2.

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

    Get the number of cards that you have to delete. That is, frequency of each element — 1. Let us call it extra.

    If extra is even, answer is number of distinct elements, (cancel out the extras within themselves), or else, distinct elements — 1.

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

where can i get editorial in english for contest?

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

    There is no English editorial.

    Short editorial

    C: 6, 5, 6, 5, 6, 5, 6, 5, ... is the optimal strategy

    D: This operation can be described as "remove two arbitrary selected cards"

    E: For each d,

    • when ri - li > d, ith kind of souvenirs can be always purchased
    • otherwise, there is at most one station where you can purchase ith kind of souvenirs. It can be easily archieved by checking d, 2d, 3d, ...

    F: I'm sorry for my poor English. It's tough for me to describe the idea of solution. Please check the Accepted code.

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

      oh thanks for the brief explanation, but don't you think an editorial is necessary for such a contest especially for difficult problems like E, F.

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

How to solve problem F? Don't know what the state of dp means. Thanks in advance.

→ Reply