You are not logged in. Please login at www.codechef.com to post your questions!

×

CHEFNIL - Editorial

0
1

PROBLEM LINK:

Practice
Contest

Author: Dmytro Berezin
Tester: Istvan Nagy
Editorialist: Oleksandr Kulkov

DIFFICULTY:

CHALLENGE

PREREQUISITES:

none

PROBLEM:

You have matrix $A:M \times N \times N$. For each $1\leq k \leq M$ you choose $1\leq i_k,j_k\leq N$ which gives you $A_{kij}$ points. For each $k>1$ you draw segment from $(i_{k-1},j_{k-1})$ to $(i_k,j_k)$ on the plane and you can only choose such $(i_k,j_k)$ that this segment doesn't intersect any previous segments. Your aim is to maximize sum of scored points.

Also you know that for generation of $A_{kij}$ was used one of two types of distributions:

  1. $\left\lfloor 100 \cdot e^{d-100} \right\rfloor+1$ where $d$ is drawn from uniform real distribution on $[0;100]$.
  2. $\min_k[100\cdot2^{-X+d_k}+1]$ over $10$ iterations where $d$ is drawn from real distribution on $[0;20]$ and $X$ denote minimum of Manhattan distances of $(k,i,j)$ from cells $(k,1,1),~(k,1,N),~(k,N,1),~(k,N,N)$ and $(k,N/2,N/2)$ and if value of element exceeds $100$ we keep it to 100.

EXPLANATION:

Let us first talk about the first probability distribution. In this distribution, the high scoring values are scattered randomly around. So, the problem is almost like finding a tour with maximum possible score. Let us first identify some top values for each of the matrix, and now will try to take them using a tour.

One possible solution is to just do the greedy by joining the adjacent pairs without taking care of that they intersect, when they intersect, just break out your solution. The other possible solution is to fix the order in which you are certain that there won't happen any intersection, for example increasing $x$, or increasing $y$. Now, in this scenario, do a greedy approach to maximize the score.

The second distribution is more or less centered around the border and around the center. In that case, you are better in case you visit the cells in a connected component first type of the tour. For example, start from a corner and take some part of that corner by visiting (row 1, left to right, and then row 2 right to left and so on, in a connected fashion). This way visit the corners first, and finally come to the mid area of the rectangle and apply similar strategies there.

Some sort of simulated annealing/hill climbing type optimizations can be applied too in order to improve these strategies even more. (It would be easier to improve in first case). Basically, we can try changing some of the intermediate cells of the path to some other node, this will be our transition. The top solution applies mentioned hill climbing strategy.

AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution will be updated soon.
Tester's solution can be found here.

RELATED PROBLEMS:

asked 18 Nov '17, 00:11

melfice's gravatar image

2★melfice
811133
accept rate: 0%

edited 21 Nov '17, 21:54

admin's gravatar image

0★admin ♦♦
19.1k348495533


@vijju123 How to approach this type of problem(challenge)? I find it very difficult to understand the problem and code it.

link

answered 19 Nov '17, 10:56

paras2411's gravatar image

1★paras2411
0
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×701
×301
×15

question asked: 18 Nov '17, 00:11

question was seen: 420 times

last updated: 21 Nov '17, 21:54