Div1 500 CubePacking

The second I opened this one, I knew I was not going to have a good match. It is that kind of problem that for me doesn't work too well. I spent a lot of time trying to do a solution that first picked dimensions of a prism in which to put all the LxLxL cubes and then to grow it to fit the 1x1x1. It seems that solution was completely wrong and clueless. Seeing at how things went, it seems this problem was way easier than that, but I just cannot think of something yet.

When I noticed that there were less than 30 minutes left, I decided to switch to 250.

Div1 250 CubeStickers

Link to problem statement

This one was painful. The first thing I did was to notice that you can sometimes use the same color in two faces. And in fact, that is the most times you can use the same color - Because if two faces are not on opposite sides of the cube, they will always be adjacent. Yet for some reason I couldn't think very fast of a way of actually verifying it.

That is right. In a cube, there are three pairs of faces that are opposites of each other. The only way to place two stickers of the same color is to place them in opposite faces. So, for each unique color in the list: If there are two or more instances of the color, "consume" two faces of the cube. If there is only one instance of the color, consume 1 face. If all 6 faces are 'consumed' everything is right and the result is "YES". If after using all colors, there are still faces that you cannot use , return "NO".

This is where the STL and thinking well of things works best. A good STL solution uses map<string, int> to first save the number of times each color appears. Then you can iterate through the elements of the map, and for each color that appears twice or more, use exactly 2 faces. And 1 face otherwise. Another way to see it is that you can use each unique color at most twice.

#include<vector>#include<map>usingnamespacestd;#define for_each(q,s)for(typeof(s.begin())q=s.begin();q!=s.end();q++)structCubeStickers{

string isPossible(vector<string>sticker)

{

map<string,int>colorTimes;

//Fillthemapwiththecountsofeachstickercolor

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

colorTimes[sticker[i]]++;

}

intavailable=0;

for_each(q,colorTimes){

//Wecanuseatmost2stickersofeachcolor.

available+=std::min(2,q->second);

}

return(available>=6)?"YES":"NO";

}};

I wanted to use for_each at some second during the match then I noticed that I had to type it all, so I gave up and did some incredibly dumb stuff with a vector for absolutely no reason. This is the moment I decided to add for_each to KawigiEdit's snippets

Div1 900 CubeBuilding

Link to problem statement

There were only 20 minutes left, but I knew two things: a) I was clueless about 500. and b) The hard one was worth 900 points, which is quite a suggestion that it is easier than 500. In a way this problem was easier than 500 , at least for me.

The first impression I had about the problem is that it was a dynamic programming problem in which you had to remove dimensions as much as possible. This impression turned out to be true. However, I made plenty of mistakes while thinking of the logic for the problem and when coding the memoization. Of course 20 minutes was too little time for me to debug and rethink things. I solved this problem only after the match.

The initial idea was as follows:

a) You can split the main problem into three variations: a) All the visible cubes must be red. b) Visible cubes must be green. and c) Visible cubes must be blue.

When we want to count the number of ways to make all visible cubes red. Then we have

**R**cubes of the correct color and

**G+B**cubes of the wrong color. When counting cases in which all visible cubes are blue, there are

**B**correct cubes and

**G**+

**R**wrong cubes. Same happens with the other case. So, what I did is generalize. F(

**good**,

**bad**,

**N**) returns the number of ways to place

**good**+

**bad**cubes in a NxN board such that only the

**good**ones are visible.

That division was mostly correct, but I eventually noticed that there was a vital mistake. The

**bad**cubes actually may have two different colors. However, solving F(

**good**,

**bad1**,

**bad2**,

**N**) may be too heavy so we need the optimization. The fix is to, once you have F(

**good**,

**bad1**+

**bad2**,

**N**), then you can get Combinations(

**bad1**+

**bad2**,

**bad1**) as the total number of ways to to pick the colors of the bad cubes. And just multiplying F(

**good**,

**bad1**+

**bad2**,

**N**) with Combinations(,

**bad1**+

**bad2**,

**bad1**) will give the total number of ways to do it for each color.

On to solve F(

**good**,

**bad**,

**N**), we can split the board in

**N**rows. For each row, we will place some cubes (good and bad) in a way that only the good ones are visible. Then we can proceed to the following row but the number of good and bad cubes may have been reduced. So, what if you could have a function G(

**good**,

**bad**) that would return the total number of ways to put

**good**correct-color and

**bad**wrong-color cubes in a single row? Since this function has a limited number of argument combinations, we could calculate the results for funtion G() before calculating F() which will remove some complexity from F().

So, for each row, pick a pair

**u**,

**v**of good and bad color cubes to place in the row , then proceed to the next row with a possibly-reduced number of good and bad cubes. Then the number of ways to have

**good**correct cubes and

**bad**wrong cubes in a NxN board by using (

**u**,

**v**) cubes in the first row is: F(good,bad, N) = G(u, v) * F(good - u, bad - v, N-1).

This allows a simple recursion that can also be memoized.

We just need to solve G. Note that after we add some

**good**cubes in the front cell of the row, then the rows behind the good cubes can have any color. The idea in here is to have a variable

**front**which will be the number of cubes on the front of the current cell. For the first cell, there are no cubes on the front of it. If there are

**front**cells on the front, then we can place

**bad**cubes as long as their height positions are less than or equal to

**front**. We can also place

**good**cubes in a height position less than or equal to

**front**AND also add new ones which will increase the

**front**value for the next cells. This was something I have overlooked during the match. Also , for the cubes that are covered by the stacks from the previous cells, we can pick any order, which is important when there are

**good**and

**bad**cubes bellow the

**front**margin.

From the last paragraph: If the previous cells on front of the current one have a stack of size

**front**and we decided to pick

**v**bad cubes and

**u**good cubes to place in the current cell. Then

**v**cannot exceed

**front**, else a bad cube would be visible. The number of ways to place the cubes in this cell is Combinations( min(

**front**,

**u**+

**v**),

**v**) , because you can only pick locations smaller than or equal to

**front**for the bad cubes. Then the number of good and bad cubes decreases whilst

**front**may increase to

**u**+

**v**if it is larger (a new size of the stack). All of this is helpful when making a second recursion which is also memoization-friendly.

The total complexity is around O(A

^{5}*N) where A is the sum of R+G+B. It barely gets 1.8 seconds in c++, so I am not sure if there is a better solution.

typedeflonglongint64;constintMOD=1000000007;structCubeBuilding{

intN;

int64 mem[26][51][26];

int64 mem2[26][51][107][26];

int64 C[101][101];

int64 G(inta,intb,intfront,intn){

//Returnsthenumberofwaystoplacea+bcubesin

//ncellsifthelargeststackinacellonfrontof

//themhassizefront.Suchthatonlytheacubes

//arevisible.

//

int64&res=mem2[a][b][front][n];

if(res==-1){

res=0;

if(n==0){

if(a==0&&b==0){

res=1;

}

}else{

for(intv=0;v<=front&&v<=b;v++){

for(intu=0;u<=a;u++){

int64 y=C[std::min(front,u+v)][v];

res+=(y*G(a-u,b-v,std::max(front,v+u),n-1))%MOD;

}

}

res%=MOD;

}

}

returnres;

}

int64 F(intgood,intbad,intp){

//Returnsthenumberofwaystoplacegood+badcubesin

//allrows>=pofaNxNboardsuchthatonlythegood

//cubesarevisible

//

int64&res=mem[good][bad][p];

if(res==-1){

res=0;

if(p==N){

if(good==0&&bad==0){

res=1;

}else{

res=0;

}

}else{

res=0;

//placecubes..

for(intu=0;u<=good;u++){

for(intv=0;v<=bad;v++){

int64 tot=G(u,v,0,N)*F(good-u,bad-v,p+1);

res=(res+tot)%MOD;

}

}

res%=MOD;

}

}

returnres;

}

intgetCount(intR,intG,intB,intN)

{

//PreparecombinationstableusingPascal'striangle

memset(C,0,sizeof(C));

for(intn=0;n<=100;n++){

C[n][0]=1;

for(intk=1;k<=n;k++){

C[n][k]=C[n-1][k-1]+C[n-1][k];

while(C[n][k]>=MOD){

C[n][k]-=MOD;

}

}

}

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

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

this->N=N;

int64 res=0;

//Redonfront:

res+=F(R,G+B,0)*C[G+B][G];

//Blueonfront:

res+=F(B,G+R,0)*C[G+R][G];

//Greenonfront:

res+=F(G,R+B,0)*C[R+B][R];

return(int)(res%MOD);

}};

**Challenge phase**

What saved me was a lucky challenge. I found a person that in his 250 solution had something like: if ( number of unique colors >= 4 ) return "YES". At first I thought it was all right, but then I noticed a case with 3 repetitions of the same color and other 3 different colors. There are 4 distinct colors in total, but it is still impossible to do it.

The end result was a increment of 11 rating points, which is fine. But I need to return back to getting steady increases in the next match , if I want to defeat my maximum rating.

## 3 comments :

500 pointer was fun. After wasting a hour thinking, 5 minutes before intermission phase I understood that it can be solved with brute force. At the end of intermission phase I had the solution, but testing it in practice room (when practice rooms appeared) showed that I had integer overflow.

C++ provides easier than std::map way for 250. Just sort the array and remove elements that are equal to two preceding elements. :)

Best STL I have found so far for the 250 is :

set st(all(sticker));

int av = 0;

for_each(q, st) av += min(2, count(*q, all(sticker)));

return av>=6 ? "YES": "NO";

Lots of people got challenged in the 250 points :p, I am on div2 it was the 500 there.. it was a nice srm and I almost got to the div1 :)

I am following now the blog for editorials for the tc matches :D the explanations are great!

By the way, anyone could help me on this UVa problem?

http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=1100

I get only WAs :/

Post a Comment