Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
Why WA on test 6? | SpaceFlyer | 1439. Поединок с И-Так-Понятно-Кем | 9 окт 2023 13:54 | 6 |
I wrote two programs, one AC, one WA. I run these two programs for many times but they always make the same answer. Is it strange? Two test for you: ---Test 1--- 4 4 D 1 D 2 L 1 L 2 ---Test 2--- 4 4 D 2 D 1 L 1 L 2 Output 1: 2 4 Output 2: 3 4 Edited by author 01.04.2006 13:51 Thank you! Edited by author 05.08.2006 10:55 deleted Edited by author 13.12.2019 21:18 |
Sqrt decomposition 0.062s =D | InstouT94 | 1439. Поединок с И-Так-Понятно-Кем | 12 окт 2022 01:07 | 1 |
|
Hint | andreyDagger | 1439. Поединок с И-Так-Понятно-Кем | 3 янв 2022 14:16 | 1 |
Hint andreyDagger 3 янв 2022 14:16 |
Memory Limit Exceeded with 70KB memory usage. | Samarendra Dash | 1439. Поединок с И-Так-Понятно-Кем | 2 май 2020 18:25 | 1 |
I am using a solution, where I store all the doors in a BST, and if door k is to be deleted then I delete the kth smallest element in the BST. Same for lookup, I search the kth smallest and print the number. In test case 2 it is showing memory limit exceeded with only some 66-69KB memory usages. But the question says 64MB memory is allocated. Then why is this happening? (I am using C++ to code this.) |
Can it be solved on Python? | DmitriyBerg | 1439. Поединок с И-Так-Понятно-Кем | 5 мар 2020 00:40 | 1 |
I've used BST but still cannot optimize it... similar code on C is accepted with 0.171s 300kb but Python is processing the code way longer and TLE #14. And no solutions on python so far. Is there something that can be done? |
Time limit correction for problem 1439. Battle with You-Know-Who | Vladimir Yakovlev (USU) | 1439. Поединок с И-Так-Понятно-Кем | 10 апр 2018 23:39 | 1 |
The time limit for the problem has been corrected from 2.0 sec to 1.0 sec. The new value better reflects the original expectations for accepted solutions back from 2006. Around 40 authors have lost their AC (mostly submitted since 2017). |
Hey.What is the Time Complexity of your algorithm? | sashimi | 1439. Поединок с И-Так-Понятно-Кем | 26 ноя 2016 23:23 | 8 |
Mine is O(m*logn*logn)and got AC in 0.75s,958 KB. I used a BST,a Hash table and Binary Search. I think my algorithm is not good enough and I'm interested in how you solve this. EM:tczw@sina.com Mine is O(mlogm) and got AC in 0.109s, 474kb I used balance binary search tree. What is your mlogm algorithm? O(mlogn), lazy segment tree, 0.078. Edited by author 16.03.2014 14:27 Mine is simple tree O(mlog(m)) and accepted time is 0.015 Mine is (mlogn), implicit segment tree |
set_class in C++ (1439 ) | svr | 1439. Поединок с И-Так-Понятно-Кем | 26 апр 2016 16:38 | 4 |
In seems that in C++ for set-object no operator for standard container inquiry : N-tn element, with log N complexity, but should be. With such operator problem 1439 would be very simple. In reality was necessary to program my own set class based on red-black trees. And N-th element to realize was very simple(hard work was balancing). It,s not well that tree-structures of standard containers are hidden for uses in C++. What did you store in red-black tree? I've tried 4 self-invented algorithms and no of them Accepted (MLE, TLE most common). In standard container's descriptions operation take_N-th_element with O(log N) complexity presence but in Microsoft Visual C++ dosn't. Using Cormen's book I build myself red-black tree -type with last additional operation. My structure stores: left, right,father, color for each node- this is standard, but additional I support(this means O(log N) renewing in each operation) new characteristics: number of sublines for each node- or subtree nodes count. Using this charactiristics and binary search It's not difficalt to build "take_N-th_element" with O(log N) complexity . Edited by author 19.04.2007 19:43 |
WA 27 | radoslav11 | 1439. Поединок с И-Так-Понятно-Кем | 8 авг 2015 18:36 | 1 |
WA 27 radoslav11 8 авг 2015 18:36 Can anyone provide me 27th test case or tell me were am I wrong? I am using dynamic segment tree where in each node I store the count of doors in the current interval. Thanks in advance. source code: https://ideone.com/PmG5Qb Sorry for bad English |
Test case #2 | Alexander V | 1439. Поединок с И-Так-Понятно-Кем | 14 мар 2013 19:29 | 1 |
Help with #2 test! give example data! all data in topics my programm pass! |
Good test for this problem | Ivan Anisimov | 1439. Поединок с И-Так-Понятно-Кем | 25 окт 2012 00:04 | 3 |
20 27 D5 L5 D7 L7 D6 L7 D1 L4 D11 L10 D14 L13 D5 L5 D1 D2 D3 D5 D4 L1 L2 L3 L4 L5 L6 L7 L8 6 9 10 6 14 18 10 3 6 11 14 16 17 18 20 Edited by author 25.10.2012 00:05 |
treap + binarySearch | Berezhko German | 1439. Поединок с И-Так-Понятно-Кем | 30 авг 2012 18:07 | 1 |
my AC used treap as data structure and binary search for the answer. In heap I have kept numbers of initial deleted rooms. After each query I was looking for this number. And if query is 'LOOK AT', I print it, else insert in treap. O(M * log^2K), where K is number of query 'D' P.S.: sorry for bad English. Edited by author 30.08.2012 18:26 |
How to determine initial numbers on the deleted doors quickly? | Alexey Dergunov [Samara SAU] | 1439. Поединок с И-Так-Понятно-Кем | 22 май 2012 21:10 | 1 |
|
Test case #22 | FreezingCool | 1439. Поединок с И-Так-Понятно-Кем | 1 сен 2011 20:25 | 2 |
Hello, Could anyone provide me with some hint about the test 22? I keep getting WA#22. |
O(M * log N) in 0.421s with C# and without Binary Search!! | Leonid (SLenik) Andrievskiy | 1439. Поединок с И-Так-Понятно-Кем | 21 авг 2011 03:58 | 1 |
Using Binary Indexed Tree (aka Fenwick tree) and standart System.Dictionary (dictionary bsaed on hashing). Hint: you do not need binary search over heap! If you're familiar with Fenwick tree's structure, you can write your own function, which'll find the smallest index in fenwick's tree with given sum. |
Memory Limit error with less then 5MB allocated to program | VC67 | 1439. Поединок с И-Так-Понятно-Кем | 8 май 2011 19:19 | 3 |
I'm have gotten "memory limit exceeded" on test 2. I try to solve this task with Fenwick tree in Java. But "memory allocated" value in result table is only 4.7MB. Stated memory limit is 16MB, and some of accepted solution have almost 16MB allocated (ID 3136829 for example). Edited by author 08.05.2011 15:37 It seems that if programm tries to allocate real big chunk of memory, that does not show in result table. i.e. 5MB and 2 test is state of program before its attempt to allocate too many mem. It's Java Memory Model. On this server Java runs with minimal and maximal size of heap sets to 64 Mb. When you creating new Java objects it allocated in heap and still there until garbage collection, even if you not using it. Since your program make calculations and not idle, Garbage collector can't collect in background an will run when most of memory will occuped So, avoid to create multiple objects with short life-time, be carefull with explicit-created objects For exapmle Scanner.nextInt explicit creating String object, that then converted into the integer, but String and associated char-array remains in memory. Also any String you created (for example when reading from file) are remain in heap until the garbage collection: when reading from file use byte-by-byte reading, char reading instead of Scanners Strings and other |
treap ML | Zhandos | 1439. Поединок с И-Так-Понятно-Кем | 14 апр 2011 09:10 | 1 |
Can anybody help me with ML? I submit cartesian tree and got ML |
For WA9 | Alexander Georgiev | 1439. Поединок с И-Так-Понятно-Кем | 30 авг 2010 16:32 | 1 |
For WA9 Alexander Georgiev 30 авг 2010 16:32 20 7 D 9 D 7 D 6 D 1 D 2 D 3 L 2 The answer should be 4. |
my prog alway WA#22. What is test22, or some hint, here my code | xurshid_n | 1439. Поединок с И-Так-Понятно-Кем | 25 авг 2009 21:31 | 1 |
import java.io.*; import java.util.*; public class Problem_1439 implements Runnable{ public static void main(String []args){ new Thread(new Problem_1439()).start(); } public void run(){ try{ reader = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); solve(); }catch(IOException e){ throw new IllegalStateException(e); } }
int nextInt()throws IOException{ reader.nextToken(); return (int)reader.nval; }
boolean nextType()throws IOException{ reader.nextToken(); String s = reader.sval; if (s.length()!=1 && s.charAt(0)!='L' && s.charAt(0)!='D'){ for (int i = 0; i< 1000000000;i++)System.out.println("ERORO"); } return reader.sval.charAt(0)=='L'; }
int n, m;
StreamTokenizer reader;
final int MAX_N = 211111;
class node{ int left, right; int lleft, rright; int x, y; int size;
node(){ left = right= x = y = size = lleft = rright = 0; } } node tree[]; int g[]; int lt, root; int i, j, c, k; int getSize(int root){ return (root == 0 ) ? 0: tree[root].size; }
int insert(int root, int x, int y){ if (root == 0 || tree[root].y <= y){
lt++; //tree[lt] = new node(); tree[lt].left = 0; tree[lt].right = 0; tree[lt].lleft = lt; tree[lt].rright = lt; tree[lt].x = x; tree[lt].y = y;
if (root > 0){ if (tree[root].x < x)tree[lt].left = root; else tree[lt].right = root; } tree[lt].size = 1 + getSize(tree[lt].left)+getSize(tree[lt].right);
if (tree[lt].left > 0)tree[lt].lleft = tree[tree[lt].left].lleft; if (tree[lt].right > 0)tree[lt].rright = tree[tree[lt].right].rright; return lt; }else if (x > tree[root].x){ tree[root].size ++; tree[root].right = insert(tree[root].right, x, y);
tree[root].rright = tree[tree[root].right].rright; return root; }else { tree[root].size++; tree[root].left = insert(tree[root].left, x, y);
tree[root].lleft = tree[tree[root].left].lleft; return root; } } int getId(int root, int k, int min){ if (root == 0)return k; int sz = getSize(tree[root].left); int delta = tree[root].x - (min + sz + 1); //if (delta < k)return getId(tree[root].right, k, min + sz + 1); if (delta >= k){ if (tree[root].left == 0)return k + min; int lright = tree[tree[root].left].rright; int delta2 = tree[lright].x - (min + sz); if (delta2 < k)return k + min + sz;else return getId(tree[root].left, k, min); }else { if (tree[root].right == 0)return k + min + sz + 1; int rleft = tree[tree[root].right].lleft; int delta2 = tree[rleft].x - (min + sz + 2); if (delta2 >= k)return k + min + sz + 1; else return getId(tree[root].right, k , min + sz + 1); } }
void solve()throws IOException{ n = nextInt(); m = nextInt(); g = new int[ MAX_N+1]; tree = new node[MAX_N + 1]; for (i = 0; i<=MAX_N;i++){ tree[i] = new node();
}
for (i = 1; i<=MAX_N;i++){ k = 1 + new Random().nextInt(i); g[i] = g[k]; g[k] = i; } root = 0; lt = 0; j = 0;
boolean type; int mind, maxd, d; mind = 1000000000; maxd = 1; d = 0; for (i = 1; i<= m;i++){ type = nextType(); k = nextInt(); if (k <= mind)k = k + 0; else if(k + d>=maxd )k+=d; else k = getId(root, k, 0);
if ( type ) {//L System.out.println(k); }else if (k<=n){//D j++; root = insert(root, k, g[j]); d ++; if (k <= mind)mind = k - 1; if (k >= maxd)maxd = k + 1; }
}
} } |
WHY WA#2? | Aleksander | 1439. Поединок с И-Так-Понятно-Кем | 25 авг 2009 19:52 | 2 |
This is my program program preg; var n,m,i,t,ch,e,sh,k,shh:longint;st:boolean;s:string;des,otv:array[1..100000]of longint;b:array[1..100000]of boolean; begin read(n);readln(m); sh:=1; for i:=1 to m do begin readln(s); if (s[1]='L') then b[sh]:=true else b[sh]:=false; val(s[3],ch,e); des[sh]:=ch;sh:=sh+1; end; sh:=1; for i:=2 to m+1 do begin if b[i-1]=false then begin for k:=i to m do begin if des[k]>=des[i-1]then begin shh:=0;st:=false; while st=false do begin shh:=shh+1;st:=true; for t:=1 to i-1 do begin if (des[k]+shh=des[t])and(b[t]=false)then st:=false; end; end; des[k]:=des[k]+shh; end; end; end; if b[i-1]=true then begin otv[sh]:=des[i-1];sh:=sh+1; end; end; for i:=1 to sh-1 do writeln(otv[i]); end. I use balanse tree, but WA#2. here my code. What is test#2? import java.io.*; import java.util.*; public class Problem_1439 implements Runnable{ public static void main(String []args){ new Thread(new Problem_1439()).start(); } public void run(){ try{ reader = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); solve(); }catch(IOException e){ throw new IllegalStateException(e); } }
int nextInt()throws IOException{ reader.nextToken(); return (int)reader.nval; }
boolean nextType()throws IOException{ reader.nextToken(); String s = reader.sval; if (s.length()!=1 && s.charAt(0)!='L' && s.charAt(0)!='D'){ for (int i = 0; i< 100000000;i++)System.out.println("ERORO"); } return reader.sval.charAt(0)=='L'; }
int n, m;
StreamTokenizer reader;
final int MAX_N = 111111;
class node{ int left, right; int lleft, rright; int x, y; int size;
node(){ left = right= x = y = size = lleft = rright = 0; } } node tree[]; int g[]; int lt, root; int i, j, c, k; int getSize(int root){ return (root == 0 ) ? 0: tree[root].size; }
int insert(int root, int x, int y){ if (root == 0 || tree[root].y <= y){
lt++; //tree[lt] = new node(); tree[lt].left = 0; tree[lt].right = 0; tree[lt].lleft = lt; tree[lt].rright = lt; tree[lt].x = x; tree[lt].y = y;
if (root > 0){ if (tree[root].x < x)tree[lt].left = root; else tree[lt].right = root; } tree[lt].size = 1 + getSize(tree[lt].left)+getSize(tree[lt].right); if (tree[lt].left > 0)tree[lt].lleft = tree[tree[lt].left].lleft; if (tree[lt].right > 0)tree[lt].rright = tree[tree[lt].right].rright; return lt; }else if (x > tree[root].x){ tree[root].size ++; tree[root].right = insert(tree[root].right, x, y); tree[root].rright = tree[tree[root].right].rright; return root; }else { tree[root].size++; tree[root].left = insert(tree[root].left, x, y); tree[root].lleft = tree[tree[root].left].lleft; return root; } } int getId(int root, int k, int min){ if (root == 0)return k + min; int sz = getSize(tree[root].left); int delta = tree[root].x - (min + sz + 1); //if (delta < k)return getId(tree[root].right, k, min + sz + 1); if (delta >= k){ if (tree[root].left == 0)return k + min; int lright = tree[tree[root].left].rright; int delta2 = tree[lright].x - (min + sz); if (delta2 < k)return k + min + sz;else return getId(tree[root].left, k, min); }else { if (tree[root].right == 0)return k + min + sz + 1; int rleft = tree[tree[root].right].lleft; int delta2 = tree[rleft].x - (min + sz + 2); if (delta2 >= k)return k + min + sz + 1; else return getId(tree[root].right, k , min + sz + 1); } }
void solve()throws IOException{ n = nextInt(); m = nextInt(); g = new int[ MAX_N+1]; tree = new node[MAX_N + 1]; for (i = 0; i<=MAX_N;i++){ tree[i] = new node();
} Random random = new Random(); for (i = 1; i<=n;i++){ k = 1 + random.nextInt(i); g[i] = g[k]; g[k] = i; } root = 0; lt = 0; j = 0; int mind = n, maxd = 1, d = 0; boolean type; for (i = 1; i<= m;i++){ type = nextType(); k = nextInt(); k = getId(root, k, 0);
if ( type ) {//L System.out.println(k); }else{//D j++; root = insert(root, k, g[j]);
}
}
} } |