| ENG RUS | Timus Online Judge |
Discussion of Problem 1073. Square Countryirinaguseva Some tips // Problem 1073. Square Country 13 Nov 2021 00:26 The most important idea for this task is the fact that according to Lagrange’s Four Square Theorem, every natural number can be written as the sum of squares of four non-negative integers. Good luck, hope this will help! Edited by author 13.11.2021 00:26 Edited by author 13.11.2021 00:26 Search Please give me some tests.Thank in advance!!!! [1] // Problem 1073. Square Country 19 Aug 2008 02:18 I don't understand problem,please give me some tests.Thank!!!!!! Yaroslav Balahonov Re: Please give me some tests.Thank in advance!!!! // Problem 1073. Square Country 13 May 2021 16:11 Here are some tests ~~~~~~~~~~~~ 11995=3 11996=4 11997=3 11998=3 11999=4 12000=3 12001=3 12002=2 12003=3 ~~~~~~~~~~~~~~ 23402=2 23403=3 23404=3 23405=3 23406=3 23407=4 23408=4 23409=1 23410=2 23411=3 ~~~~~~~~~~~~~~ 59989=3 59990=3 59991=4 59992=3 59993=2 59994=3 59995=3 59996=4 59997=3 59998=3 59999=4 60000=3 HowieMa How could we solve this problem by DP? [2] // Problem 1073. Square Country 4 Mar 2017 19:10 We could solve it by Theorem on the sum of four squares, I wonder how to solve it by DP? If you know, please help me, thank you! Mewtwo Re: How could we solve this problem by DP? // Problem 1073. Square Country 4 Mar 2017 23:17 HowieMa wrote 4 March 2017 19:10 We could solve it by Theorem on the sum of four squares, I wonder how to solve it by DP? If you know, please help me, thank you! Well... For n=72... what are the possible squares you can take? You can take 64,49,36,25...4,1 . So what's the best result for 72? The best result Best(72)=min(Best(72-64),Best(72-49),Best(72-36), ... Best(72-1))+1; Now whats the base cases? U see, for all square numbers, u can take it in one go. So Best(1)=Best(4)=Best(9)=Best(16) ... = 1 Its a top down approach. I hope u got the idea... Goodluck. Btw, I'm wondering how u solved by Theorem on the sum of four squares. Can u send your code to my mail please? ealham86@gmail.com abid1729 Re: How could we solve this problem by DP? // Problem 1073. Square Country 29 Mar 2020 14:23 i solved it with dp. but i wondered with u.plz send me ur code. EMAIL:achowdhury@isrt.ac.bd Gopesh Tulsyan WA at test#5 [4] // Problem 1073. Square Country 21 Sep 2014 14:18 I am getting a WA at test #5 Here's my code : #include <iostream> using namespace std; int main(){ int n,i=1,count=0; cin>>n; while(n>0){ if(i*i<=n) i++; else{ n-=(i-1)*(i-1); i=1; count++; } } cout<<count<<endl; return 0 } frantrucco Re: WA at test#5 [2] // Problem 1073. Square Country 10 Feb 2015 12:43 Imagine you are given the following input: n=72. Given that 72 = 6*6 + 6*6 the answer should be 2, but your output is 3. This is happening because you are solving the problem using a greedy strategy. Here a greedy strategy does not work. If you want more information on why this technique does not work read chapter 15 and 16 of "Introduction to algorithms" by Cormen,Leiserson,Rivest and Stein. ইলহাম আল মুসাব্বির Re: WA at test#5 // Problem 1073. Square Country 24 Jul 2015 01:04 Thanks for the explanation... ^_^ V.Leo Re: WA at test#5 // Problem 1073. Square Country 29 Sep 2016 19:25 Thanks a lot~ Umarjon Re: WA at test#5 // Problem 1073. Square Country 5 Oct 2016 10:30 60000 Edited by author 05.10.2016 10:30 havij4 WA test 10 |: [1] // Problem 1073. Square Country 8 Nov 2014 13:10 Hi I got WA on test 10 |: I need some testcase! PLZ HELLLLLP MEEEE! :D Abbos Re: WA test 10 |: // Problem 1073. Square Country 29 Jul 2016 10:33 Test 10 is 60000 Erik Arakelyan(AUA) Same as the Coin Change Problem // Problem 1073. Square Country 17 Jun 2016 15:08 #include <iostream> #include <cmath> using namespace std; int minCoins(int coins[], int m, int V) { int table[V+1]; table[0] = 0; for (int i=1; i<=V; i++) table[i] = INT_MAX; for (int i=1; i<=V; i++) { for (int j=0; j<m; j++) if (coins[j] <= i) { int subResult = table[i-coins[j]]; if (subResult != INT_MAX && subResult + 1 < table[i]) table[i] = subResult + 1; } } return table[V]; } int main() { int V; cin>>V; int coins[1000]; int i; for(i=1;i<=sqrt(V);i++) { coins[i-1] = (i)*(i); } int m = sqrt(V); cout<< minCoins(coins, m, V)<<endl; return 0; } This problem can be translated to get the minimum amout of coins to get the value N.(We must just check that the coins are the actual square numbers). Grandmaster Tests and answers. // Problem 1073. Square Country 11 Feb 2016 18:04 i write the output and the square roots. Input 41 Answer 2 16 25 Input 51 Answer 3 1 1 49 Input 19 Answer 3 1 9 9 Input 102 Answer 3 1 1 100 Input 18467 Answer 3 25 6561 11881 Input 6334 Answer 3 25 225 6084 Input 26500 Answer 2 256 26244 Input 19169 Answer 2 400 18769 Input 15724 Answer 3 36 1764 13924 Input 11478 Answer 3 4 25 11449 Input 29358 Answer 3 4 5329 24025 Input 26962 Answer 2 1681 25281 Input 24464 Answer 3 64 64 24336 Input 5705 Answer 3 4 225 5476 Input 28145 Answer 2 256 27889 Input 23281 Answer 3 9 7396 15876 Input 16827 Answer 3 49 5329 11449 Input 9961 Answer 3 16 144 9801 There can be any solution but the number of square roots is unique ELDVN Help anybody // Problem 1073. Square Country 20 Dec 2015 23:22 Wheres my wrong? help pleas #include <bits/stdc++.h> const int maxn = (int)1e6; const int mod = (int)1e9 + 7; using namespace std; int n; int dp[maxn]={-1}; int calc(int n){ int res=n; dp[0]=0; if(dp[n] != -1) return dp[n]; for(int i=1; i*i <= n; i++){ res=min(res,1+calc(n-i*i)); } return dp[n]=res; } int main(){ scanf("%d",&n); printf("%d\n", calc(n)); return 0; } Edited by author 20.12.2015 23:27 mihai.alpha Test 4 Wrong Answer // Problem 1073. Square Country 11 Oct 2015 17:36 Edited by author 11.10.2015 17:44 Najmaddin Akhundov How to make this code faster?? Please, help [3] // Problem 1073. Square Country 13 Oct 2014 09:26 #include <iostream> #include <cmath> #include <algorithm> using namespace std; int function(int n) { if (n == 1) return 1; else if (n == 0) return 0; else{ int k = 999999999; for (int i = 1; i <= sqrt(n); i++) { int a = function(n - i*i); if (a < k ) k = min(k, a); } return function(k) + 1; } } int main() { int n; cin >> n; cout << function(n) << endl; } Noob Re: How to make this code faster?? Please, help [1] // Problem 1073. Square Country 13 Oct 2014 12:00 use memoization Najmaddin Akhundov Re: How to make this code faster?? Please, help // Problem 1073. Square Country 15 Oct 2014 15:36 Thank you Noob, I got an AC with your help. Paras Kumar Meena Re: How to make this code faster?? Please, help // Problem 1073. Square Country 12 Jul 2015 10:39 One optimization No need to start loop from always from 1 , sqrt(N)/2 is enough ;) thing why?. :) moshcode WA14 pls help // Problem 1073. Square Country 16 Dec 2014 16:01 my code: #include<iostream> #include<cmath> using namespace std; main() { unsigned int n,temp,nc; cin>>n; nc=n; temp=sqrt(n); if(n==0) cout<<0; else if(temp*temp==n) cout<<1; else { unsigned int x=-1,m=0,q=4,t; for(unsigned int i=temp;i>=1;i--) { t=i; while(x!=0) { x=n-t*t; n=x; t=sqrt(x); m++; } if(m<q) q=m; if(m==2) break; x=-1; m=0; n=nc; } cout<<q; } } Marius Žilėnas Hint // Problem 1073. Square Country 24 Oct 2013 16:46 Use Brute Force approach with Lagrange's four square theorem, but to short-cut do check only 1, 2, 3 case. If those do not give any squares then output 4 (see Lagrange's theorem). :) Hikmat Ahmedov Lagrange's four-square theorem and its implementation with AC solution in C# [1] // Problem 1073. Square Country 10 Mar 2012 05:01 Of course, Dynamic Programming solution is better. But for your info there is a theorem of Lagrange. Quote from Wikipedia "Lagrange's four-square theorem states that any natural number can be represented as the sum of four integer squares" http://en.wikipedia.org/wiki/Lagrange%27s_four-square_theorem Example, 3 = 1^2 + 1^2 + 1^2 + 0^2 31 = 5^2 + 2^2 + 1^2 + 1^2 310 = 17^2 + 4^2 + 2^2 + 1^2. Here is my C# code: using System; class Program { static void Main() { int n = int.Parse(Console.ReadLine()); for (int i1 = 0; i1 <= (int)Math.Sqrt(n); i1++) for (int i2 = 0; i2 <= (int)Math.Sqrt(n); i2++) for (int i3 = 0; i3 <= (int)Math.Sqrt(n); i3++) for (int i4 = 0; i4 <= (int)Math.Sqrt(n); i4++) if (i1 * i1 + i2 * i2 + i3 * i3 + i4 * i4 == n) { Console.WriteLine(Math.Sign(i1)+Math.Sign(i2)+Math.Sign(i3)+Math.Sign(i4)); return; } } } Marius Žilėnas Re: Lagrange's four-square theorem and its implementation with AC solution in C# // Problem 1073. Square Country 24 Oct 2013 15:37 it's not AC gogreen 1073 - square country // Problem 1073. Square Country 22 Apr 2013 22:15 Hello i wrote the following code in python , but it takes too much time, hwo should it be improved class timus1073: def __init__(self): pass def problem(self,y): a = [0] + range(1,60001) b = [x**2 for x in range(1,246)] for i in b: j = 0 while j+i <= 60000: if (a[j+i] > a[j] + 1): a[j+i] = a[j] + 1 j = j + 1 return a[y] if __name__ == "__main__": p = timus1073() a = input() print p.problem(int(a)) alexdeg why i have WA#1 [1] // Problem 1073. Square Country 11 Mar 2013 20:30 var fi,fv:text; chi,kolc: longint; procedure round_sqrt(a:longint; var kol:longint); var b:longint; begin b:=trunc(sqrt(a)); b:=b*b; a:= a-b; if a> 0 then begin kol:=kol+1; round_sqrt(a,kol); end else kol:=kol+1; end; begin assign(fi,'input.txt'); reset(fi); assign(fv,'output.txt'); rewrite(fv); {============} read(fi,chi); kolc:=0; if chi>0 then round_sqrt(chi,kolc); write(fv,kolc); {============} close(fi); close(fv); end. Kvark_161 Re: why i have WA#1 // Problem 1073. Square Country 30 Mar 2013 13:16 Don't use files. Only standart streams. Artem Ladik easy search [5] // Problem 1073. Square Country 8 Jul 2009 01:22 var i,j,k,n:longint; begin read(n); for i:=1 to 250 do if sqr(i)=n then begin write(1); exit; end; for i:=1 to 250 do for j:=1 to 250 do if sqr(i)+sqr(j)=n then begin write(2); exit; end; for i:=1 to 250 do for j:=1 to 250 do for k:=1 to 250 do if sqr(i)+sqr(j)+sqr(k)=n then begin write(3); exit; end; write(4); end. evjava Re: easy search [3] // Problem 1073. Square Country 23 Oct 2009 20:20 If N was bigger, you would have time limit. nguyenductam Re: easy search [2] // Problem 1073. Square Country 4 Apr 2010 18:14 I don't think so. My code got AC. #include<stdio.h> int i,j,k; long int n; int main() { scanf("%d",&n); for(i=1;(i*i)<=n;i++) if((i*i)==n) { printf("%d",1); return 0; } for(i=1;i*i<=n;i++) for(j=1;j*j<=n;j++) if((i*i+j*j)==n) { printf("%d",2); return 0; } for(i=1;i*i<=n;i++) for(j=1;j*j<=n;j++) for(k=1;k*k<=n;k++) if((i*i+j*j+k*k)==n) { printf("%d",3); return 0; } printf("%d",4); return 0; } But this solution is bad. Connector Re: easy search // Problem 1073. Square Country 10 Jul 2010 18:30 I think it's DP in this problem O(n*sqrt(n)); Daniyar I don't think so. My code got AC // Problem 1073. Square Country 8 Feb 2013 11:25 for(i=1;(i*i)<=n;i++) if((i*i)==n) { printf("%d",1); return 0; } you can just write if (sqrt(n) * sqrt(n) == n) Mahmood Re: easy search // Problem 1073. Square Country 4 Oct 2011 21:02 this is the most epic answer I've read....hhhh :) u are awesome thanks dud and good luck hatred [Ivanovo SPU] Weak tests? [1] // Problem 1073. Square Country 19 Jan 2013 23:05 My program 4729094 got AC, but the same program gives WA2 on problem 1593 (harder tests). So, there is a class of numbers those my solution gives incorrect answer and I think some of such numbers must be below 60000 Sandro (USU) Re: Weak tests? // Problem 1073. Square Country 20 Jan 2013 02:00 2nd test of problem 1593 was added to the test set Erzhan Shaniev can anyone send me solution of this question? please ! (my mail is: erzhan_jktl@mail.ru) [1] // Problem 1073. Square Country 3 Mar 2008 23:05 Toy Re: can anyone send me solution of this question? please ! (my mail is: erzhan_jktl@mail.ru) // Problem 1073. Square Country 3 Jan 2013 08:38 Could you tell me case for Text 14.Thank You Toy WA 14!!!! // Problem 1073. Square Country 3 Jan 2013 08:11 Could you give me case for 14.Thank you. Irina WA 14 // Problem 1073. Square Country 1 Nov 2012 19:28 Could you give me case for test 14? Thank you!
|