I had issues entering the site for the first three minutes of the contest. Apparently they got fixed themselves.

Problem A - HQ9+

An easy one, the only characters that do any printing are H, Q and 9. So, just make a loop to detect them.

I actually spent a lot of time getting my setup to run and test stuff for some reason.

Problem B - Unary

Just at the bottom of the statement, it finally explains that the unary system just writes 1 n times. The length of a number n when represented in unary is thus

*exactly*n.

Then we need to find the actual number n. It is the result of the concatenation of a (possibly large) amount of 4 bits numbers in binary. Three things:

- Consider the binary blocks as decimal numbers directly, for example consider < to be 8 right away.

- To concatenate 1000 with 1010 is the same as doing: 1000 * 10000 + 1010. In decimal it translates into 8 * 16 + 10.

- So, to concatenate the (n-1) first symbols with a new one, find the result X for the n-1 first symbols then do: (n-1)*16 + new.

- The actual number may be very large (400 bits). But the problem asks for the result modulo 1000003. We can just exploit some modular arithmetic . (X * Y + Z) mod 1000003 is equal to ( (X mod 1000003) * (Y mod 1000003) + Z ) mod 1000003. This way, we need only to remember the partial results modulo 1000003.

constintMOD=1000003;

inttranslate(charch){

switch(ch){

case'>':return8;

case'<':return9;//→1001,

case'+':return10;//→1010,

case'-':return11;//→1011,

case'.':return12;//→1100,

case',':return13;//→1101,

case'[':return14;//→1110,

case']':return15;//→1111.

}}

intsolve(string x){

intres=0;

for(inti=0;i<x.size();i++){

res=(res<<4)%MOD;

res+=translate(x[i]);

res%=MOD;

}

returnres;}

Problem C - Turing tape

* Keep in mind the integer value of the previous printed character. For i=0, this is 0, else it is the (i-1)-th character of the input string.

* The conversion is: rev[ (x - rev(last) ) mod 256 ], it is simple to revert, first, reverse the i-th printed character, then solve the modular equaton, yes, once again modular arithmetic.

I was going to explain more problems but I will go take lunch, will update this soon.

Problem D - Piet

Oh, this is such an evil problem. Anyway, since n can be 10^7, you'd probably like to do each step in O(1). In order to do each step in O(1) you need to precalculate various things that you can use in each step. First, find the blocks and which block each cell belongs to.

What I did was to also precalculate the corner cells of each block (A look at the statement reveals that every move involves moving from a corner of a block to another).

To represent the directions (DP), I use a integer from 0 to 3. The offsets (change of coordinates) are left, down, right, up - ordered in clockwise order. CP will then be the offset in the direction index from DP and is -1 or 1.

The implementation of the logic takes some work of thought. In my case, I need to convert DP and CP into a corner of the current block. Then from that corner, move according to DP and find the next block. If it is black or outside the board, you would need to rotate DP and CP according to the statement.

intm;intn;

string board[50];

intblockn;intcellBlock[50][50];intblockCornerX[2500][2][2];intblockCornerY[2500][2][2];

charsolve(){

//a)letussaveablockidforeachsquareinthegrid

memset(cellBlock,-1,sizeof(cellBlock));

blockn=0;

intw=m;

inth=board[0].size();

//getinfoaboutourbelovedblocks.

for(inti=0;i<w;i++){

for(intj=0;j<h;j++){

if((board[i][j]!='0')&&(cellBlock[i][j]==-1)){

inta=i;

while((a<w)&&(board[a][j]==board[i][j])){

a++;

}

intb=j;

while((b<h)&&(board[i][b]==board[i][j])){

b++;

}

for(intx=i;x<a;x++){

for(inty=j;y<b;y++){

cellBlock[x][y]=blockn;

}

}

for(intx=0;x<2;x++){

for(inty=0;y<2;y++){

blockCornerX[blockn][x][y]=i+(a-1-i)*x;

blockCornerY[blockn][x][y]=j+(b-1-j)*y;

}

}

blockn++;

}

}

}

intBP=0;

intdx[4]={0,1,0,-1};

intdy[4]={1,0,-1,0};

intDP=0;

intCP=-1;

for(intt=0;t<n;t++){

//cout<<"t"<<t<<":"<<BP<<";"<<dx[DP]<<","<<dy[DP]<<";"<<CP<<endl;

intnx=dx[DP]+dx[(DP+CP+4)%4];

intny=dy[DP]+dy[(DP+CP+4)%4];

if(nx==-1){

nx=0;

}else{

nx=1;

}

if(ny==-1){

ny=0;

}else{

ny=1;

}

intcx=blockCornerX[BP][nx][ny];

intcy=blockCornerY[BP][nx][ny];

nx=cx+dx[DP];

ny=cy+dy[DP];

if((nx<0)||(nx>=w)||(ny<0)||(ny>=h)||(board[nx][ny]=='0')){

//black

if(CP==-1){//leftturnsintoright

CP=1;

}else{

//rightturnsintoleft,butDProtates90degrees.

DP=(DP+1)%4;

CP=-1;

}

}else{

BP=cellBlock[nx][ny];

}

}

//cout<<"t"<<n<<":"<<BP<<";"<<DP<<";"<<CP<<endl;

returnboard[blockCornerX[BP][0][0]][blockCornerY[BP][0][0]];}

Problem E - Logo turtle

At first I was excited but then figured the problem has little to do with LOGO. It took me a while to understand that T - turn around means a 180 degrees turn. Anyway, the problem is solvable with dynamic programming.

Take for instance a recurrence F(p, n, d, minimize). If minimize is true, the function will find the minimum possible position offset if we only use commands higher than or equal to p, must change

**n**commands, and d is 0 if we are facing right or 1 if we are facing left. At each recursive step, we can decide to alter the p-th character or not. If we do, we increase (d is 0) or decrease (d is 1) the position, or turn the direction and then will move F(p+1, nn, nd, minimize) positions.

The base case is when p is equal to the number of commands, there are no commands to make. However, remember that we must do n changes. If n is even, we can waste the changes by repeating all of the changes on a single command (and thus changing nothing). Else we return -INFINITE (if minimize is false) or INFINITE (if it is true).

Why do we need to minimize and maximize the result? Because the largest distance can be at some point that is negative. So, if the minimum value we can find is negative, we can negate it and find a possible max distance.

Edit: seems I passed system tests in all the problems. Good. Hopefully I will only do division 1 problem sets from now (unless the contest is div2 only, I guess).

**Edit:**Here is the code for E.

stringcommands;

boolknownAnswer[101][51][2][2];intanswer[101][51][2][2];

constintINF=1000000;

//Returnstheminimum/maximumchangeindistancestartingatcommandp.Ifwemust//donchanges.Thecurrentdirectionisd(0:positive,1:negative).//intrec(intp,intn,intd,intwantMinimum){

int&res=answer[p][n][d][wantMinimum];

if(!knownAnswer[p][n][d][wantMinimum]){

res=(wantMinimum?INF:-INF);

if(p==commands.size()){//iftherearenomorecommandsleft,we

//cannotdecidetochangeanymorecommands

if(n%2==0){

res=0;//won'tmoveanything,theonlypossibleoffsetis0.

}

}else{

for(intdoChange=0;doChange<2;doChange++){

if((doChange==0)||(n>0)){//canweactuallychangethis?

intnn=n;

intnd=d;

charcom=commands[p];

if(doChange){

com=((com=='T')?'F':'T');

nn--;

}

intx=0;

if(com=='T'){

nd=!d;

}else{//moveforward(dependingonyourdirection).

if(d==0){

x++;

}else{

x--;

}

}

if(wantMinimum){

res=std::min(res,x+rec(p+1,nn,nd,wantMinimum));

}else{

res=std::max(res,x+rec(p+1,nn,nd,wantMinimum));

}

}

}

}

knownAnswer[p][n][d][wantMinimum]=true;

}

returnres;}

intsolve(intn){

memset(knownAnswer,0,sizeof(knownAnswer));

intminim=abs(-rec(0,n,0,true));//minimumoffsetfromthisstartingpoint

intmaxim=abs(-rec(0,n,0,false));//maximum...

returnstd::max(minim,maxim);}

## 7 comments :

Congratulations on 8th place!

Thanks

Hello vexorian. I was wondering if you can send me your solution for E problem? I read your post and understood the main idea, but can i take a look over your code please I'm pretty sure I'll get it faster? (i won't use it). Thanks in advance, Tudor.

The problem with my original solution for E was that during the contest I did a lot of things that made the solution more complicated for no reason (weren't needed).

I thought you could see solutions from the standings. Seems that is not the case.

Ok, I have posted a fixed version of the solution.

Since I am new to codeforces' rating, I tried to compare the percentiles needed for each rating in TopCoder and Codeforces.

I just learned that the percentile required to be in division 1 in topcoder is around 65 (means you have to be better than 65% of the coders). Whilst in Codeforces it is 85%).

In fact, being purple in Codeforces is equivalent to having around 1650 points in Topcoder. It is actually interesting that the rating values for given percentiles between both sites tend to be within 100 points with codeforces' rating being higher. Except in the case of the very high rated coders, where things go the opposite way and Topcoder's are inflated.

Thanks for replying my post. I understand now your code and what is the main idea of the solution. Best luck next rounds and see you on higher ranks every time!

Great Performance,congrats!!!

(And a great editorial too! )

Post a Comment