# SDICE - Editorial

Author & Editorialist : Shruti Agrawal
Testers : Shubham Jain, Aryan Choudhary

SIMPLE

# PREREQUISITES:

Implementation, Modulus, Math

# PROBLEM:

Chef has N 6-sided standard dice. Each die has dimensions 1×1×1. First, Chef forms four vertical stacks of dice on his table, which together make up a pile of dice with a base area up to 2×2. Among all such structures, the total visible surface area of Chef’s structure must be the smallest possible.

Then, Chef calculates the number of pips on the visible faces of all dice in the structure. Among all possible arrangements of dice, what is the maximum possible total number of visible pips?

# QUICK EXPLANATION:

For minimum visible area, dice should be stacked together, 4 dice in a level.
If 4 is not possible then arranged as such they share a face to minimize the visible surface area.
Each dice must be kept in such a way that the faces with more pips are visible.

# EXPLANATION:

For minimum visible area, dice should be stacked together, 4 dice in a level.
Only at the topmost level, it can be less than 4 dice, or only if N<4.

In other words, if there are N dice then floor(N/4) levels would be there with 4 dice at each level.
if N%4 != 0, then there would be a level with less than 4 (i.e. N%4) dice.

In the top tier, the dice should be arranged as such they share a face with each other for minimizing the visible surface area.

For any dice,
if 5 faces are visible, then the values should be 6, 5, 4, 3, 2.
if 4 faces are visible, then the values should be 6, 5, 4, 3.
if 3 faces are visible, then the values should be 6, 5, 4.
if 2 faces are visible, then the values should be 6, 5.

For example,
If N = 4, then the number of visible faces in each dice is 3. So, the total number of pips in the structure would be 4*(6+5+4), which is equal to 60.

N = 2 N = 3 N = 4

N = 5 N = 6 N = 8

N = 9 N = 10 N = 11

# SOLUTIONS:

Setter's Solution
``````#include<bits/stdc++.h>
using namespace std;
#define ll long long int

int main(){

int i,j,k,t;
cin>>t;

while(t--){
ll n;
cin>>n;

ll ans=0;
if(n%4==1){
ans=20;
}
if(n%4==2){
ans=36;
}
if(n%4==3){
ans=51;
}
ll times=n/4LL;
ans+=times*44LL;

if(times>=1){
ans+=(4LL*(ll)(4-n%4));
}
cout<<ans<<"\n";
}
return 0;
}
``````
Tester's Solution
``````//Author - Aryan (@aryanc403)

#ifdef ARYANC403
#else
#pragma GCC optimize ("Ofast")
#pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
//#pragma GCC optimize ("-ffloat-store")
#include<bits/stdc++.h>
#define dbg(args...) 42;
#endif

using namespace std;
#define fo(i,n)   for(i=0;i<(n);++i)
#define repA(i,j,n)   for(i=(j);i<=(n);++i)
#define repD(i,j,n)   for(i=(j);i>=(n);--i)
#define all(x) begin(x), end(x)
#define sz(x) ((lli)(x).size())
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define endl "\n"

typedef long long int lli;
typedef long double mytype;
typedef pair<lli,lli> ii;
typedef vector<ii> vii;
typedef vector<lli> vi;

const auto start_time = std::chrono::high_resolution_clock::now();
void aryanc403()
{
#ifdef ARYANC403
auto end_time = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> diff = end_time-start_time;
cerr<<"Time Taken : "<<diff.count()<<"\n";
#endif
}

long long readInt(long long l, long long r, char endd) {
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true) {
char g=getchar();
if(g=='-') {
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g&&g<='9') {
x*=10;
x+=g-'0';
if(cnt==0) {
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);

assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd) {
if(is_neg) {
x=-x;
}
assert(l<=x&&x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l, int r, char endd) {
string ret="";
int cnt=0;
while(true) {
char g=getchar();
assert(g!=-1);
if(g==endd) {
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt&&cnt<=r);
return ret;
}
long long readIntSp(long long l, long long r) {
}
long long readIntLn(long long l, long long r) {
}
string readStringLn(int l, int r) {
}
string readStringSp(int l, int r) {
}

assert(getchar()==EOF);
}

vi a(n);
for(int i=0;i<n-1;++i)
return a;
}

const lli INF = 0xFFFFFFFFFFFFFFFL;

lli seed;
inline lli rnd(lli l=0,lli r=INF)
{return uniform_int_distribution<lli>(l,r)(rng);}

class CMP
{public:
bool operator()(ii a , ii b) //For min priority_queue .
{    return ! ( a.X < b.X || ( a.X==b.X && a.Y <= b.Y ));   }};

void add( map<lli,lli> &m, lli x,lli cnt=1)
{
auto jt=m.find(x);
if(jt==m.end())         m.insert({x,cnt});
else                    jt->Y+=cnt;
}

void del( map<lli,lli> &m, lli x,lli cnt=1)
{
auto jt=m.find(x);
if(jt->Y<=cnt)            m.erase(jt);
else                      jt->Y-=cnt;
}

bool cmp(const ii &a,const ii &b)
{
return a.X<b.X||(a.X==b.X&&a.Y<b.Y);
}

const lli mod = 1000000007L;
// const lli maxN = 1000000007L;

lli T,n,i,j,k,in,cnt,l,r,u,v,x,y;
lli m;
string s;
const vi a={0,20,36,51,60,20+44+12,36+44+8,51+44+4,60+44};
//priority_queue < ii , vector < ii > , CMP > pq;// min priority_queue .

int main(void) {
ios_base::sync_with_stdio(false);cin.tie(NULL);
// freopen("txt.in", "r", stdin);
// freopen("txt.out", "w", stdout);
// cout<<std::fixed<<std::setprecision(35);
dbg(a);
while(T--)
{
if(n<=8)
cout<<a[n]<<endl;
else
{
const lli l=(n/4)-1;
n&=3;n+=4;
cout<<a[n]+l*44<<endl;
}
}   aryanc403();
return 0;
}
``````
6 Likes

When there are two dice, one can place those two dice diagonally resulting in 5 sides of each dice exposed. This give us total sum of 40 (20 on each dice).
Can anyone explain, why 36 is answer for such situation.

Placing the dice diagonally results in more visible surface area.

1 Like

First, we had to minimize the visible area and then calculate the total number of pips.

for 1 dice visible faces = 6+5+4+3+2 =20
for 2 dices visible faces = 2 * 6+2 * 5+2 * 4+2 * 3 = 36
for 3 dices visible faces = 3 * 6+3 * 5+3 * 4+2 * 3=51
for 4 dices visible faces = 4 * 5+4 * 6+4 * 4 = 60
but for 5 th dice which will placed on 2 layer, the total visible faces should be = 4 * 5+4 * 4+4 * 6+5+4+3+2=74 why tester solution shows 76 am I missing something?

My solution

For five dice, visible faces are 4,5,6 of 2nd,3rd,4th dice and 5,6 of 1st die and 2,3,4,5,6 of the fifth die. so total sum is (4+5+6)*3+(5+6)*1+20=45+11+20=76

1 Like

In the case of two dice, you place them side by side such that 1 of both die touches the ground and 2 touches each other. so visible pips are 3,4,5,6 of both dice. Therefore, the sum is (3+4+5+6)*2=36.

1 Like

although I was able to solve the question while the contest was on, I still found the editorial good. It made me visualize a lot more clearly.

1 Like

I think this analysis is incorrect since opposite faces of 6-sided standard dice always add up to 7. So when 4 dices are placed together as shown in the image, the exposed faces should be:
[6,5,4] [6,5,3]
[6,5,3] [6,5,4]

Can someone please correct me if I am wrong somewhere?

When you put 2 dice [Dice A, Dice B] together by joining the 2 pip faces, each dice will mirror each other across the face 2. This means 3s and 4s of the 2 dice are not aligned together. Now when you add 2 more dice [Dice C, Dice D] to it, Face 3 of Dice A will be hidden and Face 4 of the dice B will be hidden or vice versa depending on to which side you add Dice C and D. So for Dice A visible faces will be [6,5,4] and for B, visible faces will be [6,5,3]. Similar will be the case for Dice C and D. So I don’t think standardizing faces as [6,5,4] when 3 faces are visible is correct.

The analysis given in the editorial would be correct if faces of the dice can be moved around to maximize the pips exposed which would fail the ‘6-Sided Standard Dice’ part or the Dice are not identical which then fails to be a standard considering all the Dice are in the same Environment.

No, the analysis is indeed correct, you can always get
[6,5,4] [6,5,4]
[6,5,4] [6,5,4]
on the exterior edges of a 4 dice case.
I’ll try to make a figure here, the numbers you see are the numbers on the visible three sides which would be seen when you place the 4 dices adjacent to each other.

1 Like

yo

Got it! Thanks a ton. What I was doing is keep adding to the existing structure. What needs to be done is re-arrange to always expose the maximum on each die. Much clearer from the image you shared.

1 Like

Great Editorial!!!

1 Like

For 4 dice it would be => (4 * 6 + 4 * 5 + 4 * 4) => 60
For 5 dice it would be => (4 * 6 + 4 * 5 + 4 * 4) - 4(since there would be die stacked on top of 4) + 20(6 + 5 + 4 + 3 +2)
Please do take care that we have find the sum of maximum pips possible so you we have to manipulate accordingly.
in your case you missed to take 6 for the top die. rather than doing 4 * 5 + 4 * 4 + 4 * 6 + 5 + 4 + 3 + 2 + 1
try this (4 * 6 + 4 * 5 + 4 * 4) - 4(since there would be die stacked on top of 4) + 20(6 + 5 + 4 + 3 +2)
I hope that you got where you went wrong.

can anyone tell me why in this code 44 is multiplied with p?

using namespace std;

int main()
{
long int t;
cin>>t;
for(long int i=0;i<t;i++){
long int n,p=0,q;
cin>>n;
if(n==1)
{
cout<<“20\n”<<"\n";
}
else if(n==2)
{
cout<<“36\n”<<"\n";
}
else if(n==3)
{
cout<<“51\n”<<"\n";
}
else if(n==4){
cout<<“60\n”<<"\n";
}

``````else if(n>4){
p=n/4;
q=n%4;
p=p*44;
if(q==0)
{
cout<<p+16<<"\n";
}
else if(q==1)
{
cout<<p+32<<"\n";
}
else if(q==2)
{
cout<<p+44<<"\n";
}
else if(q==3)
{
cout<<p+55<<"\n";
}}
}
return 0;
``````

}

But here minimum surface area would be when only one stack of dice is made then why didn’t we consider that

Ttamimjd, Because total pips visible for each level except the topmost level will be (6+5)*4.
6+5 because only 2 faces wil be visible for each dice. & Multiplied by 4 because at a level all 4 dices will have same no of visible pips.so 6+5 for 1 dice * 4 for 4 dices at a level…
Hence (6+5)4= 114=44 pips visible at each level from level 1 till second topmost level.

li = [0 , 20 , 36 , 51 , 60]
re = {1:16 , 2:12 , 3:11 , 0:5}

def solve(N):
sum = li[4]
if N<=4:
return li[N]

``````for i in range(5,N+1):
r = i%4
sum+=re[r]
return sum
``````

T = int(input())
while T>0:
n = int(input())
print(solve(n))
T-=1

I am trying to express N as a and b
N= 4*a+b
b is in range [0,8].

I am precalculating the answer till 8 dices and for greater than 8 we just add 4*a.
Calculating a and b becomes the real problem.

Which I solve here
https://www.codechef.com/viewsolution/44934074

But I get wrong answer for N>8.

Any help will be appreciated.
Thanks.

}