Why Wa18? What is test?

Why Runtime Error?

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    unsigned short n, m;
    scanf("%hu", &n);
    vector <unsigned long long> bytes(n);
    vector <vector<unsigned short> > red(n);
    for(unsigned short i=0;i<n;i++) scanf("%llu", &bytes[i]);
    for(unsigned short i=1;i<n;i++) {
        unsigned short x, y;
        scanf("%hu %hu", &x, &y);
        red[x-1].push_back(y);
        red[y-1].push_back(x); }
    if(n>1) {
        for(unsigned short i=0;i<red.size();i++) sort(red[i].begin(), red[i].end());
        for(unsigned short i=0;i<red.size();i++) {
            for(unsigned short j=0;j<red[i].size()-1;j++) {
                if(red[i][j]==red[i][j+1]) {
                    for(unsigned short pos=j+1;pos<red[i].size()-1;pos++) red[i][pos] = red[i][pos+1];
                    red[i].pop_back(); }
            }
        }
    }
    scanf("%hu", &m);
    for(int i=0;i<m;i++) {
        unsigned short v, t;
        scanf("%hu %hu", &t, &v);
        if(t==1) {
            for(unsigned j=0;j<red[v-1].size();j++) bytes[red[v-1][j]-1] += bytes[v-1]; }
        if(t==2) printf("%llu\n", bytes[v-1]%1000000007); }
}

I use a simple DP ,but WA#10.Give me some useful tests,pls.
And I'd like to know if there is a better algo.

Recursive solution works fine! If you are getting TLE, Rethink your DP state :)

When my sort compare function is:
bool cmp(pair<int, int> p1, pair<int, int> p2)
{
    if(p1.first != p2.first)
        return p1.first < p2.first;
    else
        return p1.second >= p2.second;
}

I get WA#14.
And then delete the "=" like :
bool cmp(pair<int, int> p1, pair<int, int> p2)
{
    if(p1.first != p2.first)
        return p1.first < p2.first;
    else
        return p1.second > p2.second;
}
I get AC;

Try this test:
5
0 3
3 5
5 7
0 0

AC answer is:
2
0 3
3 5

not:
3
0 3
3 5
5 7

Input: 1440 5723
Output: 7163

Input: -2972 -2411
Output: -5383

Input: 6307 4686
Output: 10993

Input: 5185 -2017
Output: 3168

Input:

7
1 1 1 1 1 1 1
1 2
1 3
1 4
1 5
2 6
2 7
9
1 1
1 1
1 1
1 1
1 1
1 6
2 2
1 2
2 7

output:
7
8

I used segment tree, but got wa on testcase 6

This is when there's only one pole.
1
1 2
The answer should be:
1
1

what's is the wrong with this solution ?: i find the shortest path from the first vertx in the chain to the last ( with bfs) an print that path.i read my code , and I think it's correct ,say if I misunderstood the problem

CODE:-

import java.util.*;
public class titans
{
    public static void main (String[] args) throws java.lang.Exception
    {
        int ind = 0; int w = 0;
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a[] = new int[n];
        for (int i = 0; i < n; i++)
        {
            a[i] = sc.nextInt();
        }
        int largest = a[0] + a[1] + a[2];
        if (n%2 != 0 )
        {
            w = (n/2) + 1;
        }
        else
        {
            w = n/2;
        }
        for (int j = 0; j <= w; j++)
        {
            int new_long = a[j] + a[j+1] + a[j+2];
            if (new_long >= largest)
            {
                largest = new_long;
                ind = j + 2;
            }
        }
        System.out.println(largest + " " + ind);
    }
}
----------------------------------------------------------
Please tell where am I going wrong. The code is working fine on my system. Thanks in advance.
-----------------------------------------------------------
Thanks for your time but I have found the solution - thanks again!

Edited by author 28.11.2015 19:30

I solved this problem with a non-greedy solution.
Basically there are only one of the following 4 cases:
1. total number of '+' is <= 2N, problem solved;
2. There exists one column without any '+', and there also exists one column with more than 2 '+'(i.e. at least three), in this case you can "move" that two '+'s to the empty column (through two permutations);
3. Similar condition for case 2, move the row;
4. None of above is satisfied, using Hungarian Algorithm to find a best traversal.

Repeat above process until case 1 is reached.

This is not greedy and we can prove that it is correct:
Both case 2 and 3 guarantees that 1) the total number of '+'s does not change, and 2) cannot continue infinitely, i.e. it must reach case 4 at some point.
Then case 4 guarantees the total number of '+'s will be reduced at least by 1 (due to the fact that 2N + 1 is odd, and neither case 2 and case 3 is satisfied, can be easily proved)

Code:
 const Nmax=155000;
var
 Z,L1,R1:array[1..Nmax] of longint;
 A:array[1..Nmax] of char;
 N,M,Middle,L,R,i,j,k:longint;
 ch:char;

function Min(x,y:longint):longint;
begin
 if(x>y) then x:=y;
 Min:=x;
end;

BEGIN
 N:=0;
 read(ch);
 while(ord(ch)>=ord('a')) do begin
  inc(N);
  A[N]:=ch;
  read(ch);
 end;
 readln;

 inc(N);
 A[N]:='#';
 M:=N;
 read(ch);
 while(ord(ch)>=ord('a')) do begin
  inc(N);
  A[N]:=ch;
  read(ch);
 end;

 Z[1]:=N;
 R:=0;
 L:=0;

 for i:=2 to N do begin
  if(i<=r) then Z[i]:=min(R-i+1,Z[i-L+1])
  else Z[i]:=0;
  while(i+z[i]<=N)and(A[i+z[i]]=A[z[i]+1]) do inc(z[i]);
  if(i+z[i]-1>r) then begin
   L:=i;
   R:=i+z[i]-1;
  end;
 end;

 k:=0;
 L1[k]:=N+1;
 R1[k]:=N+1;

 i:=N;
 while(i>=M+1) do begin
  if(i+z[i]-1>=L1[k]-1) then begin
   inc(k);
   L1[k]:=i;
   R1[k]:=L1[k-1]-1;
  end;
  dec(i);
 end;

 if(L1[k]=M+1) then begin
  writeln('No');
  while(k>0) do begin
   for i:=L1[k] to R1[k] do write(A[i]);write(' ');
   dec(k);
  end;
 end
 else begin
  writeln('Yes');
 end;
END.

In what position brick can fall through the hole? Why program like follows doesn't work properly?

var
 a, b, c, d, e: real;
begin
 readln(a, b, c, d, e);
  if (a<=d)and(b<=e)or
     (a<=e)and(b<=d)or
     (a<=d)and(c<=e)or
     (a<=e)and(c<=d)or
     (b<=d)and(c<=e)or
     (b<=e)and(c<=d) then
    writeln('YES')
  else
    writeln('NO')
end.

Please, tell me some tests to check my program...
I have WA#2

Give me test#12, please. I tried all tests in the discussions, but still WA12

Edited by author 27.01.2014 14:42

Решая задачу обыватель мог столкнуться с проблемой того,как вводить данные. Данные водятся потоком, поэтому мы не знаем какое количество чисел войдут на проверку, для этого нам нужно использовать следующую конструкцию:

var
r:real;
..
Begin
while not seekeof do
Begin
read(r);
..
End;
..
End.

while not seekeof do - пока не конце файла, то делай то то. пропуская пробелы и переходы на новую строчку. Но так как отсутствует файлы, то он ждёт конец потока вводимых с экрана данных.
Для решения просто вставляем эту конструкцию, дополняя кодом и всё.
http://acm.timus.ru/help.aspx?topic=pascal

Edited by author 28.11.2015 11:30

here is my code if someone can help me, thanks you and greetings.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Scanner;

public class P1100 {

    public static void main(String[] args) {
       Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);

        int n = in.nextInt();
        int [] vec=new int[n*2];
        for(int i=0;i<n*2;i++)vec[i]=in.nextInt();
        int [] aux=new int[n];
        int mayor=0,menor=100;
        for(int i=1;i<n*2;i=i+2){
            if(menor>vec[i]){
                menor=vec[i];
            }
            if(mayor<vec[i]){
                mayor=vec[i];
            }
        }
        int sig=-1;
        for(int i=0;i<n;i++){
            for(int j=1;j<n*2;j=j+2){
               if(mayor==vec[j] && vec[j]!=-1 ){
                   System.out.printf(" %d %d",vec[j-1],vec[j]);
                   vec[j]=-1;

               }
               if(sig<mayor && sig < vec[j] && vec[j]!=-1){
                   sig=vec[j];
               }
            }
            mayor=sig;
            sig=-1;

        }
        out.flush();

    }
}

Hi.
Is O(N^2) solution good for this problem? I got TL on 8th test. Should I reduce constant in O() or should I find N*logN solution? It's strange that 25M operations take over 2 seconds.