My code: What's wrong???

#include <algorithm>
#include <vector>
#include <utility>
#include <stdio.h>

#define ARRAY_SIZEOF(a) (sizeof(a) / sizeof(a[0]))
#define INF 0x7fffffff

using namespace std;

typedef long long int lli;

int M, N;
int C[100][500];
int T[101][500];
int m1[500];
int m2[500];
int path[500*500];

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
#endif
    int i, j, k;

    scanf("%d%d", &M, &N);
    for (i = 0; i < M; i++) {
        for (j = 0; j < N; j++) {
            scanf("%d", &C[i][j]);
            C[i][j]++;
            T[i+1][j] = INF;
        }
    }

    for (i = 1; i <= M; i++) {
        m1[0] = T[i-1][0] + C[i-1][0];
        for (j = 1; j < N; j++) {
            m1[j] = min(m1[j-1], T[i-1][j]) + C[i-1][j];
        }
        m2[N-1] = T[i-1][N-1] + C[i-1][N-1];
        for (j = N-1; j-- > 0; ) {
            m2[j] = min(m2[j+1], T[i-1][j]) + C[i-1][j];
        }
        for (j = 0; j < N; j++) {
            T[i][j] = min(m1[j], m2[j]);
        }
    }

    int jmin = 0;
    for (j = 1; j < N; j++) {
        if (T[M][j] < T[M][jmin]) {
            jmin = j;
        }
    }
    i = M;
    j = jmin;
    k = 0;
    do {
        path[k++] = j + 1;
        int m = T[i-1][j];
        jmin = j;
        if (j-1 >= 0 && T[i][j-1] < m) {
            jmin = j-1;
            m = T[i][jmin];
        }
        if (j+1 <  N && T[i][j+1] < m) {
            jmin = j+1;
            m = T[i][jmin];
        }
        if (m == T[i-1][j])
            i--;
        else
            j = jmin;
    } while (i);

    for (i = 0; i < k; i++) {
        printf("%d ", path[k-1-i]);
    }
    printf("\n");

    return 0;
}

I sort the the 2^k states by the bits it contains, then check the states in order, and always TLE #22

Then, I choose a state randomly in the 2^k states and check if it's legal, and get accepted……

part of my code:

 63     int ans = (1 << k) - 1;
 64     int tot = 1 << k;
 65     int times = 0;
 66     while (tot > 0 && (times * realm < (500000000))) {
 67         int now = rand() % tot;
 68         if (countBit(arr[now]) < countBit(ans)){
 69             memset(visit,0,sizeof(visit));
 70             times++;
 71             if (dfs(0,arr[now])) {
 72                 ans = arr[now];
 73             }
 74         }
 75         arr[now] = arr[--tot];
 76     }

try this test:
11
+
11
#####
22

Для каждого места (буквы + расстояния между ними) будем проверять длину макс подпалиндрома с помощью бин поиска (его длину).
Осталось за О(1) проверить является ли эта подстрока палиндромом, что можно сделать с помощью хешей (заранее посчитать хэш для каждого префикса, и высчитывать хэш подстроки в обе стороны и сравнивать)

I am getting WA for test#15 with my C++ code. Is there anybody who can give an explanation why this is happening?

import java.math.BigInteger;
import java.util.Scanner;

public class Main {

    public static BigInteger step(int a, int b)
    {
        BigInteger temp=BigInteger.valueOf(a);
        for (int i=1; i<b; i++)
        {
            temp=temp.multiply(BigInteger.valueOf(a));
        }
        return temp;
    }

    public static void main(String[] args)
    {
        Scanner inp=new Scanner(System.in);
        int n=inp.nextInt();
        int m=inp.nextInt();
        int y=inp.nextInt();
        boolean f=false;
        for (int i=0;i<m;i++)
        {
            BigInteger x=step(i,n);
            BigInteger c=x.mod(BigInteger.valueOf(m));
            if (c.compareTo(BigInteger.valueOf(y))==0)
            {
                System.out.print(i+" ");
                f=true;
            }
        }
        if (f==false)
            System.out.print("-1");
    }
}

I don't know how to do it faster, than now. Please help me.

Edited by author 03.02.2013 15:10

I had the same problem, and solved it after changing all c++ io functions from <iostream> to <cstdio>

Почему в условии задачи сказано, что начальная и конечная точки маршрута фиксированы, а в примерах конечные точки получаются разными?

Edited by author 08.07.2013 01:51

What is optimal asymptotic for this problem? My algo has O(M*log(N)) where N - length of scary Martian word, and M - length of text of Ovchinnikov's book, but i have TLE on 21th test

Better correct the memory usage by Java programs. You can simply decrease memory by 200 KB or just increase memory limits for some problems that can't be solved on Java or C#.

                Язык запрещен для данной задачи
                Language is not allowed for this problem

Edited by author 26.04.2013 17:32

use DP, mainly involved with:
  permutation  and  combination
A(n,k)
C(n,k)

or, you can think about there is a x-Axis.

two points (a, b)  can be placed  --a--b--    --b--a--  ||  --(ab)--    the first two solution has two groups, and the last one has one groups for the overlap.

This problem is very easy!.
if N=1 output is  0;
if N=2 and first language=second language output is 0;
if N=2 and first language not = second language output "first"-"second" (fist and second - it's name of language)
If N>2 if there are two or many equal languages output "Impossible"
If N>2 if all languages different you print N and print all name languages this your language.
Your language it is thought up string of latin letters. But dangerous this it. your language will be string len<10 and latin letters in small case.

Tests:
input:
1
a
output:
0

input:
2
a
a
output:
0

input:
2
a
b
output:
a-b

input:
3
a
b
c
output:
a-qwerty
b-qwerty
c-qwerty

input:
3
a
a
b
output:
Impossible

tell me, please, what input in test 5.

Can you give me some "extra" test or smth like that... My prog passed all my tests but i get wa#3...

Thnx!

request for any optimizations possible for python solution: not it get TLE #42

import sys

#sys.stdin = open("smalltest.txt")
#sys.stdin = open("input.txt")

top = 0
stack = [0] * 2000020
input = sys.stdin.read().split()
operations = int(input[0])
ans = ""

for i in xrange(operations) :
    op = int(input[i+1])
    if op > 0 :
        stack[top] = op
        top += 1
    elif op < 0 :
        top -= 1
        ans += str(stack[top]) + "\n"
    else :
        if operations - i > top :
            l = max( 0, top - operations + i )
            cnt = top - l
            stack[top:top+cnt] = stack[l:top]
            top += cnt

sys.stdout.write( ans )

I think the problem is little unclear.
It does not mention if the centipede continues putting shoes with the same strategy for right foot, when it is so.


Edited by author 03.07.2013 19:21

Edited by author 03.07.2013 17:04

you must print n^2 and n.

You can solve it o(1) just precalc answers fir all test by brute forse, than put it to array.
Proffit