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;
}
I can't find timezone of the contest. If it's plausible to you, could you tell me relevant time for India?. Thanks.
It's 21:00 JST, and equivalent to 17:30 IST, I think.
Thanks. It would be one hour before for me then. Also, was time mentioned somewhere? (Going by some downvotes :) ).
Time of the AtCoder Regular Contest 070: https://www.timeanddate.com/worldclock/fixedtime.html?msg=AtCoder+Regular+Contest+070&iso=20170318T21&p1=248&ah=1&am=40
Big thanks. I think that would be it for my future contests. Great help mate. I did +1 (but there are some who don't believe in the pure and useful dissemination of information, so someone downvoted. :) ). Regards.
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?
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.
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 :)
Make Asia Great Again!
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)
I understand. As I said it depends entirely on which groups of people it aims at.
Does ABC 056 has an interactive problem?
No, interactive algorithms are too advanced for ABC.
I'm so sorry to making interactive problems too earlier, important and enable partial-points problems.
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.
Contest starts in 15 minute
s
OMG, did nothing :P How to solve D (second task)?
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.
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 anO(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 cardi
just check inO(K)
whether there is any set with a sum betweenK-V
andK-1
by saying "I will take sumS
from left ofi
" and checking whether any sum betweenK-V-S
andK-1-S
is obtainable from the suffix afteri
(partial sums). Total,O(N*K)
.Loved the contest, well done guys!
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
Problem E seems like a problem in APOI 2016!
Was anyone else confused by this sentence in problem D?
At first I thought that meant "if there exists good subset..." but the actual meaning was "if for every good subset..."
yes, it was confusing.
How to solve E?
Hey why you dont give editorial in english ? We dont understand japanese language and google translator is not as good from japanese to english .
They do have editorial in English. You just need to scroll the pdf file a little bit.
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 ?
1+2+0+4+5
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
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).
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.
Questions about E:
How can one see, that a function, described in the editorial, is a polyline with that slopes? What about the intercepts?
How to recalculate that slopes using sets?
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.
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.