My python 3.3 program has TLE in problem 12.
Has anyone a hint to speed up this algorithm.

My AC program give answer 3 for a following test:
2
4 1 2 3 4
4 1 2 5 4
3 1 2 3

But I think answer must be: 3 4

Am I right?

the length of a route is determined by the number of spans only

But what's span?!

Could you give me some test data ?

I did get AC on this. I used queue and in_degree array. First pushed zero in_degree elements in queue and then visited neighbour for each element in front , reduced in_degree of neighbours by 1 each time to indicate one parent has reduced.

Edited by author 29.04.2020 12:08

import java.util.Scanner;

public class Test{
    public static void main(String[] args) {

   Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
   int b = sc.nextInt();
   int c = sc.nextInt();
   if(a>=0 && b>=0 && c>=0 && a<=100 && b<=100 && c<=100 && a<=b && b<=c ){
       if(a==0 && b==0 || a==0 && b==1|| b==0||c==0||(a==1&& b==1&&c==1)){
    System.out.println(a-b-c);
    }
      else  System.out.println(a-b*c);
}
    }
}

    Can somebody give me some tests?
    I can;t find what's wrong with my prog.
    Thanks a lot.

double dif = Math.abs(oform - neoform);
if (oform > neoform && dif > 0.000001) {
            System.out.println("Cash");
        } else {
            System.out.println("Insurance");
        }

#include <iostream>
#include <string>
#include<vector>
using namespace std;
string turn(string s)
{
    string news;
    for (int i = s.length() - 1; i >= 0; i--)
        news.push_back(s[i]);
    return news;
}
int main()
{
    string s; string news;
    getline(cin, s);
    vector <int> l;
    vector <string> counts;
    for (int i = 0; i < s.length(); i++)
    {
        int n = s.length();
        for (int j = 1; j <= s.length() - n + 1 && (s.length() - n + 1) <= (s.length() - i); j++)
        {
            news = s.substr(i, j);
            if (turn(news) == news && news.length() > 1)
            {
                l.push_back(news.length()); counts.push_back(news);
            }
            n--;
        }

    }
    int maxl = 0; string saves;
    for (int k = 0; k < l.size(); k++)
    {
        if (l[k] > maxl)
        {
            maxl = l[k]; saves = counts[k];
        }
    }
    cout << saves;
}

If you have WA25 and low try this test:

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

I can't figure out where my mistake is. Can someone give me some tests?

import java.util.*;
public class Maximums {
    public static void main(String[] args) {
        Scanner scn = new Scanner(System.in);
        int N = -564646878;   // random value hehehehe
        while (N != 0) {
            N = scn.nextInt();
            if (N == 0) {
                break;     // As per the problems requirement it should terminate at 0
            } else if (N == 1) {
                System.out.println(1);
            } else {
                N = N + 1;    // problems indexing are upto N
                int[] arr = new int[N];    // creating an array to create desired sequence
                arr[0] = 0; arr[1] = 1;   // initialising the array with the given values in question
                int max = Integer.MIN_VALUE;  // to start with
                for (int i = 2; i < N; i++) {
                    if (i % 2 == 0) {
                        arr[i] = arr[i / 2];     // for even indexes
                        if (arr[i] > max) {
                            max = arr[i]; // comparing
                        }} else {
                        arr[i] = arr[(i - 1) / 2] + arr[((i - 1) / 2) + 1];  // for odd indexes
                        if (arr[i] > max) {
                            max = arr[i];// comparing
                        }}}
                System.out.print(max);   // finally printing the max value upto the given index 'N'.
                System.out.println();   // for new line ( P.S. I know i could have made the upper line to println but that's boring
                }}}} /// Happy Coding Dudes n Dudettes

why is the 10th element 4? isn't it 3?

a silly mistake got me wa. A simple testcase helped me. here it is-
3
3 2 1

Edited by author 12.04.2020 20:09

answer will be long or long long.

I mean, there obviously must be some compiler optimizations that enable the O(K^2) algorithm to be accepted for the worst case.

For example, I've tried binary search, given that this is a convex function, and the amount of branch prediction misses slows the thing down a lot.

I've been looking at godbolt.org output and can't figure out what is happening here.

firstly i get wa on 8, then 9,then 13
And finally AC on .001

Got AC with a program that had a 100% wrong answer on this test:
1 5 2
1 2
1 4
 _ _ _ _ _
| |X| |X| |
Definitely should be 3 (as we got 3 1x1 stripes separated by black cells), my prog got 2 and got AC. Dont know if adm reads this but why not - good to know for everyone

Also hi to all ITMO vtalgo dudes <3

Fucking participants!
This problem is the most stupid problem I have ever seen.
Why the problem is to output the calendar but not to find the day of
week? It is very simple to find but it is IMPOSSIBLE to output! The
sample does not give the answers to many questions.
Why I MUST GUESS, GUESS and GUESS again?
...
Diman_YES[UT], the leader of Universal Team

I wa many times.
Thank you very much!