rng_58's blog

AtCoder Regular Contest 070 and interactive problems
By rng_58, history, 8 years ago, In English

There will be ARC 070 this Saturday, and interactive problems may be used there.

You can try an example of interactive problem on AtCoder here: https://practice.contest.atcoder.jp/tasks/practice_2

Here is my solution for 100 points:

#include <fstream>
#include <string>

using namespace std;

int main(void){
	int N,Q,i,j;
	
	scanf("%d%d", &N, &Q);
	
	string s;
	for(i=0;i<N;i++) s += (char)('A' + i);
	
	for(i=0;i<N;i++) for(j=0;j<N-1;j++){
		printf("? %c %c\n", s[j], s[j+1]);
		fflush(stdout);
		char ans;
		scanf(" %c", &ans);
		if(ans == '>') swap(s[j], s[j+1]);
	}
	
	printf("! %s\n", s.c_str());
	fflush(stdout);
	
	return 0;
}
  • Vote: I like it
  • +74
  • Vote: I do not like it

Comments Comments (35)
| Write comment?
»
8 years ago, # |
  Vote: I like it -6 Vote: I do not like it

I can't find timezone of the contest. If it's plausible to you, could you tell me relevant time for India?. Thanks.

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

All the contests are at the same time. Maybe you can make the time of your contests more diversified in the future so that more people might be able to participate?

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

    What time do you suggest in particular?

    Given that many contestants come from Japan, it's almost the latest possible time slot (21:00-22:XX), and if we make it earlier it will be less convenient for people in Russia/Europe.

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

      This time is a bit too early for western coast and central region of US. I wish you could scatter the time all around so that everyone can participate in some round, like topcoder and codeforce. Of course if you only target people in Asia, then nevermind :)

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

        Make Asia Great Again!

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

        In my opinion, it is ok that atcoder sometimes change the starting time, but:
        Many codeforces rounds starts in 0:00-3:00 JST (?) and even many hackerrank rounds (Hourrank, 101 Hack) too, and I can't participate many of them. But if he/she fits in the timezone, he/she can participate.
        I think you said that you want more 0:00-3:00 JST contests, I can't participate many contests even I am practicing hard for contests! (Many coders in Japan participates usual-time codeforces round, but I am only 14 and if next day I have a school, I can't participate)

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

          I understand. As I said it depends entirely on which groups of people it aims at.

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

Does ABC 056 has an interactive problem?

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

    No, interactive algorithms are too advanced for ABC.

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

      I'm so sorry to making interactive problems too earlier, important and enable partial-points problems.

      • Square869120Contest #4(2017/04/09) Problem H: Link
      • Square869120Contest #3( 2016/11/20 ) Problem H: Link

      I'm so sorry about held contests with interactive problem before the contest (ARC070), practice contest, and there is no way to practice this types of problem before Square869120Contest #3 without any announcement in codeforces blog.
      → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Contest starts in 15 minute

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

OMG, did nothing :P How to solve D (second task)?

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

    Sort the cards in descending order and binary search for the first unnecessary card. Checking whether a card is unnecessary can be done with a knapsack-like algorithm.

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

    For a card with value V to be unnecessary, there has to be a subset of cards that DOES NOT contain it with sum in the interval [K-V, K-1]. I did an O(N*K) dynamic programming in order to find out for each prefix (and each suffix) of the array of cards what sums in the range [0, K-1] you can obtain using cards in said prefix/suffix. Then, for each card i just check in O(K) whether there is any set with a sum between K-V and K-1 by saying "I will take sum S from left of i" and checking whether any sum between K-V-S and K-1-S is obtainable from the suffix after i (partial sums). Total, O(N*K).

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

Loved the contest, well done guys!

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

This was a pretty bad contest for me :/

C: Newline?!

D: Wow one line was wrong in my binsearch solution

E: After wasting half the time on C and D --> only brute force partial

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

Problem E seems like a problem in APOI 2016!

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

Was anyone else confused by this sentence in problem D?

If, for any good subset of the cards containing card i, the set that can be obtained by eliminating card i from the subset is also good, card i is unnecessary.

At first I thought that meant "if there exists good subset..." but the actual meaning was "if for every good subset..."

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

How to solve E?

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

Hey why you dont give editorial in english ? We dont understand japanese language and google translator is not as good from japanese to english .

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

    They do have editorial in English. You just need to scroll the pdf file a little bit.

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

      Ow thanks :) .

      Hello ,

      C — Go Home , I am facing with that problem . For the input 12 how output is 5 ?

      My solution is :

      at time 0 we jump from 0 to 1 co-ordinate

      at time 1 we jump from 1 to 3 co-ordinate

      at time 2 we jump from 3 to 6 co-ordinate

      at time 3 we dont jump because now jump length will be 4 , since we are on co-ordinate 6 so if we jump we will be on 6+4=10 co-ordinate ,

      at time 4 we dont jump because now jump length will be 5 , since we are on co-ordinate 6 so if we jump we will be on 6+5=10 co-ordinate ,

      at time 5 we will jump because now jump length will be 6 , since we are on co-ordinate 6 so if we jump we will be on 6+6=12 co-ordinate . We reached on co-ordinate 12 at time 6 . because one jump takes one second (5+1=6) .

      So ans should be 6 . Why 5 ?

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

        1+2+0+4+5

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

          thanks :) .

          How to solve this problem if they said

          Find minimum jump and minimum time to reach X . Here we have to minimize the time and minimize the jump also .

          For example :

          12

          ans should be : minimum jump=4 and minimum time=5

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

            Consider that you jump forward every second. After t jumps you'll be at some point P >= X for the first time. Obviously, you can't use less than t seconds to get to X, but it can easily be shown, that you can get to X at exactly t seconds (just do not perform the jump of length P — X).

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

I think that you should recalibrate the point values. The 1000 ptr was definitely worth much more. I would say that it was worth at least 1200 pts.

It is important to provide correct point values. Please, do not be so modest in the future.

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

Questions about E:

  1. How can one see, that a function, described in the editorial, is a polyline with that slopes? What about the intercepts?

  2. How to recalculate that slopes using sets?

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

    Can someone please explain the editorial in some more detail? It is not at all apparent to me after reading the explanation about how we move from DP[i][x] to the polyline solution described.

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

It seems that the tests for problem D are too weak. Look at this accepted submission, for example. It's incorrect: with K = 2018, a = [2, 3, 2014, 2015] the correct answer is 0, but it returns 1.

→ Reply