sinovels Chapter 142 Rules
Chapter 142 Rules
Chapter 142 Rules
A round of enthusiastic applause erupted.
Most of the audience members were staring at the big screen, waiting to see the rules.
The big screen lit up.
Team on-site coding challenge. Three-hour time limit. One major problem, divided into three progressive stages.
Title: Design a Chinese input method engine.
When Lin Dong saw this line of text, his fingers paused on the keyboard for a moment.
Input method.
The screen, battery, motherboard, casing, touch algorithm, antenna, and driver are all included, but the input method still uses an open-source solution, resulting in a mediocre experience and complicated adaptation.
He originally planned to make a set after the New Year, but now the final question is about input methods.
His lips twitched slightly.
Take it away as soon as it's done.
Phase 1 (60 minutes): Core Index.
Design an index structure from Pinyin to Chinese characters. Given a dictionary (approximately 10 entries), the system should support Pinyin input and return a list of matching candidate words. The response time should not exceed 20ms, and the memory usage should not exceed 1MB.
Phase Two (60 minutes): Intelligent Association.
Building upon Phase 1, a word association feature has been added. Input a word, and the system automatically predicts the next possible word. Memory usage will increase by no more than 0.5MB.
Phase 3 (60 minutes): Dynamic optimization.
Building upon Phase Two, a dynamic word frequency adjustment function has been added. User habits influence the candidate word ranking in real time. Memory usage will increase by no more than 0.5MB, with total memory usage not exceeding 2MB.
Submissions: Submit code after each stage; the system will automatically evaluate it. Those who pass all three stages will be ranked according to their total time.
Professor Li paused, then scanned the entire room: "Now, I declare—the Innovation Cup Programming Contest finals officially open."
The countdown on the big screen was 03:00:00.
The gymnasium fell silent, with only the sound of keyboards clicking.
Lin Dong did not rush to make a move.
He reviewed the requirements for the three stages again, then leaned back in his chair and closed his eyes.
Phase 1: Core Index.
The conventional approach to mapping Pinyin to Chinese characters is to use a Trie tree, which has a time complexity of O(n) and manageable memory usage. However, each node in a Trie tree requires storing 26 pointers, and for 100,000 entries, the memory usage will definitely exceed 1MB. A different approach is needed.
He thought of the data structure that Li Hu had rewritten.
In the second round of the competition, Li Hu's original solution to the problem was 0 (n^2), but after rewriting it, it was reduced to 0 (n log n).
The core improvement was replacing nested loops with hashing and binary search, and changing data storage from a chained table to an array. Lin Dong glanced at it from behind Li Hu at the time, thought the idea was good, and jotted it down. He never expected it would come in handy today.
He opened his eyes and opened the editor.
First, use a hash table to store the mapping from pinyin to word index, and then use an array to store the word itself.
During the query, the hash is used to find the index, and a binary search is used to locate the position, completing the task in one go. The time complexity is O(log n).
(n), memory usage—he calculated it, and it's about 0.6MB.
enough.
He started writing code.
Fingers landed on the keyboard at a moderate pace. Hash functions, collision handling, binary search boundary conditions—
He went through every detail in his mind several times. He wasn't "writing" code; he was "translating" what was in his head.
He wrote for about thirty minutes, then stopped and checked it over. The hash function was fine, the binary search boundary handling was correct, and there were no memory leaks.
He glanced at Li Hu beside him. Li Hu was also typing, his fingers flying across the screen, lines of code appearing one after another. He was writing stage one, using hashing and binary search—exactly the same approach as Lin Dong.
Lin Dong's lips twitched slightly.
He didn't tell Li Hu how to do it, and Li Hu didn't ask him. They were on the same page. The optimal solution to the problem was right there; whoever was skilled enough would see it.
He looked away and continued writing.
After another ten minutes of writing, the code was finished.
He pressed "Compile"—and it passed.
Press "Run" again—all test cases pass.
Response time – he glanced at it, 12ms. Memory usage – 0.58MB.
He took a deep breath and pressed "Submit".
On the big screen, the icons of the Four Heavenly Kings team lit up—submit.
A commotion broke out in the audience.
"So fast? Submitted in just forty minutes?"
"There's still no word from Zhang Yang's team."
"Isn't this too rushed?"
Li Hu turned around and lowered his voice, "Fourth brother, you handed it in?"
"Um."
"So fast?"
Lin Dong didn't answer, staring at the big screen.
A few seconds later, the icon turned red.
Not approved.
A murmur arose from the audience.
"It was returned."
"I told you, it was too rushed."
"Won't the Four Heavenly Kings cause a stir?"
Zhou Lin sat in the audience, gripping Chen Lu's arm so tightly her nails were almost digging into it: "What happened?"
Chen Lu stared at the big screen, her voice steady: "It's not over yet."
Lin Dong stared at the "Not Approved" message on the screen, his face expressionless.
He opened the evaluation feedback and glanced at it—boundary conditions.
The word segmentation boundary between the pinyin "liang" and "lian" was not handled.
He cursed himself inwardly.
It was indeed missed.
He started to change.
An additional check was added to the hash function to process "liang" and "lian" separately.
Five minutes, all done.
After recompiling and rerunning, all test cases passed.
Press "Submit" again.
On the big screen, the icon turned green.
by.
Time taken: 45 minutes.
Lin Dong leaned back in his chair and let out a long sigh.
Li Hu chuckled beside him, "You scared me."
"Continue," Lin Dong said.
Phase 1 is complete, but everyone else's Phase 1 is not yet complete.
Zhang Yang's team hasn't submitted their Phase 1 report yet.
Chen Long and Xu Zang haven't made a move yet, waiting for Lin Dong and Li Hu to finish Phase One so they can move on to Phase Two.
"Phase Two, who's coming?" Lin Dong asked.
Xu Zang spoke up: "I'll do it."
Lin Dong glanced at him.
"What do you need?" Lin Dong asked.
"The code for Phase One," Xu Zang said, "and the dictionary as well."
Lin Dong sent him the code for Phase 1.
Xu Zang opened it, read it from beginning to end, and said nothing.
Then open the editor and start writing.
Lin Dong didn't disturb him, leaning back in his chair and watching.
Xu Zang's approach was different. Phase Two required word association—input a word, and the system would automatically predict the next possible word.
The conventional approach is to count the co-occurrence frequency between words. With 100 entries in the lexicon, there are 10 billion pairs that can't be stored.
Xu Zang did not use conventional methods.
He maps each word to a fixed-dimensional vector and then calculates the similarity between the vectors. Words with high similarity are considered possible next words.
Lin Dong had considered this idea, but hadn't thought about it in depth.
Because the vector dimension is too high, the computational cost is too large. However, Xu Zang used dimensionality reduction—using hashing—to compress the high-dimensional vector into a low-dimensional vector, reducing the computational cost from 0 (n²) to 0 (n).
Xu Zang wrote very quickly, with very little code, but the logic was very convoluted.
Lin Dong read it once and understood it. Chen Long also came over to take a look, didn't say anything, but pushed up his glasses.
Fifty minutes later, Xu Zang stopped pointing.
"I'm done writing," he said.
"Have you checked it?" Chen Long asked.
"No," Xu Zang said.
Lin Dong was taken aback: "No inspection?"
Xu Zang glanced at him: "You check for me."
Lin Dong didn't say anything, but took the code and looked at it line by line.
Hash function, no problem.
Vector dimensionality reduction, no problem.
The similarity calculation did not handle the boundary conditions.
He changed one line of code and added a condition.
"Okay," he said.
Xu Zang nodded and pressed "Submit".
On the big screen, the icons of the Four Heavenly Kings team lit up—submit.
Another commotion erupted in the audience.
"Phase two is submitted too? So fast?"
"Team Zhang Yang hasn't been in Phase Two for very long."
A few seconds later, the icon turned green.
by.
Time taken: 50 minutes.
Li Hu was so excited he almost jumped up from his chair, but Chen Long held him back.
"Don't get excited," Chen Long said. "There's still Phase Three."
Lin Dong glanced at the time on the big screen.
The countdown has one hour and twenty-five minutes left. Team Zhang Yang just passed stage one in sixty-five minutes.
The Four Heavenly Kings took a total of one hour and thirty-five minutes, which was nearly twenty minutes faster than Zhang Yang's team.
But the third stage is the most difficult part.
Dynamic adjustment of word frequency.
User habits influence candidate word ranking in real time. The conventional approach is to use LRU or LFU algorithms, maintain a word frequency table, and update the weights after each input.
However, 0.5MB of memory cannot store much data. 10 entries, each storing an integer frequency, would require 40 bytes, roughly 0.4MB. Adding an LRU doubly linked list would definitely exceed the memory limit.
Lin Dong had another idea.
He studied this algorithm—the approximate counting algorithm—after the second round.
A fixed-size two-dimensional array that does not store specific word frequencies, but only approximate values. Memory usage is fixed at 0.3MB, and the response time is 0 (1).
It wasn't prepared for the finals; I just thought "it might come in handy later," so I wrote a demo on a whim.
I never expected to actually need it today.
He opened the editor and started writing.
The algorithm is not complicated.
Given a 2D array with d rows and w columns, each input is hashed to a specific row and column, and its count is incremented. During a query, the minimum value at that position is used as an approximate count. Error is controllable, and memory usage is fixed.
He wrote very quickly. Every variable, every function, every line of code had been mentally reviewed countless times.
Li Hu leaned closer to take a look, stared at it for a while, and then asked, "Your algorithm is a bit similar to the one in the second round?"
Lin Dong didn't look up: "Mm."
Li Hu scratched his head and didn't ask any more questions.
He recalled that when he rewrote that problem after the second round, Lin Dong stood behind him and glanced at him. At the time, he thought Lin Dong was just looking casually.
Now he knows that Lin Dong has fully understood the essence of that data structure and has even applied it here.
Chen Long also leaned over to take a look, stared for a few seconds, then adjusted his glasses: "When did you write this algorithm?"
"Before," Lin Dong said.
Chen Long didn't ask any more questions.
Twenty minutes later, Lin Dong stopped pointing.
"I'm done writing," he said.
"Have you checked it?" Chen Long asked.
Lin Dong didn't answer; he read it himself.
The hash function is fine, the array boundaries are fine, and the error in the approximate counting is within an acceptable range.
Memory usage—he calculated it, 0.3MB. Adding the 0.58MB from stage one and the 0.4MB from stage two, the total is 1.28MB, far below the 2MB limit.
He pressed "Compile"—passed. He pressed "Run" again—all test cases passed. Response time—7ms.
He took a deep breath and pressed "Submit".
On the big screen, the icons of the Four Heavenly Kings team lit up—submit.
The audience fell silent. Everyone was staring at the icon.
The icon turns green after a few seconds.
by.
Time taken: 40 minutes.
Li Hu froze for a second, then grabbed Chen Long beside him and exclaimed, "We passed! We passed all three stages!"
Chen Long was being choked so tightly he could hardly breathe, but he couldn't break free.
Xu Zang opened his eyes, glanced at the big screen, and a slight smile appeared on his lips.
Lin Dong leaned back in his chair and let out a long sigh.
Total time: 45 minutes + 50 minutes + 40 minutes, 135 minutes. Two hours and 15 minutes.
He glanced at Zhang Yang's team's progress. Stage three, still writing.
Nearly forty minutes later, Zhang Yang's team submitted their submission.
by.
However, the total time taken was almost forty minutes longer than that of the Four Heavenly Kings.
Lin Dong withdrew his gaze.
Zhang Yang's team lost.
Because their approach was wrong. LRU is the conventional optimal solution, but in this scenario, there isn't enough memory. The approximate counting algorithm he used is a dimensionality reduction approach.
The starting point of this journey was the night after the second round ended, when Li Hu was rewriting code in his dormitory and he stood behind him and took a look.
At the time, he didn't think much of it; he just felt that "this data structure could be optimized further." So he did some research and wrote a demo.
I never expected to need it today.
He glanced at Li Hu.
Li Hu was still excited, talking to Chen Long, his face beaming like a fool.
He was unaware that Lin Dong had used his approach, nor that Lin Dong had prepared the Phase 3 algorithm in advance because of his habit.
He just wanted to write his code better.
Lin Dong withdrew his gaze, and the corner of his mouth twitched slightly.
Sometimes it's like that; you don't know what you've done, but everything you do paves the way for the future.
The final rankings were displayed on the big screen.
First Place: The Four Heavenly Kings. All three stages completed. Total Time: 135 minutes. Code Quality:
S.
Second place: Zhang Yang Team. Completed all three stages. Total time: 175 minutes. Code quality:
B+.
Third place: Geek Alliance Team. Passed both stages.
Other teams: Stage 1 or below.
The audience erupted in chaos.
"One hundred and thirty-five minutes? Less than two and a half hours?"
"Zhang Yang's team took 175 minutes, almost 40 minutes short!"
"The Four Heavenly Kings are too powerful!"
"That number 4, Lin Dong, wrote the third stage all by himself, and it only took him forty minutes."
"Really? Zhang Yang has been writing for over forty minutes and it still hasn't passed."
"Zhang Yang eventually passed, but the time difference was too great."
Zhou Lin jumped up from her seat and screamed. Zhao Yu also stood up and clapped her hands. Chen Lu didn't stand up, but she loosened her bag strap, her lips curved into a smile, and her eyes brightened.
Li Hu remained seated, staring blankly at the words "First Place" on the big screen for several seconds. Then he stood up, turned around, raised his hands towards the audience, and gave them two thumbs up.
Laughter and applause erupted from the audience.
Chen Long pushed up his glasses, and the corners of his mouth curved slightly. Xu Zang leaned back in his chair, his eyes closed, but the corners of his mouth were also curved.
Lin Dong sat on the far side, watching the three of them.
It's a win.