India ICPC — Chennai 2023 Regionals Discussion

Блог пользователя drath10

Автор drath10, история, 2 года назад, По-английски

This is a discussion blog for the ICPC India Chennai regionals 2023.

Link — ICPC Chennai regionals 2023

Since most of the problems went unsolved, you can add your solutions in the comments or hints to the problems. Feel free to add your opinions about the contest.

drath10
2 года назад
21

Комментарии (21)

Написать комментарий?

drath10

2 года назад, скрыть # |

Auto comment: topic has been updated by drath10 (previous revision, new revision, compare).

→ Ответить

ghoshsai5000

2 года назад, скрыть # |

Could you order them by difficulty ?

→ Ответить

drath10

2 года назад, скрыть # ^ |

-13

G>C>I>D>H>rest of them.

Didn't solve the other problems but the five problems were very standard.

→ Ответить

sg0071729

2 года назад, скрыть # |

For B, simple brute force with big int template works.

For A ( nothing concrete ), my thought process was that a trie and some preprocessing we could reach a string $$$s_i$$$ such that $$$s_x$$$ in the answer is a prefix of $$$s_i$$$ only $$$\sqrt{L}$$$ string would be considerable for $$$s_x$$$ using this, however I was not able to get anything further

For E ( nothing concrete ), I think it was observational

For F ( nothing concrete ), I think trying greedily increasing weights which increases the answer by least amount should work, however I was not able to prove it or even fast track this for finding which edge that corresponds to the minimum increase

→ Ответить

blitztage

2 года назад, скрыть # ^ |

did you manage to get correct answer verdict? if yes, can you link your submission?

→ Ответить

sg0071729

2 года назад, скрыть # ^ |

for B yes I was able to get the correct verdict, I represented numbers in base $$$2^{63}$$$

I initially assumed the actual solution would involve usage of log but that didn't seem necessary

→ Ответить

blitztage

2 года назад, скрыть # ^ |

we did face precision issues with log, some team got TLE using bigint I heard hence asked. Would be great if you could link your submission

→ Ответить

sg0071729

2 года назад, скрыть # ^ |

← Rev. 2 →

my solution

not sure if it would open, so

paste bin

→ Ответить

blitztage

2 года назад, скрыть # ^ |

Thanks!

→ Ответить

sg0071729

2 года назад, скрыть # ^ |

you could avoid precision issues by maintaining the actual thing till a certain value then its log probably

tle with big int is easily avoidable, just a matter of reducing constants

→ Ответить

blitztage

2 года назад, скрыть # ^ |

← Rev. 2 →

you could avoid precision issues by maintaining the actual thing till a certain value then its log probably

Did that, it doesn't work. Realised one issue could be a(2^x — 1) = b(4^x — 1)/3 type of things. Which would not be considered equal in log though we want it to. Tried to handle these cases separately, but still i am missing something

→ Ответить

GusFring

2 года назад, скрыть # ^ |

Not the prettiest solution but it works: https://codedrills.io/submissions/949900

→ Ответить

sg0071729

2 года назад, скрыть # ^ |

the idea is that if the numbers are both less than B u compare them, if only one is greater u already have ur answer. If both are greater, compare log(digit1(base1^x)) and log(digit2(base2^y)), from there as both numbers are bigger than B if the difference in log is too great they are already far apart as each is bigger than B. If they are too close, equality occurse for only ({2,4},{2,8},{2,16},{4,8},{4,16},{8,16},{3,9}) if B is large enough.

→ Ответить

blitztage

2 года назад, скрыть # ^ |

← Rev. 2 →

Yeah, I get it, but when we ran this in contest, it didn't work (as in, gave wrong answer on samples, it's possible i misimplemented)

→ Ответить

sg0071729

2 года назад, скрыть # ^ |

In a live contest, it is very understandable that this could take 1-2 hrs to pass on a good day and more if you just miss something here or there.

My suggestion would have been, in case I was a part of your team, to first do the brute force so that we can check where our working solution gets it wrong and then adjust accordingly.

In live contests, more often than not a simple mistake can take up a lot of time, for our team I missed that in $$$H$$$ the term in summation had an $$$n$$$ so would lead to $$$n^2$$$ term, this alone took me 3 hrs to rectify

→ Ответить

JaySharma1048576

2 года назад, скрыть # |

+37

I was the author of E and H and here is the model solution for E (Hex-Hopping Horsey):

First, 3-color the hex grid as below:

11 x 11 grid colored

It is not hard to see that in this coloring, the "short" horsey moves will always connect cells of the same color.

Then try to construct Hamiltonian paths/cycles joining all cells of a single color. For any given $$$n \geq 3$$$, you can always construct atleast $$$1$$$ Hamiltonian cycle and atleast $$$2$$$ Hamiltonian paths. Then break the cycle and connect its ends to one of the ends of each of the other paths using "long" Horsey moves to get a single Hamiltonian path visiting all cells. Two "long" moves are the minimum you need in any case. The following is an example of how to do it for an $$$11\times 11$$$ grid:

Hamiltonian cycle for green cells

Hamiltonian path for blue cells

Hamiltonian path for yellow cells

Merged Hamiltonian path

Notice that in the construction above, the first and the last cells are adjacent to each other. You can always achieve this for all valid $$$n$$$ by choosing the correct color for the cycle and the correct ends of the paths to join to the cycle.

You can observe that the pattern of the answer depends on the value of $$$n\bmod 3$$$. The following are examples of the construction for different values of $$$n\bmod 3$$$:

9 x 9 (n mod 3 = 0)

10 x 10 (n mod 3 = 1)

11 x 11 (n mod 3 = 2)

No answer exists for $$$n=2$$$ and you can hardcode the answer for small $$$n$$$ such as $$$n=3$$$. For the rest, you can follow the construction patterns.

Solution in C++

/*...................................................................*
 *............___..................___.....____...______......___....*
 *.../|....../...\........./|...../...\...|.............|..../...\...*
 *../.|...../.....\......./.|....|.....|..|.............|.../........*
 *....|....|.......|...../..|....|.....|..|............/...|.........*
 *....|....|.......|..../...|.....\___/...|___......../....|..___....*
 *....|....|.......|.../....|...../...\.......\....../.....|./...\...*
 *....|....|.......|../_____|__..|.....|.......|..../......|/.....\..*
 *....|.....\...../.........|....|.....|.......|.../........\...../..*
 *..__|__....\___/..........|.....\___/...\___/.../..........\___/...*
 *...................................................................*
 */
 
#include <bits/stdc++.h>
using namespace std;

struct cell
{
    int x, y;
};

vector<cell> find_path(int n, cell bottom_left)
{
    bool up = true;
    int x = bottom_left.x;
    int y = bottom_left.y;
    vector<cell> path;
    while(y<=n)
    {
        path.push_back({x,y});
        if(up)
        {
            if(x+2<=n)
                x+=2;
            else
            {
                if(x==n)
                    x--;
                else
                    x++;
                if(x%2==0)
                    y++;
                else
                    y+=2;
                up = false;
            }
        }
        else
        {
            if(x-2>=1)
                x-=2;
            else
            {
                if(x==2)
                    x--;
                else
                    x++;
                if(x%2==0)
                    y++;
                else
                    y+=2;
                up = true;
            }
        }
    }
    return path;
}

vector<cell> find_cycle(int n, cell bottom_left)
{
    int x = bottom_left.x;
    int y = bottom_left.y;
    vector<cell> cycle;
    while(y<=n)
    {
        cycle.push_back({x,y});
        if(x+2<=n)
            x+=2;
        else
        {
            if(x==n)
                x--;
            else
                x++;
            if(x%2==0)
                y++;
            else
                y+=2;
        }
    }
    x = cycle.back().x;
    y = cycle.back().y;
    cycle.pop_back();
    bool up = false;
    while(y>bottom_left.y)
    {
        cycle.push_back({x,y});
        if(up)
        {
            if(x+2<=n-2)
                x+=2;
            else
            {
                if(x==n-2)
                    x--;
                else
                    x++;
                if(x%2==0)
                    y-=2;
                else
                    y--;
                up = false;
            }
        }
        else
        {
            if(x-2>=1)
                x-=2;
            else
            {
                if(x==2)
                    x--;
                else
                    x++;
                if(x%2==0)
                    y-=2;
                else
                    y--;
                up = true;
            }
        }
    }
    return cycle;
}

void rearrange_cycle(vector<cell> &cycle, cell start)
{
    int n = cycle.size();
    for(int i=0;i<n;i++)
    {
        if(cycle[i].x==start.x && cycle[i].y==start.y)
        {
            vector<cell> temp;
            for(int j=0;j<n;j++)
                temp.push_back(cycle[(i+j)%n]);
            cycle = temp;
            break;
        }
    }
}

void solve(int tc)
{
    int n;
    cin >> n;
    vector<cell> path;
    if(n<=2)
        cout << -1 << '\n';
    else if(n==3)
    {
        path.push_back({1,2});
        path.push_back({3,2});
        path.push_back({2,3});
        path.push_back({1,1});
        path.push_back({2,2});
        path.push_back({3,1});
        path.push_back({1,3});
        path.push_back({3,3});
        path.push_back({2,1});
        for(int i=0;i<path.size();i++)
            cout << path[i].x << " ";
        cout << '\n';
        for(int i=0;i<path.size();i++)
            cout << path[i].y << " ";
        cout << '\n';
    }
    else
    {
        vector<cell> path1,path2;
        vector<cell> cycle;
        if(n%3==0 || n%3==2)
        {
            path1 = find_path(n,{1,2});
            reverse(path1.begin(),path1.end());
            cycle = find_cycle(n,{1,1});
            rearrange_cycle(cycle,{3,4});
            path2 = find_path(n,{2,1});
        }
        else if(n%3==1)
        {
            path1 = find_path(n,{1,1});
            reverse(path1.begin(),path1.end());
            cycle = find_cycle(n,{1,2});
            rearrange_cycle(cycle,{2,3});
            path2 = find_path(n,{2,1});
        }
        for(int i=0;i<path1.size();i++)
            cout << path1[i].x << " ";
        for(int i=0;i<cycle.size();i++)
            cout << cycle[i].x << " ";
        for(int i=0;i<path2.size();i++)
            cout << path2[i].x << " ";
        cout << '\n';
        for(int i=0;i<path1.size();i++)
            cout << path1[i].y << " ";
        for(int i=0;i<cycle.size();i++)
            cout << cycle[i].y << " ";
        for(int i=0;i<path2.size();i++)
            cout << path2[i].y << " ";
        cout << '\n';
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int tc=1;
    cin >> tc;
    for(int ttc=1;ttc<=tc;ttc++)
        solve(ttc);
    return 0;
}

→ Ответить

sg0071729

2 года назад, скрыть # ^ |

Nice question, thanks for mentioning your solution, it is really appreciated

→ Ответить

blitztage

2 года назад, скрыть # ^ |

I think a few of the parts of the problem could be removed and it would have been fun to solve. This version felt overwhelming atleast in the team contest setting. We couldn't finish it in time even after getting the 3-color idea very fast

→ Ответить

JaySharma1048576

2 года назад, скрыть # ^ |

The original problem proposal had neither the shortest path constraint nor the constraint on the starting and ending cells being adjacent. But soon we realized that Warnsdorf's heuristic works quite well for hexagonal boards too. First we added only the shortest path condition but it was again possible to make the heuristic pass all tests by adding some more greedy conditions and trying a few different starting cells. Finally the adjacency condition was added to prevent heuristic solutions from passing or atleast making those solution more difficult than the model solution.

→ Ответить