I have not updated this site anymore. So please visit my new blog
Alim is here
Post3
#include <stdio.h>
#define max(a,b) (a>b)?a:b
int sum[100][100];
int inf = 1<<25;
int SUM(int si,int sj,int ei,int ej)
{
int res = sum[ei][ej];
if(sj-1>=0)
res-=sum[ei][sj-1];
if(si-1>=0)
res-=sum[si-1][ej];
if(si-1>=0&&sj-1>=0)
res+=sum[si-1][sj-1];
return res;
}
int main()
{
int i,j,y,x,N,M,m,c;
char buffer[100];
scanf("%d",&c);
getchar();
getchar();
while(c--)
{
N = 0;
M = 0;
while(gets(buffer)&&buffer[0])
{
for(M=0;buffer[M];M++)
sum[N][M]=buffer[M]-'0';
N++;
}
for(i=0;i<N;i++)
for(j=1;j<M;j++)
sum[i][j]+=sum[i][j-1];
for(i=0;i<M;i++)
for(j=1;j<N;j++)
sum[j][i]+=sum[j-1][i];
m = 0;
for(i=0;i<N;i++)
for(j=0;j<M;j++)
for(y=i;y<N;y++)
for(x=j;x<M;x++)
if(SUM(i,j,y,x)==(y-i+1)*(x-j+1))
m = max(m,(y-i+1)*(x-j+1));
printf("%d\n",m);
if(c)
putchar('\n');
}
return 0;
}
CODE
#include<bits/stdc++.h>
using namespace std;
int a[105][105],cu[105][105];
int main()
{
int i,j,k,n,m,d,test;
cin>>test;
getchar();
getchar();
while(test--)
{
i=0;
while(1)
{
i++;
string s;
getline(cin,s);
if(s=="") break;
n=s.size();
for(j=0;j<n;j++)
{
if(s[j]=='0') a[i][j+1]=-100001;
else a[i][j+1]=1;
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
cu[i][j]=cu[i][j-1]+a[j][i];
}
long long max_sum=0,sum;
for(i=1;i<=n;i++)
{
for(j=i;j<=n;j++)
{
sum=0;
for(k=1;k<=n;k++)
{
sum=sum+cu[k][j]-cu[k][i-1];
if(sum<0) sum=0;
max_sum=max(sum,max_sum);
}
}
}
long long final_max_sum=max_sum;
max_sum=0;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(a[i][j]==0) a[i][j]=1;
else a[i][j]=-100001;
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
cu[i][j]=cu[i][j-1]+a[j][i];
}
for(i=1;i<=n;i++)
{
for(j=i;j<=n;j++)
{
sum=0;
for(k=1;k<=n;k++)
{
sum=sum+cu[k][j]-cu[k][i-1];
if(sum<0) sum=0;
max_sum=max(sum,max_sum);
}
}
}
final_max_sum=max(max_sum,final_max_sum);
cout<<final_max_sum<<endl;
if(test) puts("");
}
return 0;
}
Efficient Way to Find Sum of Divisor(SOD)
Imagine you wish to work out the sum of divisors of the number 72. It would not take long to list the divisors, and then find their sum: 1 + 2 + 3 + 4 + 6 + 8 + 9 + 12 + 18 + 24 + 36 + 72 = 195.
However, this method would become both tedious and difficult for large numbers like 145600. Fortunately, there is a simple and elegant method at hand.
Let σ(n) be the sum of divisors of the natural number, n.
For any prime, p: σ(p) = p + 1, as the only divisors would be 1 and p.
Consider pa: σ(pa) = 1 + p + p2 + … + pa (1).
Multiplying by p: pσ(pa) = p + p2 + p3 + … + pa + 1 (2).
Subtracting (1) from (2): pσ(pa)−σ(pa) = (p−1)σ(pa) = pa+1 − 1.
Hence σ(pa) = (pa+1 − 1)/(p − 1).
For example, σ(34)=(35−1)/(3−1) = 242/2 = 121,
and checking: 1 + 3 + 9 + 27 + 81 = 121.
Although no proof is supplied here, the usefulness of the function, σ(n), is its multiplicity, which means that σ(a×b×…)=σ(a)×σ(b)×…, where a, b, …, are relatively prime.
Returning to example, we use the fact that σ(72) = σ(23×32). As 23 and 32 are relatively prime, we can separately work out σ(23) = 24 − 1 = 15 and σ(32) = (33 − 1)/2 = 13. Therefore, σ(72) = 15×13 = 195.
Related Problem: Lightoj-1054
Uva-12455 – Bars
UVA-12455
তোমাকে আমি চারটি লাঠি দিলাম। ধর লাঠিগুলোর দৈর্ঘ্য ২৫,১৫,১০,৮ সেঃমিঃ। আর তোমাকে যদি বলি ১৮ দৈর্ঘ্যের একটি লাঠি বানানো সম্ভব কিনা? তুমি তো সাথে সাথে মনে মনে ভাববে এটা তো class two এর বাচ্চাকে বলতে পারতেন!! ( সামনাসামনি তো আর বলতে পারবে না!! ) আর তক্ষুনি তুমি একটা superglue আঠা দিয়ে ১০ ও ৮ দৈর্ঘ্যের লাঠি দুটো জোড়া মেরে আমার হাতে ধরিয়ে দেবে। কিন্তু তোমাকে যদি ২০০ টা লাঠি ( ভিন্ন ভিন্ন দৈর্ঘ্যের ) দিয়ে বলি p দৈর্ঘ্যের একটা লাঠি তৈরি করা সম্ভব কিনা? এখন পালাবে কোথায় বাছাধন! p অবশ্যই সবগুলো লাঠি যোগ করলে যে দৈর্ঘ্য হবে তার সমান বা ছোট হবে।
একটু চিন্তা কর কিভাবে এই problem টা solve করা যায়। তোমাকে ১৫ মিঃ সময় দিলাম।
আসলে এটা একটা DP এর কেরামতি। DP দুটি প্রধান Characteristics হলঃ ( Top-Bottom Dynamic Programming এর ক্ষেত্রে )
(১) Latest Value কে বের করার জন্য Previous Value কে Use করা।
(২) Problem এ অবশ্যই at least একটা উত্তর তোমার জানা থাকতে হবে।( Base Case)
আচ্ছা বলতো এই Problem এ জানা উত্তর টা কি? জানা উত্তর টা হল 0 দৈর্ঘ্যের একটা লাঠি তৈরি করা সম্ভব কিনা এর উত্তর সবসময় Yes. অনেক DP Problem এর ক্ষেত্রে এই জানা উত্তর টা খুবই গুরুত্বপূর্ণ ।
যেমন LCS(Longest Common Sub-sequence).
ধরি, আমাদের চারটি লাঠি আছে। ৪,৫,২,৯ সেঃমিঃ । বলা হল ১১ দৈর্ঘ্যের লাঠি তৈরি করা সম্ভব কিনা?
আচ্ছা বলতো সবচেয়ে কত বড় দৈর্ঘ্যের লাঠি তৈরি করা সম্ভব? ৪+৫+২+৯=২১
তার মানে, 0 থেকে ২১ দৈর্ঘ্যের মধ্যে Fixed কোন কোন দৈর্ঘ্যের জন্য লাঠি তৈরি করা সম্ভব আমাদের সেটাই বের করতে হবে।
আমরা একটা Array Use করব। নাম দিলাম identifier[i] .এর মান হবে কেবল 0 অথবা ১
i তম Value-র মান 0 মানে i দৈর্ঘ্যের লাঠি তৈরি করা সম্ভব না। আর i তম Value-র মান ১ মানে i দৈর্ঘ্যের লাঠি তৈরি করা সম্ভব।
প্রথমে ধরি একটা দৈর্ঘ্যের জন্যও লাঠি তৈরি করা সম্ভব না। তাহলে,
for(i=0;i> এই ধাপে প্রথম লাঠির দৈর্ঘ্য 4সেঃমিঃ।
>> Previous Information(Before this step): 0 দৈর্ঘ্যের জন্য লাঠি তৈরি সম্ভব অর্থাৎ identifier[0]=1;
>>Updated Information(In this step): 0+4=4 দৈর্ঘ্যের জন্য লাঠি তৈরি সম্ভব অর্থাৎ identifier[4]=1;
*Grand Information(After processing this step):
identifier[0]=1;
identifier[4]=1;
Step-2
>> এই ধাপে প্রথম লাঠির দৈর্ঘ্য 5সেঃমিঃ।
>> Previous Information(Before this step): 0,4 দৈর্ঘ্যের জন্য লাঠি তৈরি সম্ভব অর্থাৎ identifier[0]=1;
identifier[4]=1;
>>Updated Information(In this step): 0+5=5,4+5=9 দৈর্ঘ্যের জন্য লাঠি তৈরি সম্ভব অর্থাৎ identifier[5]=1;
identifier[9]=1;
*Grand Information(After processing this step):
identifier[0]=1;
identifier[4]=1;
identifier[5]=1;
identifier[9]=1;
Step-3
>> এই ধাপে প্রথম লাঠির দৈর্ঘ্য 2সেঃমিঃ।
>> Previous Information(Before this step): 0,4,5,9 দৈর্ঘ্যের জন্য লাঠি তৈরি সম্ভব অর্থাৎ
identifier[0]=1;
identifier[4]=1;
identifier[5]=1;
identifier[9]=1;
>>Updated Information(In this step): 0+2=2,4+2=6,5+2=7,9+2=11 দৈর্ঘ্যের জন্য লাঠি তৈরি সম্ভব অর্থাৎ
identifier[2]=1;
identifier[6]=1;
identifier[7]=1;
identifier[11]=1;
*Grand Information(After processing this step):
identifier[0]=1;
identifier[4]=1;
identifier[5]=1;
identifier[9]=1;
identifier[2]=1;
identifier[6]=1;
identifier[7]=1;
identifier[11]=1;
Step-4
>> এই ধাপে প্রথম লাঠির দৈর্ঘ্য 9সেঃমিঃ।
>> Previous Information(Before this step): 0,4,5,9,2,6,7,11 দৈর্ঘ্যের জন্য লাঠি তৈরি সম্ভব অর্থাৎ
identifier[0]=1;
identifier[4]=1;
identifier[5]=1;
identifier[9]=1;
identifier[2]=1;
identifier[6]=1;
identifier[7]=1;
identifier[11]=1;
>>UpdatedInformation(In this step): 0+9=9,4+9=13,5+9=14,9+9=18,2+9=11,6+9=15,7+9=16,11+9=20 দৈর্ঘ্যের জন্য লাঠি তৈরি সম্ভব অর্থাৎ
identifier[9]=1;
identifier[13]=1;
identifier[14]=1;
identifier[18]=1;
identifier[11]=1;
identifier[15]=1;
identifier[16]=1;
identifier[20]=1;
*Grand Information(After processing this step):
identifier[0]=1;
identifier[4]=1;
identifier[5]=1;
identifier[9]=1;
identifier[2]=1;
identifier[6]=1;
identifier[7]=1;
identifier[11]=1;
identifier[9]=1;
identifier[13]=1;
identifier[14]=1;
identifier[18]=1;
identifier[11]=1;
identifier[15]=1;
identifier[16]=1;
identifier[20]=1;
তাহলে যে যে দৈর্ঘ্যের জন্য লাঠি তৈরি করা সম্ভব টা হলঃ
0,2,4,5,6,7,9,11,13,14,15,16,18,20
কেউ যদি জানতে চায় m দৈর্ঘ্যের লাঠি তৈরি করা সম্ভব কিনা, তাহলে identifier[m] এর মান যদি ১ হয় তাহলে সম্ভব , যদি 0 হয় তাহলে সম্ভব নয়।
আশা করি Problem এর Base টা তোমাদের Clear হয়েছে। তাহলে আর দেরি না করে ঝটপট এই প্রবলেম টা Solve করে ফেলো। UVA 12455 এবং UVA 562
এই পোস্টটি যদি পুরপুরি না বুঝতে পার তাহলে কোথায় বুঝলেনা আমাকে জানাতে পারো। তারপরও যদি না পারো তাহলে “Solution” এই Menu তে Code দেখতে পারবে। তবে ভালভাবে না বুঝে Code দেখা ঠিক হবেনা।
এই পোস্টটি PDF Format এ Download
Uva-674 – Coin Change
Short Problem Description:
Given the 5 coins 1,5,10,25,30 and an amount( assume, taka). You have to find the number of ways the amount can be made using these 5 coins.
Solution Approach:
This is an easy dp problem. So try to find overlapping sub-problem,
recurrence relation and also base case. This is a common technique to solve a dp problem.
In this problem I will try to find these…At first I declare a function f(i,j) which returns the number of ways of j taking first i coins.
Now,
f(i,j)=0, if i==0 base case
f(i,j)=1, if j<5 base case
f(i,j)=f(i-1,j) ,if(j-coin[i])=0 recurrence relation
Problem Link: Click Here
My Code: Click Here
Uva-10450 – World Cup Noise
Short Problem Description:
Given n. You have to output how many bit string of length n is possible so that no consecutive 1 exists. As for example, if n=3, then there are total 2^3=8 bit string possible. They are 000, 001, 010, 011, 100, 101, 110, 111. But among these 011, 110, 111 have the bit string with consecutive 1. So answer is 8-3=5.
Solution Trick:
The logic of this problem goes to Tree Diagram. Simply try to draw a tree with 0 and 1 so that no consecutive 1 remains together. Then see, the logic is just Fibonacci Series.
My Code: Click Here
Uva-10003 – Cutting Sticks
Solution Trick:
The problem goes to the simple Dynamic Programming. Just divide the problem into similar subproblems and write an efficient code. Actually,
for dp problem idea is very important for solving. So try to develop your own Algorithm.
My Code: Click Here
Problem-16(Power digit sum)
215 = 32768 and the sum of its digits is 3 + 2 + 7 + 6 + 8 = 26.
What is the sum of the digits of the number 21000?
Solution Trick:
The logic goes to childhood multiplication process. What can we do when we want to multiply a big number a( such as a=9999999999999) by a number b (such as b=2 ) . We continuously multiply the rightmost digit of a by b until we reach the leftmost digit of a.
My Solution: Click Here
Alim's Blog 