fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5. 	// Complexity - Big O
  6. 	// Seberapa banyak operasi yg dilakukan/runtime berubah
  7. 	//   saat ada perubahan input
  8. 	// contoh: bubble sort vs quick sort
  9. 	/*
  10. 	int n, data[1000001];					// O(1)
  11. 	cin >> n;								// O(1)
  12. 	for(int i = 0; i < n; i++)				// O(n)
  13. 		cin >> data[i];
  14. 	for(int i = 0; i < n; i++)				// O(n^2)
  15. 		for(int j = 1; j < n; j++)
  16. 			if(data[j] < data[j-1]) {
  17. 				int tmp = data[j];
  18. 				data[j] = data[j-1];
  19. 				data[j-1] = tmp;
  20. 			}
  21. 	n = 10 -> op = 1+1+10+90 = 102
  22. 	n = 100 -> op = 1+1+100+9900 = 10002
  23. 	n = n -> op ~ n^2 -> O(n^2)
  24. 	*/
  25. 	// Rule of Thumb: 10^8 op = 1s
  26. 	// Big O = O(n^2)
  27. 	/*
  28. 	O(n)
  29. 	n = 10 -> rt = 1ms
  30. 	n = 100 -> rt = 10ms
  31. 	n = 1000 -> rt = 100ms
  32. 	..
  33.  
  34. 	O(n^2)
  35. 	n = 10 -> rt = 1ms
  36. 	n = 100 -> rt = 100ms
  37. 	n = 1000000 -> rt = 10^10ms
  38. 	*/
  39.  
  40. 	// 4 Paradigm overview
  41. 	/*
  42. 	// n <= 200000, data[i] <= 10^6
  43. 	int data = {10, 7, 3, 5, 8, 6, 9, 11}, n = 8;
  44. 	//                 ^  ^  ^     ^   
  45. 	// 3, 5, 8, 9
  46.  
  47. 	// 1. Cari bilangan terbesar & terkecil dari array data. O(n)
  48. 	maks = data[0];
  49. 	for(int i = 1; i < n; i++)
  50. 		if(data[i] > maks)
  51. 			maks = data[i];
  52. 	// 2. Cari bilangan terbesar urutan ke-k dari array data. (k<=n)
  53. 	// Pendekatan pertama: sort O(n^2) -> Time Limit Exceeded
  54. 	// Pendekatan kedua: Cari bil terbesar, lalu hapus.
  55. 	//                   Cari bil kedua terbesar, lalu hapus.
  56. 	//                   Ulangi sampai bil ke-(k-1) terbesar & hapus.
  57. 	//                   Cari bil ke-k terbesar. -> O(n*k) = O(n^2)
  58. 	for(int i = 0; i < k; i++)
  59. 		for(int j = 0; j < n; j++)
  60. 			...
  61. 	// Pendekatan yang tepat: sort O(n log n)
  62. 	// 3. Cari selisih terbesar dalam array data.
  63. 	// Pendekatan complete search -> O(n^2) -> TLE
  64. 	for(int i = 0; i < n; i++)
  65. 		for(int j = i+1; j < n; j++)
  66. 			if(maks < abs(data[i]-data[j]))
  67. 				maks = abs(data[i]-data[j]);
  68. 	// loop = (n-1)+(n-2)+...+1+0 = n*(n-1)/2 = (n^2-n)/2
  69. 	// Greedy -> O(n)
  70. 	// 4. Cari panjang LIS = Longest Increasing Subsequence di array data.
  71. 	// Dynamic Programming
  72. 	// - banyak subsoal yang overlap, yang seharusnya bisa dikerjakan
  73. 	//   sekali saja
  74. 	// 9! = 362880
  75. 	// 10! = 362880*10 = 3628800
  76. 	// 11! = 3628800*11 = 39916800
  77. 	// teknik memoization
  78. 	*/
  79.  
  80. 	// Complete Search
  81. 	// Iterative = loop
  82. 	// Recursive = fungsi rekursif
  83. 	// Pruning -> tidak melanjutkan proses yang pasti gagal
  84. 	/* 8 ratu di papan catur -> 8 Queens problem
  85. 	o..o..o.
  86. 	.o.o.o..
  87. 	..ooo...
  88. 	oooQoooo
  89. 	..ooo...
  90. 	.o.o.o..
  91. 	o..o..o.
  92. 	...o...o
  93.  
  94. 	C(64, 8) = terlalu besar
  95.  
  96. 	1.......
  97. 	..2.....
  98. >	....3...
  99. 	........
  100. 	........
  101. 	........
  102. 	........
  103. 	........
  104. 	8^7
  105. 	*/
  106.  
  107. 	/*
  108. 	// Divide & Conquer -> harus terurut
  109. 	// linear search -> per langkah -1 -> O(n)
  110. 	// binary search -> per langkah /2 -> O(log n)
  111.  
  112. 	// Soal: cari sebuah nilai dalam array yg terurut
  113. 	// cari = 10
  114. 	// {1, 1, 2, 2, 2, 4, 5, 6, 6, 9, 10, 13, 17, 22, 23}
  115. 	//           |-------------------------------------|
  116. 	// data terurut: i1 <= i2 -> data[i1] <= data[i2]
  117. 	int data[] = {1, 1, 2, 2, 2, 4, 5, 6, 6, 9, 10, 13, 17, 22, 23}, n = 15;
  118. 	int cari = 10;
  119.  
  120. 	// linear search
  121. 	for(int i = 0; i < n; i++)
  122. 		if(data[i] == cari)
  123. 			cout << cari << " ditemukan di index " << i << endl;
  124.  
  125. 	// binary search
  126. 	// {1, 1, 2, 2, 2, 4, 5, 6, 6, 9, 10, 13, 17, 22, 23}
  127. 	//  |--------------------|-------------------------|
  128. 	//                          |----------|-----------|
  129. 	//                          |--|---|
  130. 	//                                 |
  131. 	// dalam 1 langkah -> search space berkurang jadi 1/2 nya
  132. 	// dalam x langkah -> search space berkurang jadi 1/2^x nya
  133. 	// n = 2^x -> x = log2 n
  134. 	// ukuran search space = n -> banyak langkah = log2 n = log n
  135. 	int lo = 0, hi = n-1, mid;
  136. 	while(lo < hi) {
  137. 		mid = (lo+hi)/2;
  138. 		if(data[mid] > cari)
  139. 			hi = mid-1;
  140. 		else if(data[mid] < cari)
  141. 			lo = mid+1;
  142. 		else
  143. 			lo = hi = mid;
  144. 	}
  145. 	cout << cari << " ditemukan di index: " << lo << endl;
  146. 	*/
  147.  
  148. 	// *
  149. 	// Bisection method / Binary Search The Answer (BSTA)
  150. 	// 0 <= x < PI/2, sin(x) = increasing
  151. 	// x1 < x2 -> sin(x1) < sin(x2)
  152. 	// sin(x) = 0.75 -> x = arcsin(0.75)
  153. 	double PI = acos(-1);
  154. 	// cos(180) = cos(PI) = -1
  155. 	// acos(-1) = PI
  156.  
  157. 	double y = 0.75;
  158. 	double lo = 0, hi = PI/2, mid;
  159. 	while(hi-lo > 1e-7) {	// 1.23e-4 = 1.23*10^-4
  160. 		mid = (lo+hi)/2;
  161. 		cout << lo << " " << mid << " " << hi << endl;
  162. 		if(sin(mid) > y)
  163. 			hi = mid;
  164. 		else if(sin(mid) < y)
  165. 			lo = mid;
  166. 	}
  167. 	cout << "arcsin(" << y << ") = " << lo << endl;
  168.  
  169. 	// Dynamic Programming
  170. 	// - banyak subsoal yang overlap -> jangan dihitung berulang2
  171. 	// - pakai memo -> memo[200][20] -> memoization
  172. 	// top down vs bottom up
  173. 	// classical
  174.  
  175. 	return 0;
  176. }
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 0.785398 1.5708
0.785398 1.1781 1.5708
0.785398 0.981748 1.1781
0.785398 0.883573 0.981748
0.785398 0.834486 0.883573
0.834486 0.859029 0.883573
0.834486 0.846757 0.859029
0.846757 0.852893 0.859029
0.846757 0.849825 0.852893
0.846757 0.848291 0.849825
0.846757 0.847524 0.848291
0.847524 0.847908 0.848291
0.847908 0.8481 0.848291
0.847908 0.848004 0.8481
0.848004 0.848052 0.8481
0.848052 0.848076 0.8481
0.848052 0.848064 0.848076
0.848052 0.848058 0.848064
0.848058 0.848061 0.848064
0.848061 0.848062 0.848064
0.848061 0.848061 0.848062
0.848061 0.848062 0.848062
0.848062 0.848062 0.848062
0.848062 0.848062 0.848062
arcsin(0.75) = 0.848062
https://ideone.com/fV9Q0n
language:
C++ (gcc 8.3)
created:
16 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!