Common Board @ Timus Online Judge

Mahilewets Nikita [BSUIR] It was hard to solve // Problem 2072. Kirill the Gardener 3 3 Sep 2017 17:01

LLL quicksort TLE#11; use heapsort instead and got AC // Problem 1613. For Fans of Statistics 3 Sep 2017 16:12

Mahilewets Nikita [BSUIR] Python TLE // Problem 1776. Anniversary Firework 2 Sep 2017 18:49

Ashiqul Islam Test 54 // Problem 1463. Happiness to People! 2 Sep 2017 16:19

T_e_n_Jl_bl_u Please, what kind of test in #6 test? [2] // Problem 1369. Cockroach Race 1 Sep 2017 07:44

AlEkSeY~` Помогите пж, ошибка в 11 тесте // Problem 1688. Team.GOV! 1 Sep 2017 23:03

Mahilewets Nikita [BSUIR] Nice new feature! 31 Aug 2017 12:36

Sherxon WIUT No Need To Use Loop, Only If can solve it [9] // Problem 2011. Long Statement 27 Nov 2014 01:14

srevarun idea // Problem 1385. Interesting Number 30 Aug 2017 14:51

LastOne WA 15 [1] // Problem 1651. Shortest Subchain 30 Aug 2017 07:49

Please help

#include <bits/stdc++.h>
using namespace std;
const int infInt = 1<<30;
vector<int>adj[100010];
pair<int,int> edges[100010];
int parent[100010],dist[100010];
map< pair<int,int> ,int> Map;
bool mark[100010];

void path(int u){
if(parent[u]==u){
    cout<<edges[u].first<<" "<<edges[u].second;
    return;
}
path(parent[u]);
cout<<" "<<edges[u].second;
}
int main(){
int ant,curr,root,n;
cin>>n;
for(int i=0;i<n;i++){
    cin>>curr;
    if(i>0){
      edges[i].first=ant;
      edges[i].second=curr;
      adj[ant].push_back(curr);
      Map[make_pair(ant,curr)]=i;
    }

    if(i==0)
      root=curr;
    ant=curr;
}
if(root==curr){
    cout<<root<<endl;
    return 0;
}
queue<int> q;
for(int i=1;i<n;i++){
    parent[i]=i;
    dist[i]=infInt;
    if(edges[i].first==root){
      q.push(i);
      dist[i]=0;
    }
    if(edges[i].second==curr)
      mark[i]=true;
}

while(!q.empty()){
    int u=q.front();
    q.pop();
    int x=edges[u].first;
    int y=edges[u].second;
    for(auto z: adj[y]){
      int v=Map[make_pair(y,z)];
      if(v>u and dist[v]>dist[u]+1){
        dist[v]=dist[u]+1;
        parent[v]=u;
        q.push(v);
      }
    }
}
int best=infInt,bestInd=-1;
for(int i=1;i<n;i++){
    if(dist[i]<best and mark[i]){
      bestInd=i;
      best=dist[i];
    }
}
path(bestInd);
cout<<endl;
return 0;
}

LastOne Re: WA 15 // Problem 1651. Shortest Subchain 30 Aug 2017 08:51

Or this, aldo wa 15
What´s the problem??

#include <bits/stdc++.h>
using namespace std;
const int infInt = 1e9;

vector<int>adj[100010];
pair<int,int> edges[100010];
int final;
map< pair<int,int> ,int> Map;
bool mark[100010];

bool vis[100010];
int dp[100010];

int f(int u){
if(edges[u].second==final)return 0;
if(vis[u])return dp[u];
vis[u]=true;
int x=edges[u].first;
int y=edges[u].second;
int ans=infInt;
for(auto z:adj[y]){
    int v=Map[make_pair(y,z)];
    if(v>u)
      ans=min(ans,1+f(v));
}
return dp[u]=ans;
}

void rec(int u){
if(edges[u].second==final){
    cout<<" "<<final<<endl;
    return;
}
int x=edges[u].first;
int y=edges[u].second;
for(auto z:adj[y]){
    int v=Map[make_pair(y,z)];
    if(v>u and dp[u]==1+f(v)){
      cout<<" "<<y;
      rec(v);
      break;
    }
}
}

int main(){
int ant,curr,root,n;
cin>>n;
for(int i=0;i<n;i++){
    cin>>curr;
    if(i>0){
      edges[i].first=ant;
      edges[i].second=curr;
      adj[ant].push_back(curr);
      Map[make_pair(ant,curr)]=i;
    }

    if(i==0)
      root=curr;
    ant=curr;
    if(i==n-1)
      final=curr;
}
if(root==curr){
    cout<<root<<endl;
    return 0;
}
int best=infInt,bestInd=-1;
for(int i=1;i<n;i++){
    if(edges[i].first==root){
      int ans=f(i);
      if(ans < best){
        best=ans;
        bestInd=i;
      }
    }
}
cout<<edges[bestInd].first;
rec(bestInd);

}

LastOne wrote 30 August 2017 07:49

Please help

#include <bits/stdc++.h>
using namespace std;
const int infInt = 1<<30;
vector<int>adj[100010];
pair<int,int> edges[100010];
int parent[100010],dist[100010];
map< pair<int,int> ,int> Map;
bool mark[100010];

void path(int u){
if(parent[u]==u){
    cout<<edges[u].first<<" "<<edges[u].second;
    return;
}
path(parent[u]);
cout<<" "<<edges[u].second;
}
int main(){
int ant,curr,root,n;
cin>>n;
for(int i=0;i<n;i++){
    cin>>curr;
    if(i>0){
      edges[i].first=ant;
      edges[i].second=curr;
      adj[ant].push_back(curr);
      Map[make_pair(ant,curr)]=i;
    }

    if(i==0)
      root=curr;
    ant=curr;
}
if(root==curr){
    cout<<root<<endl;
    return 0;
}
queue<int> q;
for(int i=1;i<n;i++){
    parent[i]=i;
    dist[i]=infInt;
    if(edges[i].first==root){
      q.push(i);
      dist[i]=0;
    }
    if(edges[i].second==curr)
      mark[i]=true;
}

while(!q.empty()){
    int u=q.front();
    q.pop();
    int x=edges[u].first;
    int y=edges[u].second;
    for(auto z: adj[y]){
      int v=Map[make_pair(y,z)];
      if(v>u and dist[v]>dist[u]+1){
        dist[v]=dist[u]+1;
        parent[v]=u;
        q.push(v);
      }
    }
}
int best=infInt,bestInd=-1;
for(int i=1;i<n;i++){
    if(dist[i]<best and mark[i]){
      bestInd=i;
      best=dist[i];
    }
}
path(bestInd);
cout<<endl;
return 0;
}

Mahilewets Nikita [BSUIR] Congratulations [1] 29 Aug 2017 21:19

November Rain How to solve this problem?I used Djkstra,but I've got TLE. [7] // Problem 1325. Dirt 18 Apr 2004 18:05

Gheorghe Stefan Re: How to solve this problem?I used Djkstra,but I've got TLE. [5] // Problem 1325. Dirt 19 Apr 2004 01:50

Lee algorithm. Runs in O(N * M).

If you don't know it, here is a short description: you start from starting position (sl, sc) and now you expand this node; in a queue you put all its neighbours. You do this only if you optimize by going to that neighbour, i.e. the current cost is shorter than the previous one. let a[i][j] be a matrix with two fields: boots and length. a[i][j] means: minimum number of boots and minimum length to reach (i, j) from start position.
You expand from (x, y) to a neighbour (c, d) when:
a[x][y].boots + 1 (if you change boots, 0 else) < a[c][d].boots or a[x][y].boots + 1 = a[c][d].boots and a[x][y].length + 1 < a[c][d].length. Obvious, you take the valid neighbours (not 0s or outside ones)
hope it's clear...

Vladimir Yakovlev (USU) Why do you think it works only O(N*M)? [1] // Problem 1325. Dirt 19 Apr 2004 19:19

Sq1 Re: Why do you think it works only O(N*M)? // Problem 1325. Dirt 16 Aug 2017 01:32

Can someone explain where is the problem in this solution?

Melody Re: How to solve this problem?I used Djkstra,but I've got TLE. // Problem 1325. Dirt 19 Apr 2004 20:55

I just used the algorithm as you described.
But it got tle.
Anyway thank you very much.
Now I've got it,using heap will help me.

Edited by author 19.04.2004 20:55

Pavel Nalivaiko Re: Lee's algorithm [1] // Problem 1325. Dirt 20 Apr 2004 00:29

I wrote the solution with Lee's algorithm, as it was discribed above by Gheorghe Stefan, and got TL on test 16.
I doubt it works in O(MN).
I test the solution at my local computer - it gaves the correct answers (obviously), but works about 10 times slower, then my solution with Dijkstra!

Denis Koshman Re: Lee's algorithm // Problem 1325. Dirt 21 Aug 2008 03:54

I BFS on number of boots and Dijkstra on walk-length inside odd/even slices. Dijkstra is linear-time here because of same-length edges (front line is kept as bidirectional list in non-descending order of walk-length, insertion position goes only forwards). AC in 0.062 sec :)

Edited by author 21.08.2008 21:13

Pavel Nalivaiko I used Dijkstra with K-based Heap and got AC // Problem 1325. Dirt 19 Apr 2004 19:55

It could be proved that in Dijkstra's algorithm the choice K = E /V is assimptotically optimal. So, applying to our problem, E / V equals to 8.

yifei To Admins [2] // Problem 1358. Cables 12 Apr 2006 06:35

Filip Franik Tests for WA7 // Problem 1878. Rubinchik's Cube 14 Aug 2017 19:48

Andrew1703 Code don't works with big numbers, Python 3.4 [9] // Problem 1017. Staircases 23 Jun 2017 02:00

k=int(input())
a=[]
a.append(0)
a.append(1)
a.append(1)
a.append(2)
a.append(2)
s=0
for j in range(5,k+1):
if j%2==1:
     for i in range(1,j//2+1):
         s+=a[i]
     a.append(s)

else:
     for i in range(1,j//2):
         s+=a[i]
     s=s+a[j//2]-1
     a.append(s)
s=0
print(a)

Mahilewets Re: Code don't works with big numbers, Python 3.4 [8] // Problem 1017. Staircases 23 Jun 2017 09:35

You are printing a, print(a). A is a LIST.

Andrew1703 Re: Code don't works with big numbers, Python 3.4 // Problem 1017. Staircases 23 Jun 2017 22:10

FUUUCK, thanks, its so stupid error(

Andrew1703 Re: Code don't works with big numbers, Python 3.4 [6] // Problem 1017. Staircases 23 Jun 2017 22:17

but code still not works, starting with the second test, and in example program gives WA, but I check code at least 3 times, I cant find errors((

Mahilewets Re: Code don't works with big numbers, Python 3.4 [5] // Problem 1017. Staircases 23 Jun 2017 23:25

I don't understand how does your algorithm work. My AC - program is calculating values sequentially for different ladders. Time complexity is O(N*N*N). So, it is basically two dimensional dynamic programming.

Mahilewets Re: Code don't works with big numbers, Python 3.4 [4] // Problem 1017. Staircases 23 Jun 2017 23:28

And your algorithm has time complexity just O(N*N). It is not surprising that I can't understand it without explanation. It is extremely optimized solution, with heavy math behind.

Edited by author 23.06.2017 23:28

Grandmaster Re: Code don't works with big numbers, Python 3.4 [3] // Problem 1017. Staircases 11 Aug 2017 05:17

you don't need heavy math you can in O(n^2) time and O(n^2) space i don't know how u got O(n^3)
cin >> n;
    for(int i = 0; i < n; i++)
        dp[i][0] = 1;
    for(int i = 1; i < n; i++)
        for(int j = 1; j <= n; j++)
        {
            dp[i][j] = dp[i - 1][j];
            if(j >= i)
                dp[i][j] += dp[i - 1][j - i];
        }
    cout << dp[n - 1][n];

Edited by author 11.08.2017 05:18

Edited by author 11.08.2017 05:19

Mahilewets Nikita [BSUIR] Re: Code don't works with big numbers, Python 3.4 [2] // Problem 1017. Staircases 11 Aug 2017 09:07

When I was solving it
I thought
There is a staircase consists of X cubes and it's height is Y
Then just add some new stair with height Z
Z is strictly greater than Y
Get new staircase with X+Z cubes and height Z

Mahilewets Nikita [BSUIR] Re: Code don't works with big numbers, Python 3.4 [1] // Problem 1017. Staircases 11 Aug 2017 09:11

But also I know
There is a solution based on generating functions
I can't understand generating functions theory
So I have AC on task but don't understand generating functions and that guy didn't had AC at the moment
So probably generating functions are hard for him just like they are hard for me
That is why I have called generating functions "heavy math"

Grandmaster Re: Code don't works with big numbers, Python 3.4 // Problem 1017. Staircases 14 Aug 2017 18:39

tell me more, do you know a good article for this?

Imran Yusubov My Code [1] // Problem 1012. K-based Numbers. Version 2 13 Apr 2009 10:45

XSpider AC Solve. It's problem is very easy!! [1] // Problem 1048. Superlong Sums 26 Mar 2008 01:18

Neo Nomaly What method I have to use? [2] // Problem 1448. Lighting in Hogwarts 26 Mar 2006 16:30

Peter Ivanov Re: What method I have to use? [1] // Problem 1448. Lighting in Hogwarts 20 Aug 2006 04:18

The only method I used to solve it was the intuition.
I hope anyone who knows a proof of any solution (I think there are many) will expain it.

Felix_Mate Re: What method I have to use? // Problem 1448. Lighting in Hogwarts 13 Aug 2017 23:23

Пожалуйста, не сдавайте задачу, не понимая своё решение!!!

Это хорошая математическая задача из темы на конструктив.
Во-первых, покажем, что решение всегда существует.
Для k=1 утверждение справедливо.
Пусть уже построена последовательность s1...sk, удовлетворяющая условию задачи.
Пусть cij=кол-во 1 на [i,j].
Покажем, что можно добавить 0 или 1 в конец, чтобы полученная последовательность также была решением. Предположим противное: при добавлении 0 есть подотрезок [i,k+1], где cik>(k-i+2)b/100+2 (1) или cik<(k-i+2)b/100-2 (2) и при добавлении 1 есть подотрезок [j,k+1], где cjk>(k-j+2)b/100+1 (3) или cjk<(k-j+2)b/100-3 (4).
Заметим, что (1) и (4) невозможны (по индукции |cik-(k-i+1)b/100|<=2 => cik<=(k-i+1)b/100+2 и |cjk-(k-j+1)b/100|<=2 => cjk>=(k-j+1)b/100-2).

Итого получаем (2) и (3) одновременно:
cik<(k-i+2)b/100-2, cjk>(k-j+2)b/100+1 => cjk>cik => j<i.
Рассмотрим отрезок [j,i-1]. По индукции cj,i-1=cjk-cik удовлетворяет условию |(cjk-cik)-(i-j)b/100|<=2 => cjk<=cik+(i-j)b/100+2<(k-i+2)b/100+(i-j)b/100=(k-j+2)b/100.
=> cjk<(k-j+2)b/100. С другой стороны, выполнено (3)-противоречие => 0 или 1 даёт решение длины к+1.

Как сконструировать решение? Из док-ва видно, в каких местах возникают проблемы. Когда можно добавить 0 (если нельзя => нужно добавить 1-это даст решение по док-ву)?
0 можно добавить <=> для 1<=i<=k выполнено (k-i+2)b/100-2<=cik<=(k-i+2)b/100+2. Второе неравенство выполнено (т.к. cik<=(k-i+1)b/100+2). Поэтому нужно (k-i+2)b/100-2<=cik. Когда это условие нарушается? Оно нарушается <=> существует такое 1<=i<=k, что cik<(k-i+2)b/100-2 <=> cik<(-b/100)i+(2kb/100-2).Заметим что cik неубывает, а (-b/100)i+(2kb/100-2) строго убывает => нарушение происходит <=> i=1 <=> c1k<-b/100+2kb-2=kb/100-2 <=> 100*c1k<kb-200. В этом случае 0 брать нельзя.

Edited by author 13.08.2017 23:28

Baurzhan if you have wa#7 [1] // Problem 1713. Key Substrings 7 Nov 2010 11:06

Ayaz Time limit exit! // Problem 1086. Cryptography 13 Aug 2017 12:47