-emli-'s blog

AtCoder Regular Contest 072 / Beginner Contest 059

By -emli-, history, 8 years ago, In English

Two contests AtCoder Regular Contest 072 and AtCoder Beginner Contest 059 will be held at the same time.

You can participate in whichever contest you want. (However, you can't register to both competitions.) The last two tasks in ABC are the same as the first two tasks in ARC.

Time： April 22nd (Saturday), 21:00 JST

Duration: 100 minutes

Number of Tasks: 4

writer： hogloid

Rating： 0-2799 for ARC, 0-1199 for ABC

The point value are:

ABC: 100 — 200 — 300 — 500

ARC: 300 — 500 — 900 — 900

We are looking forward to your participation!

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

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

How to Solve Problem D?

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

    write stupid solution, and then you can notice that if abs(x — y) <= 1 answer is Brown else Alice

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

      It seems that this way helps a lot.

      Implementing a Brute Force Solution then trying to notice the Sequence.

      Nice Job 300iq Thank You.

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

        Can you post the stupid solution?

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

          I could not even write that stupid solution correctly :(

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

            I think this is enough.

                boolean solve (int x, int y) {
        if ((x == 1 && y == 1) || (x == 1 && y == 0)) 
             return false;
        boolean win = false;
        for (int i = 2; i <= x; i += 2) {
            if (!solve(x - i, y + i / 2)) win = true;
        }
        for (int i = 2; i <= y; i += 2) {
            if (!solve(x + i / 2, y - i)) win = true;
        }
        return win;
    }
            → Reply
            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Ohhhh,I put in the code powers of 2 ,not multiple of 2 :(

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

              I think even only this is enough :D

              boolean solve (int x, int y) {
    for (int i = 2; i <= x; i += 2) {
        if (!solve(x - i, y + i / 2)) return true;
    }
    for (int i = 2; i <= y; i += 2) {
        if (!solve(x + i / 2, y - i)) return true;
    }
    return false;
}
              → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anybody give hint for C? Greedy solution was incorrect.

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

    "For every i (1≤i≤n−1), the sign of the sum of the terms from the 1-st through i-th term, is different from the sign of the sum of the terms from the 1-st through (i+1)-th term."

    From this we know that the sign of the prefix Sums of the Solution will be like that in the end

    +Ve, -Ve, +Ve, -Ve, +Ve, ... or -Ve, +Ve, -Ve, +Ve, -Ve, ...

    So just take the minimum of transforming the Original Sequence to Both Solutions.

    If You are trying to transform the Sequence to one of the Solutions and the prefix sum of the first i elements should be positive but now it is negative you will need to make some operations to make the sum 1 (The least positive number), and If You are trying to transform the Sequence to one of the Solutions and the prefix sum of the first i elements should be negative but now it is positive you will need to make some operations to make the sum -1 (The biggest negative number).

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

      Thank You! I tried for any one sequence. If first one is +ve than +ve unless negative. Nice Approach.

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

How to solve E?

→ Reply