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?

The minimal output is: 1-2*5 = -9.

Edited by author 04.03.2020 22:45

consider follow string: ABZZBBBZZA.
2 polindroms: ZZBBBZZ and ABA - correctly for this problem?

Python 3.6


a=int(input())
if a<=4 and a>=1:
    print("few")
    if a<=9 and A>=5:
        print("several")
        if a<=19 and a>=10:
            print("pack")
            if a<=49 and a>=20:
                print("lots")
                if a<=99 and a>=50:
                    print("horde")
                    if a<=249 and a>=100:
                        print("throng")
                        if a<=499 and a>=250:
                            print("swarm")
                            if a<=999 and a>=500:
                                print("zounds")
                                if a>=1000:
                                    print("legion")

Ya popitalsya perebrat' vse varianti dlya N = 6 i smog naschitat' tolko 14 vot oni:
1. WRWRWR    9. WRWRBW
2. RWRWRW   10. RWRWBR
3. WBRWRW   11. WBRBWR
4. RBWRWR   12. RBWBRW
5. WRBWRW   13. WRBWBR
6. RWBRWR   14. RWBRBW
7. WRWBRW   15. ??????
8. RWRBWR   16. ??????
Kakie dva ya upustil?

#include<stdio.h>


int n,k,answer;
int main()
{
scanf("%d %d",&n,&k);
int len = n/2;


if(k==len)
{
printf("0");
return 0;
}
else if(k<len)
{
answer = len - k;
}
else
{
answer = k - len - 1;
}

printf("%d",answer);
}

3
1 2 10
2 3 100
3 4 1000
1
1 2 10

Answer: 2 2 3 100 3 4 1000

#include <bits/stdc++.h>

int main()
{
    int n,i,j,k;

    scanf("%d",&n);

    for(i=1; i<=n; i++){
            if(i==1 && n!=1){
                printf("(");
            }
        for(j=1; j<=i; j++){
            if(i==1 && n==i){
                printf("(sin(1))+%d",n);
            }
            else if(i==1){
                printf("(sin(1)+%d)",n);
            }
            else {
                if(j%2==0){
                    printf("-sin(%d",j);
                }
                else if(j==1){
                    printf("sin(%d",j);
                }
                else {
                    printf("+sin(%d",j);
                }
                if(j==i){
                    //printf(")");
                    for(k=1; k<=i; k++){
                        printf(")");
                    }
                }
            }
        }
        //if(i==n){
          //  printf(")");
       // }
       if(i!=1 && i!=n){
        printf("+%d)",n+1-i);
       }
       else if(i!=1 && i==n){
        printf("+%d",n+1-i);
       }

    }
    return 0;
}

My algorythm has maximum O(n^2) complexity. I have TLE 18 test.
But, when i artificially set limits for n (amount of layers) to 200 and for k (amount of bricks in a single layer) to 290, my program still gets TLE 18 test, i really have no idea how is it possible. It should get WA\AC if inputs are more than limits since i do not see any possibility of an endless cycle in my algo.

Edited by author 27.02.2020 21:19

Edited by author 27.02.2020 21:36

Could anybody give me some tricky tests? This problem seems to be trivial but I got WA. I guess it's all about format of result.

Just a sort problem

My O(N^2) solution works for 0.187s
but 10000 * 10000 = 1e8, it means that O(N^2) solution should work only for 1
second (not less), but in this task there is 0.5 sec and O(N^2) solution gets AC

5
0 -100000000
1 -100000000
1 -99999999
-1 100000000
0 100000000
I think, this answer is wrong:
0 -100000000
1 -100000000
-1 100000000
But my AC program doesn't think so.

I have WA#2 and i don't understand what is wrong..
If I understood problem correctly, my program works well on all tests, which I tried.

Edited by author 23.02.2020 18:27

    For each vertex in tree find the nearest vertex from the way to root, in which we need to change direction. If such vertex doesn't exist, let it be -1. Let's call this vertex as bad[V], where V - some vertex in tree.
    To answer on query for vertex X, let's travel in "bad" array from X until we meet bad[X]=-1. Let's save visited vertices (excluding query vertex X) to some array (let's call this array "change"). Now it's quety obvious, that we need to change directions only in those visited vertices to "activate" path from root to leaf.     Before changing values in "bad" array for vertex from X to root, let's take some vertex V from "change" array. Before query there was a set of vertices which have the same "bad" vertex as a V (bad[V]=bad[V_1]=bad[V_2]=...=bad[V_n], V_i - vertex from the set), and now we need to change their "bad" value to V, because we change direction in vertex V.
    Finally, we need to set bad[V]=-1 to all vertices from X to root.
    To do all operations efficiently we can use heavy-light decomposiotion + segment tree. So, the total complexity would be O(N + Q*(log(N))^2), N - number of vertices in tree.

Edited by author 06.06.2019 17:11

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
 int a;
 int n;
 cin >> n;
 vector<int> v;
 for (int i = 0; i < n; i++) {
  cin >> a;
  v.push_back(a);
 }
 n = 0;
 sort(v.rbegin(), v.rend());
 for (int i = v.size()-1; i > (v.size()-2) / 2; i--)
  n += (v[i]+1)/2;
 cout << n << endl;
}

Sort the n teams and take the first (n/2 + 1) team's people (by people i mean, array[i]/2 + 1).

If you have problem understanding what i have just written or for better understanding, give this a go : https://ideone.com/vD6SAm

Well, you have to know how to determine the distance between two points first.
It can be calculated by, dis = sqrt((x1-x2)^2+(y1-y2)^2).

You can say that, we can just calculate the distance in between the points but why the raidius of the nails are given. Its because the rope is wrapped around each and every nails. But the rope is not in fully contact with nails. The more nails we get, the less contact we have in between rope and nails.

The amount of which the rope is in contact with nail is : s = parameter of a nail/the number of nails.

So we are just required to print out : d(d is the sum of the distance between them) + number of nails * s(s is the amount which the rope is in contact with nails)

If you have problem understanding my word or for better understanding, give this a go : https://ideone.com/t1M3rK

Edited by author 21.02.2020 01:31

List<long> coll = new List<long>();
            List<decimal> answer = new List<decimal>();
            List<string> a = new List<string>();
            string line;
            while (true)
            {
                line = Console.ReadLine();

                answer.Clear();
                coll.Clear();
                a.AddRange(line.Split());
                a.RemoveAll(x => x.Equals(""));

                for (int i = 0; i < a.Count; i++)
                {
                    coll.Add(long.Parse(a[i]));

                }

                for (int i = 0; i < coll.Count; i++)
                {
                    var d = (decimal)Math.Sqrt(coll[i]);
                    answer.Insert(0, d);
                }
                Console.Clear();
                for (int i = 0; i < answer.Count; i++)
                {

                    Console.WriteLine(answer[i].ToString("0.0000##"));
                }
            }


Edited by author 21.02.2020 00:40