| Show all threads Hide all threads Show all messages Hide all messages |
| IF you have TL and use sqrt + map | Toshpulatov (MSU Tashkent) | 1846. GCD 2010 | 3 Apr 2020 00:21 | 1 |
instead map use unordered_map |
| do you know what test 12 is? | STAVASD | 1354. Palindrome. Again Palindrome | 1 Apr 2020 19:22 | 4 |
once I've solved this exercise, but know a vontto make my algorithm better. I've forced whith WA#12. Could you tell me this test? I've solved it!!)))
if you have the same problem, try
test: 1233345333
ansver: 12333453335433321 |
| No subject | mmd18cury | 1086. Cryptography | 1 Apr 2020 11:20 | 1 |
#include <iostream>
#include <vector>
#include <iterator>
using namespace std;
int n = 163841;
vector<char> prime(n + 1, true);
void eratosphen() {
prime[0] = false;
prime[1] = false;
for (int i1 = 2; i1 <= n; ++i1)
if (prime[i1])
if (i1 * 1ll * i1 <= n)
for (int j1 = i1 * i1; j1 <= n; j1 += i1)
prime[j1] = false;
}
int main() {
eratosphen();
vector <long long> list(15001); int i = 2;
for (int il = 1; il <= 15000;) {
for (int ip = 2; ip < prime.size(); ip++) {
if (prime[ip]) {
list[il] = ip;
il++;
}
}
}
int k;
cin >> k;
for (int i0 = 0; i0 < k; i0++){
int m;
cin >> m;
cout << list[m] << '\n'; \
}
} |
| If you have WA 7 | Toshpulatov (MSU Tashkent) | 1628. White Streaks | 31 Mar 2020 16:40 | 1 |
|
| An O(K^2) solution | CmYkRgB123 | 1119. Metro | 30 Mar 2020 23:12 | 3 |
Sort the quarters that can be crossed.And then dp. The state transition equation is F[i]=Max{ F[j] + 1 | P[j].x<P[i].x and P[j].y<P[i].y } The maximum of F[i] is the number of the the quarters that should be crossed. Then you can work out the answer. Edited by moderator 18.08.2020 02:22A solution for Chinese readers.Much clearer.
这道题有明显的动态规划策略。首先不要按照方格来考虑，考虑顶点，这样目标点就是(N+1,M+1)。
---------算法1-----------
最直观的想法是按照矩阵动态规划。
设状态F[i,j]为走到点(i,j)时的最短路径
状态转移方程
F[i,j]=Min
{
F[i-1,j]+100
F[i,j-1]+100
F[i-1,j-1]+141.4213562373
}
边界条件 F[0,0]=0
F[N+1,M+1]就是结果。
但是对于8M的内存限制，要使用滚动数组。
时间复杂度为O(N*M)
---------算法2-----------
可以发现，如果我们只走直边的话，要走(N+M)*100长度。如果走C条斜边，那么要走(C*141.4213562373)+(N+M-C*2)*100 的长度。那么显然我们要尽可能使C更大，即多走斜边。
这样可以转化为经典的LIS模型。即把所有的斜边按照坐标排序，然后求最长的上升序列(x，y都要严格递增)，走这样的斜边一定是最优的策略。于是我们可以求出C。
结果就是(C*141.4213562373)+(N+M-C*2)*100。
Vijos 1336其实就是这道题的数据加大版。对于较小的K和很大的N,M，只能用算法2解决。 by translating.............
A solution for Chinese readers.Much clearer.
This problem has obvious dynamic programming strategies. First, don't think in terms of squares, consider vertices, so the target point is (N + 1, M + 1).
--------- Algorithm 1 -----------
The most intuitive idea is dynamic programming in terms of matrices.
Let the state F [i, j] be the shortest path to the point (i, j)
State transition equation
F [i, j] = Min
{
F [i-1, j] +100
F [i, j-1] +100
F [i-1, j-1] +141.4213562373
}
Boundary condition F [0,0] = 0
F [N + 1, M + 1] is the result.
But for the 8M memory limit, a rolling array is used.
Time complexity is O (N * M)
--------- Algorithm 2 -----------
It can be found that if we only go straight, we have to go to (N + M) * 100 length. If you take the C hypotenuse, then you have to take the length of (C * 141.4213562373) + (N + M-C * 2) * 100. So obviously we want to make C as large as possible, that is, take more hypotenuse.
This can be transformed into a classic LIS model. That is, sort all the hypotenuses according to the coordinates, and then find the longest ascending sequence (x, y must be strictly increased). Taking such hypotenuses must be the optimal strategy. Then we can find C.
The result is (C * 141.4213562373) + (N + M-C * 2) * 100.
Vijos 1336 is actually an enlarged version of this question. For smaller K and large N, M, it can only be solved by algorithm 2. |
| How could we solve this problem by DP? | HowieMa | 1073. Square Country | 29 Mar 2020 14:23 | 3 |
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! 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 i solved it with dp. but i wondered with u.plz send me ur code.
EMAIL:achowdhury@isrt.ac.bd |
| Give 13 test please | vtalgo20_egurin | 1628. White Streaks | 29 Mar 2020 01:52 | 1 |
I failed on 13 test and I can't found error. Please give a 13 test. |
| Agree? Found out the game? | Kairom `Ekexity 💻 | 2148. Insane Shot | 28 Mar 2020 14:47 | 2 |
|
| WA on TEST 20 | Ashiqur Rahman Nayeem | 1684. Jack's Last Word | 28 Mar 2020 04:35 | 2 |
|
| WA 44 | СуБаЕг | 2112. Battle log | 28 Mar 2020 02:26 | 2 |
WA 44 СуБаЕг 19 Nov 2019 23:09
Edited by author 19.11.2019 23:33
Edited by author 19.11.2019 23:44 |
| Math explanation | mberdyshev | 1214. Strange Procedure | 27 Mar 2020 22:02 | 2 |
We are given positive x and y. Let's go in the first loop.
Let's do some method refactoring for better understanding:
y0 = x*x+y;
x0 = x*x+y0;
y1 = sqrt(x0+(y0/labs(y0))*(-labs(y0)));
for (j = 1; j <= 2*y1; j++)
x0 = x0-y1;
x = x0;
y = y1;
Let's go through the lines:
y0 = x*x + y
Next:
x0 = x*x + y0 = 2*x*x + y
As y0 > 0 (x, y are positive) => y0/labs(y0) = 1
So y1 = sqrt(x0+(y0/labs(y0))*(-labs(y0))) = sqrt(x0-labs(y0)) = sqrt(2*x*x + y - (x*x + y)) = sqrt(x*x) = x
Next 2 lines equals to this:
x0 = x0 - 2*y1*y1 = 2*x*x + y - 2*x*x = y
So, x=y and y=x. x and y are swapped. After that you need to count amount of swaps and print appropriate answer |
| Could you give me some tests? | Vedernikoff 'Goryinyich' Sergey (HSE: АОП) | 1660. The Island of Bad Luck | 26 Mar 2020 00:26 | 5 |
Could somebody who solved this problem give some tests to me? WA #7 :( Also asking for some random tests, because it's hard to check the solution. random test:
25 7 3
4.0671982122
good luck =) 100 2 20
0.00000
100 98 1
0.12311156
85 17 53
2.1738219 |
| I think my solution is right but they don't accept it , help? | Ore Sama | 2066. Simple Expression | 25 Mar 2020 14:01 | 2 |
#include <stdio.h>
int main(){
int a,b,c;
scanf("%d",&a);
scanf("%d",&b);
scanf("%d",&c);
if (a>b){
if (b>c){
printf("%d",c-(a*b));
}
else{
printf("%d",b-(a*c));
}
}
if(b>a){
if (a<c){
printf("%d",a-(c*b));
}
}
return 0;
} 1) a,b,c sequence is already sorted.
2) Try "1 1 1" input. Answer is -1. |
| Use next_permutation | Dmitry Vaskin`~ | 2011. Long Statement | 24 Mar 2020 21:29 | 2 |
I used next_permutation and get AC i used next_permutation and got TLE |
| *** COUNTRIES RANKLIST *** | tainic | | 24 Mar 2020 19:52 | 2 |
Hi, I made a countries ranklist here: http://acmtimusru.appspot.com It lists the countries by rating, solved, users or last ac, where: - rating = sum(user.rating) for user in a country - solved = sum(user.solved) for user in a country - users = count of users in a country - last ac = the most recent accepted submission of any user in a country Also, clicking on a country gives you a ranklist of users in that specific country. The ranklists are updated hourly. Enjoy! Edited by author 24.03.2020 14:51That's nice. Thank your for sharing your effort with us!
God bless Antarctica!
Edited by author 24.03.2020 19:53 |
| WA #15 | Flamethrower0627 | 1104. Don’t Ask Woman about Her Age | 20 Mar 2020 19:31 | 1 |
WA #15 Flamethrower0627 20 Mar 2020 19:31 Can anybody help
Edited by author 20.03.2020 19:35 |
| Wrong Answer Test Case #1 | skartik | 2018. The Debut Album | 17 Mar 2020 11:41 | 1 |
I don't know why my solution is failing on test case 1,
I have tested against all available test cases with correct answer , but cannot pass test case 1, can anybody please tell what is test case 1. |
| Change judge id | gt123 | | 16 Mar 2020 21:20 | 1 |
Is it possible to change the judge id?
Thanks |
| WA#1 | mushfiq | 1022. Genealogical Tree | 13 Mar 2020 13:08 | 3 |
WA#1 mushfiq 27 Oct 2014 16:07 It's the same as the given sample input. But what if i have the same answer that in sample, and get WA1? |
| why doesn't it work? java | Argin | 1644. A Whole Lot of Walnuts | 12 Mar 2020 20:58 | 3 |
import java.util.Scanner;
public class javasucc {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int h = 2, s = 10;
for(int i=0; i<n; i++) {
int a = in.nextInt();
String b = in.next();
if(b=="hungry"){
if(a>h) {h = a;}
}
else if(b=="satisfied"){
if(a<s) {s = a;}
}
}
if(h >= s) System.out.println("Inconsistent");
else System.out.println(s);
}
}
and the problem is that program doesn't want to do if and i can't change s to a 1) I wasn't crying for help though but just was wondering why
2) Thanks for the link, the problem was actually in "==" |
