Yaa i have the idea of O(n^2).First you can can calculate
the slopes of all lines in O(n^2).Create a class which contains the 2 points and the slope of the line joining two points.Note that there will be n(n+1)/2 nodes and define operator == as: slopes are equal and one point must be common to both the lines.

Is it DFA?

thnx a lot  c_pp
atleast i learn something

> Is there any polynomial time solution?
yes.

- if there is a cycle the answer is always "yes"
- if there is a knot (ex. 2 2 edges), the answer is also "yes"
- if graph is multigraph, yes too

if all above is false just find the longest path in a tree and
play with it's value in comparsion with route length

I've got AC! The main observation is that no two queens can be in the same row or column.
Thus, we make an array perm[i], which stands for queen in the ith row and perm[i]th column. The problem is to find the number of permutations, which differs from the initial by 3 elements and check for each possibility whether we have conflicts on the diagonals. perm[i] is the initial permutation. I hope this hint was helpful!

I also got WA for test 4.....so I started to try some self made test cases.....and I came across this one :
5 4
2 0 1 3
My output : NO.
Correct Output should be YES.

I will have to rethink my approach.....maybe you have the same problem as well.

case 3 3 1 2 3 helped me in test 4.
But anyway it's better to write your own test case generator.

Edited by author 18.04.2020 04:47

7 4
2 5 7 5

First i did not understand this problem.but your suggestions help me.thanks!!!And it is really very practical, realistic and easy problem!!

No comments

Worm can move both left and right. Stop for a while and think about it.

Just take two books and try - you will find answer immediately

I fully agree with you.How could the answer for sample input be 2.

Edited by author 02.10.2020 16:52

n=0
Answer 10

Ok, looks like in my case the format of input data in tests #2 and #6 is differ from the one in the example. Accepted Go code is:


package main

import (
    "fmt"
    "sort"
)

type city struct {
    n, x, y int
}

func main() {
    var n int
    fmt.Scan(&n)
    m := make([]city, n)

    for i := 0; i < n; i++ {
        m[i].n = i + 1
        fmt.Scan(&m[i].x, &m[i].y)
    }

    sort.Slice(m, func(i, j int) bool {
        if m[i].x < m[j].x {
            return true
        }
        return false
    })

        for i := 0; i < n; i += 2 {
        fmt.Println(m[i].n, m[i+1].n)
    }
}


time:   0.14
memory: 2 044 КB


Edited by author 29.09.2020 01:10