thanhchauns2's blog

Solutions for April Fools Day Contest 2023 in one line (Collection)
By thanhchauns2, history, 20 months ago, In English

Hi, I collected the solutions for the problems of April Fools Day Contest 2023. Before the official editorial being posted, we can discuss about the problems here.

P/s: The editorial was published.

1812A - Are You a Robot?

Solution

1812B - Was it Rated?

Solution

1812C - Digits

Solution

1812D - Trivial Conjecture

Solution

1812E - Not a Geometry Problem

Solution

1812F - Factorization

Solution

1812G - Colour Vision

Solution

1812H - Expected Twist

Solution

1812I - Mountain Climber

Solution

1812J - Unmysterious Language

Solution
  • Vote: I like it
  • +28
  • Vote: I do not like it

»
20 months ago, # |
  Vote: I like it +8 Vote: I do not like it

After about 300 — 400 steps, a positive number will be decreased down to 1.

Where did you get those numbers from? the conjecture asks whether every positive integer will eventually get to 1 by applying the operation however many times you'd like.

The biggest answer allowed (103 digits) will take more than 3,000 operations to reach 1, but it might take millions, or never reach 1 (proving the conjecture false), which means that the [REDACTED] part must be pretty small, or the grader wouldn't be able to evaluate a very large submission definitively.

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

    Here. Or I could remember the wrong number, I watched it a long time ago.

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

      I think it is around $$$350$$$:

      void solve(){
	int mx = 0;
	for (int n1 = 1; n1 < 100000; n1++){
		int steps = 0;
		for (int n = n1; n != 1; steps++){
			if (n & 1) n = 3 * n + 1;
			else n /= 2;
		}
		mx = max(mx, steps);
	}
	cout << mx << '\n';
}
      → Reply
      • »
        »
        »
        »
        20 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        That's for numbers up to 1e5, we're talking about numbers up to 1e1000

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

    I believe the grader can just simulate $$$10^5$$$ ish steps to check if an answer is valid or not. In testing, the best number I could find was around $$$2.5 \cdot 10^4$$$ steps by just randomly generating $$$1000$$$ digit numbers and running them. In any event, it is probably impossible to find a positive integer that could work on the given constraints, and if you could, you could probably write a paper on it!

    → Reply