India ICPC — Chennai 2023 Regionals Discussion

→ Обратите внимание

До соревнования
Refact.ai Match 1 (Codeforces Round 985)
4 дня
Зарегистрироваться »

*есть доп. регистрация

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3831
3	Radewoosh	3646
4	jqdai0815	3620
4	Benq	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	gamegame	3386
10	ksun48	3373

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	160
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

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

India ICPC — Chennai 2023 Regionals Discussion

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

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
10 месяцев назад
21

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

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

drath10

10 месяцев назад, # |

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

→ Ответить

ghoshsai5000

10 месяцев назад, # |

Could you order them by difficulty ?

→ Ответить

drath10

10 месяцев назад, # ^ |

-13

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

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

→ Ответить

sg0071729

10 месяцев назад, # |

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

10 месяцев назад, # ^ |

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

→ Ответить

sg0071729

10 месяцев назад, # ^ |

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

10 месяцев назад, # ^ |

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

10 месяцев назад, # ^ |

← Rev. 2 →

my solution

not sure if it would open, so

paste bin

→ Ответить

blitztage

10 месяцев назад, # ^ |

Thanks!

→ Ответить

sg0071729

10 месяцев назад, # ^ |

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

10 месяцев назад, # ^ |

← 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

10 месяцев назад, # ^ |

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

→ Ответить

sg0071729

10 месяцев назад, # ^ |

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

10 месяцев назад, # ^ |

← 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

10 месяцев назад, # ^ |

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

10 месяцев назад, # |

+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

10 месяцев назад, # ^ |

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

→ Ответить

blitztage

10 месяцев назад, # ^ |

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

10 месяцев назад, # ^ |

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.

→ Ответить

blitztage

10 месяцев назад, # ^ |

I see, thanks for mentioning!

→ Ответить

Newtech66

9 месяцев назад, # ^ |

+16

So it wasn't a coincidence that H immediately reminded me of this problem during the contest!

→ Ответить

Соревнования по программированию 2.0

Время на сервере: 05.11.2024 19:19:41 (j3).

Десктопная версия, переключиться на мобильную.

При поддержке