×

# INOI 2012 Problem 2 TableSum

 0 Hi. I tried to solve the second problem of INOI 2012, Table Sum with the native approach (or the bruteforce way) as I'm not able to think of any other way in which we could attempt the problem. After looking at a few outputs, I thought there might be some kind of pattern in the output but couldn't find any. Any aid would be very helpful as I'm preparing for INOI 2015 and have almost no experience in algorithmic programming. I started practicing almost a week after ZIO results were out :[ Here is my code (its in java, sorry about that):  import java.io.*; import java.util.Scanner; public class TABLESUM { public static Scanner in = new Scanner(System.in); public static PrintWriter pw = new PrintWriter(System.out); public static void main(String[] args) throws IOException { int n = in.nextInt(); int[] ar = new int[n]; int[] def = new int[n]; for (int i = 0; i < n; i++) { ar[i] = in.nextInt(); } for (int i = 0; i < n ; i++) { def[i] = i+1; } for (int i = 0; i < n; i++) { tableSum(ar, def); nextPerm(def); } } public static int[] nextPerm (int[] a) { int first = a[0]; for (int i = 0; i < a.length; i++) { if (i == a.length-1) { a[i] = first; }else { a[i] = a[i+1]; } } return a; } public static void tableSum (int[] a, int[] b) { int max = 0; for (int i = 0; i < a.length; i++) { if (a[i] + b[i] > max) { max = a[i] + b[i]; } } pw.print(max + " "); pw.flush(); } }  asked 31 Dec '14, 00:22 1★pm1511 31●5●6 accept rate: 0% link to problem statement? (31 Dec '14, 00:40) mogers5★ (31 Dec '14, 00:52) pm15111★

 1 There is also a O(n) algorithm to solve this question. Instead of modifying all the column sums, we can decrease the one column sum by N, and then take the maximum column sum plus 1 to find the new maximum of the column sums. So we only need to update one column instead of all of them. You can find a detailed explanation of this question at this link: Table Sum answered 31 Dec '14, 01:07 883●1●4●22 accept rate: 9% I wrote the above code based on the O(n) algo you suggested, but I am getting WA on all except 3 test cases. Where could I be going wrong? (31 Dec '14, 14:55) sandy9992★ 1 Hey try this code . Where to submit this up .. http://ideone.com/vaGrJ6 I have a post full explanation below you can check and may you find it useful for you .. (31 Dec '14, 15:22)
 0 I insist you do it by segment trees Just make a segment tree and then call 3 updates using lazy propagation and then just call query for each n and you are done. Time complexity O(nlogn) answered 31 Dec '14, 11:09 5★japoorv 295●9●23●56 accept rate: 0%
 0 Hello all Can anybody of you tell me where i can submit this problem .. I am unable to find Online judge where i can submit this problem . Thanx in advance . answered 31 Dec '14, 18:52 1★mhungry 62●2 accept rate: 18% @pm1511 Can you please check this submissionon my behalf .. http://ideone.com/vaGrJ6 and tell me result .. (31 Dec '14, 20:06) mhungry1★ @mhungry Well, you got a 100 ;) (31 Dec '14, 20:37) pm15111★ @mhungry Did you read the solution above first or did you solve the problem on your own? (31 Dec '14, 20:41) pm15111★ I read what is mentioned by ma5termind. Even the code is same . (31 Dec '14, 20:54) mhungry1★ @mhungry Can you please explain me the code with reference to the above answer? I'm not able to match the code with what he said in the answer... (01 Jan '15, 19:58) pm15111★
 0 I did it by your method and it still gives me TLE for the problem (2 sec+) Could you please explain my error here? Why is it going wrong? #include #include #define big unsigned long long int using namespace std; /* code */ big maxScan(vector noob) { ios_base::sync_with_stdio(false); big maxn=0; for (int y=0; ymaxn) maxn=noob[y]; return maxn; } int main() { ios_base::sync_with_stdio(false); big n; cin>>n; vector nums, lastsum; for (int i=0; i>l; lastsum.push_back(i+1+l); } // vector nat; // for (int i=0; i lastsum; // for (int i=0; i temp; for (int i=1; i<=n; i++) { // temp=lastsum; // for (int j=0; j
 0 @aalok_sathe you have not used my logic i think .. #include using namespace std; #define MAXN 200005 int N,A[MAXN] ; int main() { // your code goes here cin >> N ; for(int i=1;i<=N;i++) cin >> A[i] ; for(int i=1;i<=N;i++){ A[i] += i; A[i] = max(A[i],A[i-1]) ; } cout << A[N] << " " ; int cnt = 0; for(int i=N;i>1;i--){ A[i] -= N ; A[i] = max(A[i],A[i+1])+1 ; ++cnt ; A[i-1] += cnt ; cout << max(A[i],A[i-1]) << " " ; } cout << endl ; return 0; }  this was my code for this problem. I can see in your code that you are using two loops . `for (int i=1; i<=n; i++) { // temp=lastsum; // for (int j=0; j
 0 Okay so you sort it linearly each iteration and compare by removing n-1 from (n-i)th position. Understood. thanks! answered 29 Jan '15, 10:33 17●2●4 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×399
×75

question asked: 31 Dec '14, 00:22

question was seen: 3,628 times

last updated: 26 Dec '18, 23:49