Блог пользователя wlzhouzhuan

Автор wlzhouzhuan, история, 3 года назад, По-английски

Hello, codeforces! I don't think the interactor of CF1557E is smart enough. Many wrong codes can get Accepted.

First, the hack input format in CF1557E is:

T
x[1] y[1]
x[2] y[2]
...
x[T] y[T]

As you see, we can only input the coordinate of the King, but the King's route is by interactor.

So I have no way to hack it, but to post a blog to say it.

Take my code as an example: https://mirror.codeforces.com/contest/1557/submission/125431623 .

It's not correct, and it can be easily hacked.

Here is my Hand Player , which you can control the King's route (use Windows) :

// Author: wlzhouzhuan
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pb push_back
#define fir first
#define sec second
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, t) memset(s, t, sizeof(s))
#define mcpy(s, t) memcpy(s, t, sizeof(t))
#define poly vector<int>
#define SZ(x) (int(x.size()))
template<typename T1, typename T2> void ckmin(T1 &a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> void ckmax(T1 &a, T2 b) { if (a < b) a = b; }
int read() {
  int x = 0, f = 0; char ch = getchar();
  while (!isdigit(ch)) f |= ch == '-', ch = getchar();
  while (isdigit(ch)) x = 10 * x + ch - '0', ch = getchar();
  return f ? -x : x;
}
template<typename T> void print(T x) {
  if (x < 0) putchar('-'), x = -x;
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
template<typename T> void print(T x, char let) {
  print(x), putchar(let);
}

vector<pii> vec;
bool ban[10][10];
int Qx, Qy;
int Kx, Ky;

int main() {
  Qx = Qy = 1;
  Kx = 4, Ky = 4;
  int times = 131;
  while (times--) {
    system("cls");
    for (int i = 1; i <= 8; i++) {
      for (int j = 1; j <= 8; j++) {
        if (i == Qx && j == Qy) {
          printf("Q "); 
          ban[i][j] = 0;
        } else if (i == Kx && j == Ky) {
          printf("K ");
          ban[i][j] = 0;
        } else if (i == Qx || j == Qy || abs(i - Qx) == abs(j - Qy)) {
          printf("# ");
          ban[i][j] = 1;
        } else {
          printf(". ");
          ban[i][j] = 0;
        }
      }
      puts("");
    }
    int tox, toy;
    cin >> tox >> toy;
    if (tox == -1) {
      for (auto v: vec) {
        printf("%d %d\n", v.fir, v.sec);
      }
      system("pause");
      continue;
    }
    if (ban[tox][toy]) {
      puts("Invalid!");
      system("pause");
      continue;
    }
    if (abs(tox - Kx) <= 1 && abs(toy - Ky) <= 1 && !(tox == Kx && toy == Ky)) {
      Kx = tox, Ky = toy;
      vec.pb({Kx, Ky});
    } else {
      puts("Invalid");
      system("pause");
      continue;
    }
    if (Qx & 1) Qy++;
    else Qy--;
    if (Qy > 8) Qx++, Qy = 8;
    if (Qy < 1) Qx++, Qy = 1;
    if (Qx > 8) Qx = 1; 
  }
  system("cls");
  for (auto v: vec) {
    printf("%d %d\n", v.fir, v.sec);
  }
  return 0;
}

I made the hack by hand (130+ steps, and the King still alive):

4 4
4 3
5 4
5 5
5 6
5 7
5 8
6 8
6 7
6 6
6 5
5 4
5 3
5 2
6 2
5 3
4 4
4 5
5 5
5 4
5 3
5 2
4 2
4 3
4 4
3 4
2 4
1 5
2 6
2 7
2 8
2 7
2 6
2 5
2 4
3 4
3 3
3 2
3 3
3 4
3 5
3 6
2 6
2 7
2 8
3 8
3 7
3 6
3 5
3 4
3 3
3 2
3 1
4 1
4 2
4 3
4 4
4 5
4 6
4 7
4 6
4 5
4 4
4 3
5 3
5 2
5 1
4 1
5 1
4 1
4 2
4 3
4 4
3 4
4 4
5 5
5 6
5 5
5 4
4 5
3 5
2 5
1 5
1 4
1 3
1 2
2 3
2 4
2 5
1 6
2 6
2 7
2 8
2 7
2 6
2 5
2 4
2 3
3 3
3 2
3 1
3 2
3 3
3 4
3 5
3 6
4 6
4 7
4 8
4 7
4 6
4 5
4 4
4 3
5 3
5 2
5 1
5 2
5 3
5 4
5 5
5 6
6 6
6 7
6 8
6 7
6 6
6 5
6 4
6 5
6 4
5 4

So I think writers should change the interactor's strategy to avoid the incorrect code gets Accepted.

What's your opinion about it ?

  • Проголосовать: нравится
  • +500
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится -97 Проголосовать: не нравится

orz zz

»
3 года назад, # |
  Проголосовать: нравится +254 Проголосовать: не нравится

The hack format is a joke

»
3 года назад, # |
  Проголосовать: нравится +331 Проголосовать: не нравится

The interactor is a joke.

»
3 года назад, # |
  Проголосовать: нравится +126 Проголосовать: не нравится

Some people wrote wrong code but passed the system test just because of the wrong interactor.What a mess!

»
3 года назад, # |
  Проголосовать: нравится +58 Проголосовать: не нравится

the problem is a joke.......

»
3 года назад, # |
  Проголосовать: нравится -120 Проголосовать: не нравится

orz zz

»
3 года назад, # |
  Проголосовать: нравится -134 Проголосовать: не нравится

orz zz

»
3 года назад, # |
  Проголосовать: нравится +91 Проголосовать: не нравится

In fact, this problem reminds me of The Queen and the Knight, which is a similar interactive problem.

I'm very curious about how the interactors for these two problems were implemented. Obviously it is not easy to kill some incorrect algorithms.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +42 Проголосовать: не нравится

    In this problem, the interactor does the following:

    • retroanalysis for small N (up to 40)

    • heuristics against some general flavor of solution for larger N

    • a couple strategies to not always play according to the heuristics


    In such problems, it is more obvious than ever that the jury may be unable to block all incorrect solutions from passing. In reality though, in a typical problem, the jury does not block the weirdest ones either: the ones that don't pass a specific few from the vast space of tests may still get through. Here, it's just more visible, brought to front.

    It is up to the authors whether giving a particular problem is worth the risk. And obviously, the contestants may surprise the authors then :) . Even more probable when the problem is solved by thousands.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +25 Проголосовать: не нравится

      It's fine to give such a problem and the statement is ok but I'd like to see a note if the interactor plays optimally or not. If it's impossible to win exactly 100% of games under the given conditions (idk if it's the case here), it should be mentioned like in [problem:733H].

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +12 Проголосовать: не нравится

        I think that if the statement does not say something like "It's guaranteed that the test data are randomly generated" or "It's guaranteed that the interactor's strategy is XXX", then the intended solution should assume that the interactor uses the optimal strategy. Unfortunately, it's almost impossible to write an interactor that can kill all kinds of incorrect implementations. Some algorithms based on randomization or very complex strategies may need to be attacked for specific implementations. It is not possible for the problem setter to implement all incorrect algorithms and kill them.

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится +9 Проголосовать: не нравится

          In general, yes, but there are also adaptive and non-adaptive interactors. The former should be assumed optimal, the latter not necessarily (or it should always be obvious from context — if you know that you're fighting against a fixed strategy, you know what to do). There should always be this info in a problem statement.

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
              Проголосовать: нравится +17 Проголосовать: не нравится

            Oh, I forgot the bit about adaptability.

            It's true that there are many problems where the intended solution relies on the interactor being non-adaptive. And the problem setter always forgets to mark in the statement whether the interactor is adaptive or not. Maybe we should write out the behavior of interactor explicitly in the statement (such as whether it is adaptive), so as to avoid a lot of confusion.

            Properly describing the behavior of the interactor to the participants and implementing the interactor is indeed a difficult work.

            • »
              »
              »
              »
              »
              »
              »
              3 года назад, # ^ |
                Проголосовать: нравится +10 Проголосовать: не нравится

              So why not just make the interactor public to everyone? Life would be much easier.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится

        In the case of a chess-like game with two players, obviously the interactor is adaptive, as it has to take the contestant's moves into account.

        Other than that, the default is that the jury makes a reasonable effort to win against incorrect solutions. (As in non-interactive problems, the jury makes a reasonable effort to have good test coverage.) The amount of effort that is "reasonable" is hard to formalize. It can usually be guessed with the experience level similar to what is needed to solve the problem, in the process of solving it.

        In any case, the intended way to solve such problems (by default again) is to win always, or win with high probability regardless of the strategy chosen by the opponent. If a contestant uses other ways to solve it, like guessing what the particular author's interactor can or can not do, it's the risk the contestant is willing to take upon themselves.

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится +6 Проголосовать: не нравится

          It's not obvious. You can pick a random strategy ahead of time and use it. You can even keep making an arbitrary valid move. In this problem, an adaptive strategy can be much worse — trying to "run away" will make your position very obvious very quickly since you'll hit the edge.

          The amount of effort that is "reasonable" is hard to formalize.

          More than that, it's an arbitrary amount. Case in point here.

          it's the risk the contestant is willing to take upon themselves

          If you don't have a better solution, you don't risk anything by trying a solution you don't trust. In the worst case, you end up in the same situation as if you did nothing. You also don't the possibility of simply making a mistake that isn't caught by tests. On the other hand, problemsetters risk this situation.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +179 Проголосовать: не нравится

It's not that easy to write a correct interactor to make all the wrong codes get WA.At least I don't know how to write it.

But this is not an excuse for you to put a problem that can make some OBVIOUSLY WRONG codes passed!

»
3 года назад, # |
  Проголосовать: нравится +128 Проголосовать: не нравится

When you trying to create interactive problem whit not bs solution...

»
3 года назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

Try to hack this submit: 125431551. I think this randomize algorithm is difficult to be hacked.

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

    I think the solution is absolutely right, it gets enough information from interactor and the possibility of been hacked (with more than 130 queries) is so small that can be ignored. With some greedy it can be made into a determinstic program. Maybe someone could figure the upper bound queries of the algorithm and proof it.

    UPD: There are already analysis, Here

»
3 года назад, # |
  Проголосовать: нравится +83 Проголосовать: не нравится

This problem is cool, but the only other positive thing is that it at least didn't have a big impact on the round (only 7 official participants solved it). This could potentially ruin a whole Div 1 or combined round.

»
3 года назад, # |
  Проголосовать: нравится -268 Проголосовать: не нравится

I don't think the wlzhouzhuan is smart enough.

»
3 года назад, # |
Rev. 3   Проголосовать: нравится +15 Проголосовать: не нравится

The worst interactor of interactive problems I've ever seen.

Change a little form Rev. 1.

»
3 года назад, # |
  Проголосовать: нравится +55 Проголосовать: не нравится

Imagine the interactor for problem E is Magnus Carlsen

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    And during the contest I was thinking about the construction on Lichess analysis board editor. This is definitely the chessiest CF problem ever xD. And the observation that the number of times we will repeat the scan over all rows is bounded makes it a really nice construction problem.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +15 Проголосовать: не нравится

Basically, the interactor for problem E is our BM Samay Raina.

Spoiler
»
3 года назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

Good problem, but bad interactor :(