drath10's blog

India ICPC — Chennai 2023 Regionals Discussion
By drath10, history, 10 months ago, In English

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.

  • Vote: I like it
  • +56
  • Vote: I do not like it

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
10 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Could you order them by difficulty ?

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

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

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

    → Reply
»
10 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        → Reply
        • »
          »
          »
          »
          »
          10 months ago, # ^ |
          ← Rev. 2   Vote: I like it +8 Vote: I do not like it

          my solution

          not sure if it would open, so

          paste bin

          → Reply
        • »
          »
          »
          »
          »
          10 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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

          → Reply
          • »
            »
            »
            »
            »
            »
            10 months ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            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

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              10 months ago, # ^ |
                Vote: I like it +8 Vote: I do not like it

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

              → Reply
            • »
              »
              »
              »
              »
              »
              »
              10 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                10 months ago, # ^ |
                ← Rev. 2   Vote: I like it 0 Vote: I do not like it

                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)

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  10 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  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

                  → Reply
»
10 months ago, # |
  Vote: I like it +37 Vote: I do not like it

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++
→ Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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.

      → Reply
  • »
    »
    10 months ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

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

    → Reply